The complexity of approximate (coarse) correlated equilibrium for incomplete information games
<|reference_start|>The complexity of approximate (coarse) correlated equilibrium for incomplete information games: 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 $\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 [PR'24, DDFG'24] for learning $\epsilon$-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 $\epsilon$-approximate $\mathit{coarse}$ correlated equilibrium   On the positive side, we give uncoupled dynamics that reach $\epsilon$-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.<|reference_end|>
@article{peng2024the,
    title={The complexity of approximate (coarse) correlated equilibrium for
  incomplete information games},
    author={Binghui Peng and Aviad Rubinstein},
    journal={arXiv preprint arXiv:2406.02357},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.02357},
    primaryClass={cs.GT cs.AI cs.DS cs.LG}
}