Correlated Equilibria of Games with Many Players

Hans Keiding & Bezalel Peleg

We consider the structure of the set of correlated equilibria for games with a large number n of players. Since the number of equilibrium constraints grows slower than the number of strategy arrays, it might be conjectured that the set of correlated equilibra is large. In this paper we show (1) that the average relative measure of the solution set is smaller than 2^{-n}, but also (2) that the solution set contains a number c^{n} of equilibria having disjoint supports with a probability going to I as n grows large. The proof of the latter result hinges on a combinatorial result on the number of nonnegative linear combinations of vectors representing a given point, which may be of independent interest.

September, 1998
Published in: 
International Journal of Game Theory 29 (2000), 375-389