mlsanityData to 14 Oct 2026

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

arXiv 2406.02357 ↗First posted 4 Jun 2024cs.GT cs.AI cs.DScited by 4

Not on the map. Why?

Abstract (arXiv)

We study the iteration complexity of decentralized learning of approximate correlated equilibria in incomplete information games. On the negative side, we prove that in mathitextensive-mathitform mathitgames, assuming mathsfPPAD notsubset mathsfTIME(n^mathsfpolylog(n)), any polynomial-time learning algorithms must take at least 2^log21-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 mathitcoarse correlated equilibrium On the positive side, we give uncoupled dynamics that reach ε-approximate correlated equilibria of a mathitBayesian mathitgame in polylogarithmic iterations, without any dependence of the number of types. This demonstrates a separation between Bayesian games and extensive-form games.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 29 of its 69 references that are in the map. First posted on arXiv 4 Jun 2024.

Builds on

29 of 69 references.

References · 29

  1. 2015Fast Convergence of Regularized Learning in Gamescited by 150
  2. 2018Deep Counterfactual Regret Minimizationcited by 103
  3. 2021Near-Optimal No-Regret Learning in General Gamescited by 85
  4. 2020The Complexity of Constrained Min-Max Optimizationcited by 82
  5. 2020Hedging in games: Faster convergence of external and swap regretscited by 57
  6. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 49
  7. 2021Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Gamescited by 43
  8. 2022Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Gamescited by 35
  9. 2023Fast swap regret minimization and applications to approximate correlated equilibriacited by 32
  10. 2016Settling the complexity of computing approximate two-player Nash equilibriacited by 31
  11. 2019Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functionscited by 26
  12. 2021Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibriumcited by 22
17 more
  1. 2022Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Gamescited by 19
  2. 2014Inapproximability of Nash Equilibriumcited by 17
  3. 2022Efficient Phi-Regret Minimization in Extensive-Form Games via Online Mirror Descentcited by 15
  4. 2023Near Optimal Memory-Regret Tradeoff for Online Learningcited by 15
  5. 2022The Complexity of Infinite-Horizon General-Sum Stochastic Gamescited by 11
  6. 2023From External to Swap Regret 2.0: An Efficient Reduction and Oblivious Adversary for Large Action Spacescited by 11
  7. 2023Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Gamescited by 10
  8. 2021On the Complexity of Equilibrium Computation in First-Price Auctionscited by 6
  9. 2019Efficient Regret Minimization Algorithm for Extensive-Form Correlated Equilibriumcited by 5
  10. 2023Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rulescited by 5
  11. 2023Bayes correlated equilibria, no-regret dynamics in Bayesian games, and the price of anarchycited by 5
  12. 2015Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nashcited by 4
  13. 2021Computational Hardness of the Hylland-Zeckhauser Schemecited by 3
  14. 2022Near-Optimal Phi-Regret Learning in Extensive-Form Gamescited by 3
  15. 2013The Complexity of Fairness through Equilibriumcited by 2
  16. 2021Public Goods Games in Directed Networkscited by 2
  17. 2023On the Complexity of Computing Sparse Equilibria and Lower Bounds for No-Regret Learning in Gamescited by 2

Built on by

Cited by year

Citing papers per year: 2024: 3; 2025: 1.

4 papers.

  1. 2025Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Gamescited by 3
  2. 2024Barriers to Welfare Maximization with No-Regret Learningcited by 0
  3. 2024Computational Lower Bounds for Regret Minimization in Normal-Form Gamescited by 0
  4. 2024Explore Reinforced: Equilibrium Approximation with Reinforcement Learningcited by 0