The Complexity of Approximate (coarse) Correlated Equilibrium for Incomplete Information Games

Abstract

We study the iteration complexity of decentralized learning of approximate correlated equilibria in incomplete information games. On the negative side, we prove that in extensive-form games, assuming $\mathsf{PPAD} \not\subset \mathsf{TIME}(n^{\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 $\epsilon$-approximate correlated equilibrium, where $|\mathcal{I}|$ is the number of nodes in the game and $\epsilon > 0$ is an absolute constant. This nearly matches, up to the $o(1)$ term, the algorithms of (Peng and Rubinstein STOC’2024, Dagan et al. STOC’2024) for learning $\epsilon$-approximate correlated equilibrium, and resolves an open question of Anagnostides, Kalavasis, Sandholm, and Zampetakis (Anagnostides et al. ITCS 2024). Our lower bound holds even for the easier solution concept of $\epsilon$-approximate coarse correlated equilibrium. On the positive side, we give uncoupled dynamics that reach $\epsilon$-approximate correlated equilibria of a Bayesian game in polylogarithmic iterations, without any dependence of the number of types. This demonstrates a separation between Bayesian games and extensive-form games.