Correlated equilibria of games with many players (Q1423671)

Let \(G_{m,n}\) be the class of strategic games with \(n\) players, where each player has \(m\geq 2\) pure strategies. We are interested in the structure of the set of correlated equilibria of games in \(G_{m,n}\), when \(n \to \infty\). As the number of equilibrium constraints grows slower than the number of pure strategy profiles, it might be conjectured that the set of correlated equilibria becomes large. In this paper, we show that (1) the average relative measure of the set of correlated equilibria is smaller than \(2^{-n}\); and (2) for each \(1<c<m\), the solution set contains \(c^n\) correlated equilibria having disjoint supports with a probability going to 1 as \(n\) grows large. The proof of the second result hinges on the following inequality: Let \(\mathbf c_1,\ldots, \mathbf c_l\) be independent and symmetric random vectors in \(\mathbb R^k\), \(l\geq k\). Then the probability that the convex hull of \(\mathbf c_1,\ldots, \mathbf c_l\) intersects \(\mathbb R^k_+\) is greater than or equal to \(1 - 2^{-l} [ \binom l0+\cdots+ \binom {l}{k-1}]\).