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 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 {O}\(msqrt{n}\) for fixed varepsilon. For CCE, we extend techniques from quantum algorithms for zero-sum games to multi-player settings, achieving query complexity {O}\(msqrt{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.