mlsanityData to 14 Oct 2026

Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games

arXiv 2510.16782 ↗First posted 19 Oct 2025quant-ph cs.CC cs.GTcited by 0

Not on the map. Why?

Abstract (arXiv)

Computing Nash equilibria of zero-sum games in classical and quantum settings is extensively studied. For general-sum games, computing Nash equilibria is PPAD-hard and the computing of a more general concept called correlated equilibria has been widely explored in game theory. In this paper, we initiate the study of quantum algorithms for computing varepsilon-approximate correlated equilibria (CE) and coarse correlated equilibria (CCE) in multi-player normal-form games. Our approach utilizes quantum improvements to the multi-scale Multiplicative Weight Update (MWU) method for CE calculations, achieving a query complexity of tildeO(m√n) for fixed varepsilon. For CCE, we extend techniques from quantum algorithms for zero-sum games to multi-player settings, achieving query complexity tildeO(m√n/varepsilon2.5). Both algorithms demonstrate a near-optimal scaling in the number of players m and actions n, as confirmed by our quantum query lower bounds.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 17 of its 38 references that are in the map. First posted on arXiv 19 Oct 2025.

Builds on

17 of 38 references.

References · 17

  1. 2019Introduction to Online Convex Optimizationcited by 803
  2. 2015Fast Convergence of Regularized Learning in Gamescited by 150
  3. 2021Near-Optimal No-Regret Learning in General Gamescited by 85
  4. 2020Hedging in games: Faster convergence of external and swap regretscited by 57
  5. 2021Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Gamescited by 43
  6. 2022Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Gamescited by 35
  7. 2023Fast swap regret minimization and applications to approximate correlated equilibriacited by 32
  8. 2021Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Updatecited by 20
  9. 2019Sublinear quantum algorithms for training linear and kernel-based classifierscited by 19
  10. 2025Faster Rates for No-Regret Learning in General Games via Cautious Optimismcited by 10
  11. 2023Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Samplingcited by 7
  12. 2025Cautious Optimism: A Meta-Algorithm for Near-Constant Regret in General Gamescited by 7
5 more
  1. 2022Matrix Multiplicative Weights Updates in Quantum Zero-Sum Games: Conservation Laws & Recurrencecited by 6
  2. 2023Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Gamescited by 6
  3. 2023No-Regret Learning and Equilibrium Computation in Quantum Gamescited by 5
  4. 2023Learning in quantum gamescited by 4
  5. 2023A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Gamescited by 4

Built on by

Not cited yet.