{"ID":2853119,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.16782","arxiv_id":"2510.16782","title":"Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games","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 $\\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.","short_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 qu...","url_abs":"https://arxiv.org/abs/2510.16782","url_pdf":"https://arxiv.org/pdf/2510.16782v1","authors":"[\"Tongyang Li\",\"Xinzhao Wang\",\"Yexin Zhang\"]","published":"2025-10-19T10:14:16Z","proceeding":"quant-ph","tasks":"[\"quant-ph\",\"cs.CC\",\"cs.GT\",\"cs.LG\"]","methods":"[]","has_code":false}