The complexity of approximate (coarse) correlated equilibrium for incomplete information games
This resolves an open question in algorithmic game theory by establishing computational limits for learning equilibria in games with incomplete information, which is incremental but important for understanding decentralized learning dynamics.
The paper tackles the problem of decentralized learning of approximate correlated equilibria in incomplete information games, proving a nearly tight lower bound of at least 2^(log_2^{1-o(1)}(|I|)) iterations for extensive-form games and providing an algorithm that achieves polylogarithmic iterations for Bayesian games, demonstrating a separation between these game types.
We study the iteration complexity of decentralized learning of approximate correlated equilibria in incomplete information games. On the negative side, we prove that in $\mathit{extensive}$-$\mathit{form}$ $\mathit{games}$, assuming $\mathsf{PPAD} \not\subset \mathsf{TIME}(n^{\mathsf{polylog}(n)})$, any polynomial-time learning algorithms must take at least $2^{\log_2^{1-o(1)}(|\mathcal{I}|)}$ iterations to converge to the set of $ε$-approximate correlated equilibrium, where $|\mathcal{I}|$ is the number of nodes in the game and $ε> 0$ is an absolute constant. This nearly matches, up to the $o(1)$ term, the algorithms of [PR'24, DDFG'24] for learning $ε$-approximate correlated equilibrium, and resolves an open question of Anagnostides, Kalavasis, Sandholm, and Zampetakis [AKSZ'24]. Our lower bound holds even for the easier solution concept of $ε$-approximate $\mathit{coarse}$ correlated equilibrium On the positive side, we give uncoupled dynamics that reach $ε$-approximate correlated equilibria of a $\mathit{Bayesian}$ $\mathit{game}$ in polylogarithmic iterations, without any dependence of the number of types. This demonstrates a separation between Bayesian games and extensive-form games.