The complexity of approximate (coarse) correlated equilibrium for incomplete information games

Binghui Peng, Aviad Rubinstein
Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4158-4184, 2024.

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 PPAD⊄, 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v247-peng24a, title = {The complexity of approximate (coarse) correlated equilibrium for incomplete information games}, author = {Peng, Binghui and Rubinstein, Aviad}, booktitle = {Proceedings of Thirty Seventh Conference on Learning Theory}, pages = {4158--4184}, year = {2024}, editor = {Agrawal, Shipra and Roth, Aaron}, volume = {247}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v247/peng24a/peng24a.pdf}, url = {https://proceedings.mlr.press/v247/peng24a.html}, 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.} }
Endnote
%0 Conference Paper %T The complexity of approximate (coarse) correlated equilibrium for incomplete information games %A Binghui Peng %A Aviad Rubinstein %B Proceedings of Thirty Seventh Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2024 %E Shipra Agrawal %E Aaron Roth %F pmlr-v247-peng24a %I PMLR %P 4158--4184 %U https://proceedings.mlr.press/v247/peng24a.html %V 247 %X 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.
APA
Peng, B. & Rubinstein, A.. (2024). The complexity of approximate (coarse) correlated equilibrium for incomplete information games. Proceedings of Thirty Seventh Conference on Learning Theory, in Proceedings of Machine Learning Research 247:4158-4184 Available from https://proceedings.mlr.press/v247/peng24a.html.

Related Material