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

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

39th Conference on Neural Information Processing Systems (NeurIPS 2025).