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

2024/06/04 by Binghui Peng, Aviad Rubinstein, Peng, Binghui +1 · 1 citation
Decision Sciences · Economics, Econometrics and Finance · #Game Theory and Applications #Economic theories and models #Game Theory and Voting Systems

paper · pdf · doi:10.48550/arxiv.2406.02357

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 \not⊂ TIME(n^polylog(n)), any polynomial-time learning algorithms must take at least 2^log₂^1-o(1)(|I|) iterations to converge to the set of ε-approximate correlated equilibrium, where |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 coarse correlated equilibrium On the positive side, we give uncoupled dynamics that reach ε-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.

Cited by

• Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games

Related

• Efficient Decentralized Learning Dynamics for Extensive-Form Coarse Correlated Equilibrium: No Expensive Computation of Stationary Distributions Required
• Finding Any Nontrivial Coarse Correlated Equilibrium Is Hard
• Communication Complexity of Correlated Equilibrium in Two-Player Games
• The Complexity of Markov Equilibrium in Stochastic Games
• On the Complexity of the Optimal Correlated Equilibria in Extensive-Form Games