Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games
This work provides efficient quantum algorithms for a fundamental problem in game theory, potentially benefiting computational economics and multi-agent systems, though it is incremental as it extends known quantum techniques to new equilibria types.
The paper tackles the problem of computing approximate correlated equilibria (CE) and coarse correlated equilibria (CCE) in multi-player general-sum games using quantum algorithms, achieving near-optimal query complexities of \tilde{O}(m√n) for CE and \tilde{O}(m√n/ε^{2.5}) for CCE.
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 $\tilde{O}(m\sqrt{n})$ for fixed $\varepsilon$. For CCE, we extend techniques from quantum algorithms for zero-sum games to multi-player settings, achieving query complexity $\tilde{O}(m\sqrt{n}/\varepsilon^{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.