Cover Image

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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Li, Tongyang, Wang, Xinzhao, Zhang, Yexin
Format:	Preprint
Published:	2025
Subjects:	Quantum Physics Computational Complexity Computer Science and Game Theory Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games
by: Anagnostides, Ioannis, et al.
Published: (2025)

Efficiently Computing Equilibria in Budget-Aggregation Games
by: Becker, Patrick, et al.
Published: (2025)

On the Complexity of the Optimal Correlated Equilibria in Extensive-Form Games
by: Cheval, Vincent, et al.
Published: (2025)

$\widetilde{O}(T^{-1})$ Convergence to (Coarse) Correlated Equilibria in Full-Information General-Sum Markov Games
by: Mao, Weichao, et al.
Published: (2024)

Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation
by: Zhang, Brian, et al.
Published: (2022)

Algorithms and Complexity for Computing Nash Equilibria in Adversarial Team Games
by: Anagnostides, Ioannis, et al.
Published: (2023)

Tight Inapproximability of Nash Equilibria in Public Goods Games
by: Dinh, Jérémi Do, et al.
Published: (2024)

Approximating Nash Equilibria in General-Sum Games via Meta-Learning
by: Sychrovský, David, et al.
Published: (2025)

Near Optimal Convergence to Coarse Correlated Equilibrium in General-Sum Markov Games
by: Yorulmaz, Asrin Efe, et al.
Published: (2025)

On the Computation of Equilibria in Discrete First-Price Auctions
by: Filos-Ratsikas, Aris, et al.
Published: (2024)

On the Complexity of Stationary Nash Equilibria in Discounted Perfect Information Stochastic Games
by: Hansen, Kristoffer Arnsfelt, et al.
Published: (2025)

Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Games
by: Cai, Yang, et al.
Published: (2024)

Constant Inapproximability of Pacing Equilibria in Second-Price Auctions
by: Chen, Xi, et al.
Published: (2025)

On the Complexity of Learning Nash Equilibria
by: Biggar, Oliver, et al.
Published: (2026)

Hardness of Approximate Hylland-Zeckhauser Equilibria
by: Braverman, Mark, et al.
Published: (2026)

Swap Regret and Correlated Equilibria Beyond Normal-Form Games
by: Arunachaleswaran, Eshwar Ram, et al.
Published: (2025)

A Smoothed FPTAS for Equilibria in Congestion Games
by: Giannakopoulos, Yiannis
Published: (2023)

Equilibrium Computation in First-Price Auctions with Correlated Priors
by: Filos-Ratsikas, Aris, et al.
Published: (2025)

Market Games for Generative Models: Equilibria, Welfare, and Strategic Entry
by: Wei, Xiukun, et al.
Published: (2026)

Multiplicative weights, equalizers, and P=PPAD
by: Avramopoulos, Ioannis
Published: (2016)

When Simple is Near Optimal in Security Games
by: Jalota, Devansh, et al.
Published: (2024)

Consumable Data via Quantum Communication
by: Gilboa, Dar, et al.
Published: (2024)

Computing Optimal Equilibria and Mechanisms via Learning in Zero-Sum Extensive-Form Games
by: Zhang, Brian Hu, et al.
Published: (2023)

Robust Stackelberg Equilibria
by: Gan, Jiarui, et al.
Published: (2023)

Optimally Installing Strict Equilibria
by: McMahan, Jeremy, et al.
Published: (2025)

Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games
by: Cai, Yang, et al.
Published: (2025)

On Tractable $Φ$-Equilibria in Non-Concave Games
by: Cai, Yang, et al.
Published: (2024)

Correlated Equilibria of Classical Strategic Games with Quantum Signals
by: La Mura, Pierfrancesco
Published: (2003)

Pessimism-Free Offline Learning in General-Sum Games via KL Regularization
by: Chen, Claire, et al.
Published: (2026)

Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability
by: Zhang, Brian Hu, et al.
Published: (2025)

The Complexity of Symmetric Bimatrix Games with Common Payoffs
by: Ghosh, Abheek, et al.
Published: (2024)

The Complexity of Correlated Equilibria in Generalized Games
by: Bernasconi, Martino, et al.
Published: (2025)

Nearly-Optimal Bandit Learning in Stackelberg Games with Side Information
by: Balcan, Maria-Florina, et al.
Published: (2025)

Scale-Invariant Regret Matching and Online Learning with Optimal Convergence: Bridging Theory and Practice in Zero-Sum Games
by: Zhang, Brian Hu, et al.
Published: (2025)

Last-Iterate Convergence of No-Regret Learning for Equilibria in Bargaining Games
by: Kamp, Serafina, et al.
Published: (2025)

The Complexity of Pure Strategy Relevant Equilibria in Concurrent Games
by: Bhaduri, Purandar
Published: (2025)

Modelling Network Resilience: The Complexity of Some Graph Division Games
by: Gutowski, Grzegorz, et al.
Published: (2026)

Computing Pure-Strategy Nash Equilibria in a Two-Party Policy Competition: Existence and Algorithmic Approaches
by: Lin, Chuang-Chieh, et al.
Published: (2025)

Solving Four Open Problems about Core Stability in Altruistic Hedonic Games
by: Rothe, Jörg, et al.
Published: (2025)

Belief-Invariant and Quantum Equilibria in Games of Incomplete Information
by: Auletta, Vincenzo, et al.
Published: (2016)