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

2025/10/19 by Tongyang Li, Xinzhao Wang, Li, Tongyang +3
Computer Science · Physics and Astronomy · #Quantum Computing Algorithms and Architecture #Quantum Mechanics and Applications #Quantum Information and Cryptography

paper · pdf · doi:10.48550/arxiv.2510.16782

Abstract

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 ε-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 O(m√(n)) for fixed ε. For CCE, we extend techniques from quantum algorithms for zero-sum games to multi-player settings, achieving query complexity O(m√(n)/ε^2.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.

Citations

• Cautious Optimism: A Meta-Algorithm for Near-Constant Regret in General Games
• Fast swap regret minimization and applications to approximate correlated equilibria
• Learning in quantum games
• Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling
• Matrix Multiplicative Weights Updates in Quantum Zero-Sum Games: Conservation Laws & Recurrence
• Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Games
• Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update
• Near-Optimal No-Regret Learning in General Games
• Hedging in games: Faster convergence of external and swap regrets
• Quantum algorithms for zero-sum games
• Introduction to Online Convex Optimization
• Fast Convergence of Regularized Learning in Games
• Polynomial-time Computation of Exact Correlated Equilibrium in Compact Games
• Settling the Complexity of Computing Two-Player Nash Equilibria
• Settling the complexity of computing two-player Nash equilibria
• Creating superpositions that correspond to efficiently integrable probability distributions
• Strengths and Weaknesses of Quantum Computing
• A class of games possessing pure-strategy Nash equilibria

Related

• Quantum algorithms for zero-sum games
• Quantum Strategic Game Theory
• On characterizing quantum correlated equilibria
• Determining Quantum Correlation through Nash Equilibria in Constant-Sum Games
• A quantum protocol for sampling correlated equilibria unconditionally and without a mediator