Settling the Support Complexity of Correlated Equilibria

We study the support complexity of approximate correlated equilibria (CE) in two-player games, that is, the minimum number of pure action profiles that must be assigned positive probability to approximate a correlated equilibrium of a two-player matrix game. For $\varepsilon$-approximate coarse correlated equilibria, constant approximation is possible with support $O(\log N/\varepsilon^2)$ in $N\times N$ games. For correlated equilibria, the best known upper bound was $O(\log^2 N/\varepsilon^4)$ [Babichenko et al., 2014, 2017], but whether this bound was tight remained open. We establish a matching lower bound, resolving the open question of Ko and Schvartzman [2017]. Specifically, we show that, already for two-player zero-sum games, for every $1\leq k\leq N^{1/2}$ the worst-case correlated-equilibrium gap achievable by a distribution supported on at most $k$ pure profiles is $$ Θ\left( \min\left\{1,\frac{\sqrt{\log N}}{k^{1/4}}\right\} \right), $$ which implies a $Θ(\log^2 N/\varepsilon^4)$ worst-case support bound. The proof builds on a probabilistic-method construction based on random sign matrices.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-16
DOI
https://doi.org/10.48550/arxiv.2611.20362
Primary Topic
Game Theory and Applications
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Settling the Support Complexity of Correlated Equilibria

Akbar Rafiey, Ashkan Soleymani, Gabriele Farina, Patrick Jaillet
arXiv (Cornell University)
Game Theory and Applications
preprint

Settling the Support Complexity of Correlated Equilibria

Akbar Rafiey, Ashkan Soleymani, Gabriele Farina, Patrick Jaillet
preprint en

Abstract

We study the support complexity of approximate correlated equilibria (CE) in two-player games, that is, the minimum number of pure action profiles that must be assigned positive probability to approximate a correlated equilibrium of a two-player matrix game. For $\varepsilon$-approximate coarse correlated equilibria, constant approximation is possible with support $O(\log N/\varepsilon^2)$ in $N\times N$ games. For correlated equilibria, the best known upper bound was $O(\log^2 N/\varepsilon^4)$ [Babichenko et al., 2014, 2017], but whether this bound was tight remained open. We establish a matching lower bound, resolving the open question of Ko and Schvartzman [2017]. Specifically, we show that, already for two-player zero-sum games, for every $1\leq k\leq N^{1/2}$ the worst-case correlated-equilibrium gap achievable by a distribution supported on at most $k$ pure profiles is $$ Θ\left( \min\left\{1,\frac{\sqrt{\log N}}{k^{1/4}}\right\} \right), $$ which implies a $Θ(\log^2 N/\varepsilon^4)$ worst-case support bound. The proof builds on a probabilistic-method construction based on random sign matrices.

arXiv (Cornell University)
Game Theory and Applications
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon