Breaking the 1/3 Barrier for Approximate Nash Equilibria in Symmetric Bimatrix Games
cs.GT, cs.LG
Submitted: 2026-10-18
Updated: 2026-10-18
Comments: ACM-SIAM Symposium on Discrete Algorithms (SODA), 2027
License: http://creativecommons.org/licenses/by/4.0/
The gist: We give the first unconditional family of polynomial-time algorithms that breaks the 1/3 approximation barrier for symmetric bimatrix games.
Abstract
We give the first unconditional family of polynomial-time algorithms that breaks the 1/3 approximation barrier for symmetric bimatrix games. For every fixed δ>0, an algorithm in this family computes a symmetric (1-1/sqrt 2 +δ) -approximate Nash equilibrium, improving on the previous best guarantee of (1/3+δ) due to Kontogiannis and Spirakis [2011].
Related papers
- Exact Regret Frontiers and Externality Scheduling in Centralized Serial-Dictatorship Bandits
- In-Context Credit Assignment via the Core
- Optimal Regret for Online Market Making with Limit Order Book
- Breaking 1/epsilon Barrier in Quantum Zero-Sum Games: Generalizing Metric Subregularity for Spectraplexes
- Enhancing Affine Maximizer Auctions with Correlation-Aware Payment
- LLM Bidders Preserve the Mechanism-Level Orderings of Human Bidders