TL;DR
This paper resolves a long-standing open question in game theory by proving a tight lower bound on the "support complexity" of approximate correlated equilibria. The authors show that in the worst case, representing an $\varepsilon$-approximate correlated equilibrium in an $N \times N$ game requires a distribution over $\Theta(\log^2 N / \varepsilon^4)$ action profiles, proving that the previously known upper bound is optimal and that correlation does not necessarily lead to sparser equilibrium representations.
What Problem Does This Paper Address?
In game theory, a Correlated Equilibrium (CE) is a joint probability distribution over action profiles. Imagine a mediator who privately recommends an action to each player; the distribution is an equilibrium if no player has an incentive to deviate from their recommendation, assuming others follow theirs.
A key practical question is: How "complex" is this distribution? Specifically, what is its support size—the minimum number of action profiles (cells in the payoff matrix) that must have a non-zero probability?
We already knew that:
- Nash Equilibria (NE): Players randomize independently. Each player needs a support of $O(\log N / \varepsilon^2)$.
- Coarse Correlated Equilibria (CCE): A simpler version where players decide to deviate before seeing their recommendation. This only requires a joint support of $O(\log N / \varepsilon^2)$.
For the standard Correlated Equilibrium, where deviations can depend on the specific recommendation (using "swap functions"), there was a quadratic gap. The best upper bound was $O(\log^2 N / \varepsilon^4)$, but the best lower bound was only $\Omega(\log N / \varepsilon^2)$. This paper asks: Is the $\varepsilon^4$ dependence real, or can we find much sparser correlated equilibria?
Methods
The authors use the probabilistic method to construct a "hard" game instance that forces any sparse distribution to have high "regret" (incentive to deviate).
- Random Sign Matrices: They construct a zero-sum game using a matrix $A$ where each entry is an independent Rademacher variable ($\pm 1$).
- Sparse Rademacher Norming: They prove a new technical result showing that for a random sign matrix, any sparse vector will, with high probability, have a large inner product with at least one row (or column) of the matrix. This means a player will always find a "swap" that significantly improves their payoff if the distribution is too sparse.
- Mixed-Norm Interpolation: To bridge the gap between individual row/column sparsity and the total joint support $k$, the authors employ Blei’s mixed 4/3 inequality. This analytical tool allows them to bound the total "detectable mass" of the distribution, leading to the specific $k^{1/4}$ scaling that eventually yields the $\varepsilon^4$ lower bound.
Datasets
As a theoretical paper in mathematical game theory, this work does not use empirical datasets. Instead, it relies on:
- Synthetic Game Constructions: Specifically, $N \times N$ zero-sum games derived from random $\pm 1$ matrices.
- Mathematical Proofs: Leveraging probability theory, functional analysis (Blei's inequality), and concentration of measure.
Key Insights and Ideas
- Correlation isn't a Sparsity Shortcut: One might hope that by allowing players' actions to be correlated, we could "pack" an equilibrium into fewer action profiles than the independent product of two Nash strategies. This paper shows that in the worst case, you can't. The product of two $O(\log N / \varepsilon^2)$ Nash supports gives $O(\log^2 N / \varepsilon^4)$ joint support, and this paper proves you generally can't do better.
- The Power of Swap Functions: The reason CE is harder to satisfy than CCE is the sheer number of possible deviations. In CCE, there are only $N$ constant deviations. In CE, there are $N^N$ possible "swap functions." This paper demonstrates that this massive deviation space fundamentally forces the distribution to be more spread out.
- The $k^{1/4}$ Scaling: The most surprising technical "aha" moment is the derivation of the $\Theta(k^{-1/4})$ gap. This specific exponent is what settles the $\varepsilon^{-4}$ complexity, moving it away from the more common $\varepsilon^{-2}$ seen in simpler equilibrium notions.
Key Results
- The Matching Lower Bound: For any distribution supported on $k$ profiles, there exists a game where the CE gap is at least $\Omega\left(\min\left\{1, \frac{\sqrt{\log N}}{k^{1/4}}\right\}\right)$.
- Tight Complexity: The worst-case support complexity for $\varepsilon$-approximate CE is exactly $\Theta(\log^2 N / \varepsilon^4)$.
- Separation of Equilibrium Notions: This result formally separates CE from CCE in terms of support complexity. CCE is "cheaper" to represent ($\varepsilon^{-2}$) than CE ($\varepsilon^{-4}$).
- Implications for Learning: This result suggests that certain types of "bandit" learning algorithms—which might try to use a sparse history of play as a certificate of convergence to a CE—are fundamentally limited in how quickly they can provide such a certificate.
Limitations and Future Work
- Two-Player Focus: The results are derived for two-player games. While this is the standard starting point, the support complexity for $n$-player games remains an area for further exploration.
- Worst-Case vs. Average-Case: The paper establishes a worst-case bound. Many games encountered in the real world (e.g., those with specific structures like smoothness or low rank) might admit much sparser approximate equilibria.
- Explicit Constructions: The "hard" game is found via the probabilistic method (it exists with high probability). Finding an explicit, non-random matrix that achieves this lower bound is a potential next step for combinatorialists.
Summary updated