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

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

URL: http://arxiv.org/abs/2510.16782v1
Date: Sun, 19 Oct 2025 10:14:16 GMT
Title: Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games
Authors: Tongyang Li, Xinzhao Wang, Yexin Zhang,
Abstract summary: For general-sum games, computing Nash equilibria is PPAD-hard and the computing of correlated equilibria has been widely explored in game theory.<n>We study quantum algorithms for computing $varepsilon$-approximate correlated equilibria (CE) and coarse correlated equilibria (CCE) in multi-player normal-form games.
Score: 14.684351170028853
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
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.

Related papers

Quantum EigenGame for excited state calculation [8.957579200590988]
We extend the EigenGame algorithm for both a $0textth$-order approach and for quantum computers.<n>Results show that using the Quantum EigenGame allows us to converge to excited states of a given Hamiltonian without the need of a deflation step.
arXiv Detail & Related papers (2025-03-17T18:48:40Z)
Efficiently Solving Turn-Taking Stochastic Games with Extensive-Form Correlation [52.16923999754027]
We give an algorithm for computing a Stackelberg extensive-form correlated equilibrium.<n>We also give an efficient algorithm for approximately computing an optimal extensive-form correlated equilibrium.<n>Our algorithm for approximately optimal EFCE is, to our knowledge, the first that achieves 3 desiderata simultaneously.
arXiv Detail & Related papers (2024-12-22T09:12:05Z)
Computational Lower Bounds for Regret Minimization in Normal-Form Games [68.66209476382213]
We provide evidence that existing learning algorithms, such as multiplicative weights update, are close to optimal. Our results are obtained in the algorithmic framework put forward by Kothari and Mehta.
arXiv Detail & Related papers (2024-11-04T00:39:52Z)
Barriers to Welfare Maximization with No-Regret Learning [68.66209476382213]
We prove lower bounds for computing a near-optimal $T$-sparse CCE. In particular, we show that the inapproximability of maximum clique precludes attaining any non-trivial sparsity in time.
arXiv Detail & Related papers (2024-11-04T00:34:56Z)
A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [95.50895904060309]
We introduce the Optimistic Matrix Multiplicative Weights Update (OMMWU) algorithm and establish its average-iterate convergence complexity as $mathcalO(d/epsilon)$ to $epsilon$-Nash equilibria.<n>This quadratic speed-up sets a new benchmark for computing $epsilon$-Nash equilibria in quantum zero-sum games.
arXiv Detail & Related papers (2023-11-17T20:38:38Z)
Payoff-based learning with matrix multiplicative weights in quantum games [35.111876815522116]
We study the problem of learning in quantum games - and other classes of semidefinite games - with scalar, payoff-based feedback. We introduce a suite of minimal-information matrix multiplicative weights (3MW) methods tailored to different information frameworks. We show that the 3MW method with deterministic payoff feedback retains the convergence rate of the vanilla, full information MMW algorithm in quantum min-max games.
arXiv Detail & Related papers (2023-11-04T14:56:17Z)
Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games [10.79781442303645]
We propose the first online quantum algorithm for solving zero-sum games. Our algorithm generates classical outputs with succinct descriptions. At the heart of our algorithm is a fast quantum multi-sampling procedure for the Gibbs sampling problem.
arXiv Detail & Related papers (2023-04-27T14:02:54Z)
Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
We develop the concepts of Mean-Field correlated and coarse-correlated equilibria. We show that they can be efficiently learnt in emphall games, without requiring any additional assumption on the structure of the game.
arXiv Detail & Related papers (2022-08-22T08:31:46Z)
Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
We present the first line of algorithms that require only $widetildemathcalO((XA+YB)/varepsilon2)$ episodes of play to find an $varepsilon$-approximate Nash equilibrium in two-player zero-sum games. This improves upon the best known sample complexity of $widetildemathcalO((X2A+Y2B)/varepsilon2)$ by a factor of $widetildemathcalO(maxX,
arXiv Detail & Related papers (2022-02-03T18:18:28Z)
Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
Two-team zero-sum games are defined as multi-player games where players are split into two competing sets of agents. We focus on the solution concept of Nash equilibria (NE) We show that computing NE for this class of games is $textithard$ for the complexity class $mathrm$.
arXiv Detail & Related papers (2021-11-07T21:15:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.