CS Paper Radar

A Simple Algorithm Breaking the 1/3 Barrier for Approximate Nash Equilibria in Bimatrix Games

Dongchen Li, Hanyu Li

cs.GT cs.DM ·submitted 2026-10-04 15:39 UTC · v1

Abstract

The PPAD-completeness of computing Nash equilibria in bimatrix games has driven extensive research into polynomial-time algorithms for $ε$-approximate Nash equilibria. Determining the strongest approximation guarantee achievable in polynomial time is a fundamental question in the complexity of approximate Nash equilibria. Despite sustained efforts, breaking the $1/3$ barrier has long been regarded as a difficult open problem. In this paper, we give an affirmative answer by proposing a simple, symmetric deterministic polynomial-time algorithm that has no tunable hyperparameters and achieves an approximation guarantee of approximately $0.30954+δ$. The main idea is to enrich the optimization framework of Tsaknakis and Spirakis with building blocks drawn from our work on strategy mixing and automated approximation analysis, yielding a new algorithmic structure that provides a conceptual explanation for the improved guarantee.

Closest papers

Nearest neighbours by meaning across the whole index.

Breaking the 1/3 Barrier for Approximate Nash Equilibria in Symmetric Bimatrix Games

cs.GT cs.LG ·2026-10-18 ·Ashkan Soleymani, Patrick Jaillet, Gabriele Farina
published similarity 0.88
Abstract · ACM-SIAM Symposium on Discrete Algorithms (SODA), 2027

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].

0.14

On Existence and Computational Complexity of Quasi-strict Equilibria

cs.GT ·2026-11-04 ·Kristoffer Arnsfelt Hansen, Xinhao Nie
similarity 0.75
Abstract

Quasi-strict Nash equilibrium, introduced by Harsanyi in 1973, is the Nash equilibrium refinement that requires every pure best response to be played with positive probability. Norde established that any bimatrix game admits a quasi-strict Nash equilibrium. We give a substantially simpler proof of this result that in particular avoids an intricate limit argument used in the final step of the proof by Norde. Our existence proof allows us to positively resolve the outstanding open question of PPAD membership of the problem of computing a quasi-strict Nash equilibrium, thereby settling its precise complexity. In games with three or more players, a quasi-strict Nash equilibrium is not guaranteed to exist, leading to the natural problem of deciding the existence of a quasi-strict Nash equilibrium in a given strategic form game. We show that this problem is $\exists\mathbb{R}$-complete, strengthening a previous NP-hardness result.

0.07

Breaking the One-Player Extension Barrier: History-Aware Repair for Multiplayer Approximate Nash Equilibria

cs.GT ·2026-11-04 ·Jinqi Tang, Shihong Ding, Cong Fang
similarity 0.69
Abstract

Computation of Nash equilibria is a central problem in algorithmic game theory, yet exact equilibrium computation is $\mathsf{PPAD}$-complete even for two-player games. This hardness motivates the study of polynomial-time algorithms for approximate Nash equilibria. While substantial progress has been made for two-player and three-player games, existing algorithms for general $m$-player games have largely relied on repeatedly applying one-player extension starting from improved fixed-player algorithms. Such improvements can at best strengthen the classical $1-1/m$ guarantee to $1-1/(m-c)$, for some constant $c$ independent of $m$. We break this long-standing barrier by developing an iterative algorithm that directly tackles general $m$-player games and achieves a $(1-(σ_{\star}-ε)/m)$-approximation for fixed $ε> 0$ and sufficiently large $m$, where $σ_\star\approx1.5867$ is the unique root in $(1,2)$ of $σ_\star^3-19σ_\star^2+27σ_\star+1=0$. Our approach rests on a novel iterative descent-and-repair framework that allows multiple rounds of repair. At the heart of our analysis is a new potential function inspired by continuous-time dynamics, which certifies progress across iterations and ensures polynomial-time termination. Our results highlight the power of history-aware, iterative repair in breaking approximation barriers for multiplayer games.

0.13

Hardness Amplification for Approximate Nash Equilibrium with Constantly Many Players

cs.GT cs.CC ·2026-10-19 ·Xiaotie Deng, Ningyuan Li, Zihe Wang, Jie Zhang
similarity 0.67
Abstract

For every fixed integer $k\ge2$ and fixed parameters $δ,\varepsilon\in(0,1)$ and $η\in[0,1)$, we give a deterministic polynomial-time reduction from finding a $δ$-approximate Nash equilibrium ($δ$-ANE) in a $k$-player game $G$ with payoffs in $[0,1]$ to finding an $(\varepsilon,η)$-weak approximate Nash equilibrium (weak ANE) in a game $H$ with $C$ players, where $C$ depends only on $k,δ,\varepsilon,η$, independently of the action-set sizes. The constructed game is symmetric with binary payoffs. The games and strategies are represented by complete payoff tables and probabilities, with rational entries encoded in binary. Consequently, the existence of deterministic polynomial-time weak-ANE algorithms at one fixed pair of parameters $\varepsilon\in(0,1),η\in[0,1)$ for every fixed number of players would give deterministic polynomial-time $δ$-ANE algorithms at every fixed approximation parameter $δ\in(0,1)$ and number of players. Under deterministic PPAD-ETH, combining our reduction with Rubinstein's hardness result (FOCS 2016) for bimatrix games at some fixed approximation parameter $γ_0\in(0,1)$ rules out a deterministic algorithm for $(\varepsilon,η)$-weak ANE with running time $N^{O((\log N)^{1-ξ})}$ for any fixed $ξ\in(0,1)$. This holds for every fixed $\varepsilon\in(0,1)$ and $η\in[0,1)$ at a suitable constant number $C$ of players, where $N$ is the binary encoding length of the constructed game's complete payoff table.

0.33

On the Role of Geometry in Solving Variational Inequalities

cs.CC cs.GTmath.OC ·2026-11-03 ·Ioannis Anagnostides, Ioannis Panageas, Jingming Yan
similarity 0.66
Abstract

The geometry of constraints in variational inequalities (VIs) plays a central role in applications ranging from resource allocation and equilibrium computation to constrained optimization. Yet, its effect on computational complexity has received surprisingly little attention beyond special cases. We examine this question when the constraint set is an $\ell_p$ ball. This family of problems encompasses two of the most extensively studied classes of problems in algorithmic game theory: symmetric bimatrix games for $p = 1$ and multi-player polymatrix games for $p = \infty$. Both of these problems are known to be PPAD-complete even for affine operators. We establish a comprehensive complexity landscape for VIs over $\ell_p$ balls across the full range $p\in[1,\infty]$. First, for any $p\neq 2$, we show that finding an inverse-polynomial approximate VI solution is PPAD-complete even for affine operators. In contrast, for $p=2$, we give a polynomial-time algorithm for affine VIs, extending a classic result of Ye (1992) beyond symmetric operators. On the other hand, once the operator becomes quadratic, we establish PPAD-completeness even at inverse polynomial precision. From a technical standpoint, we develop a new toolkit for exploiting the geometry of the constraint set and the structure of the operator to characterize the complexity of equilibrium and optimization problems, which is of independent interest.

0.28

The Complexity of Exact and Approximate Nash Equilibria in Anonymous Games

cs.GT ·2026-10-12 ·Zhengyang Liu
theory similarity 0.65
Abstract · 48 pages, including appendices and references; 2 figures and 4 tables

We prove that, for every fixed rational $c>0$, computing a $2^{-n^c}$-approximate Nash equilibrium in an $n$-player two-strategy anonymous game is $\mathsf{PPAD}$-complete. This holds even when one strategy always pays $1/2$ and, for all but two players, the other is constant outside at most five opponent counts. The reduction uses coefficient estimates to simulate circuit constraints approximately. Exact computation requires eliminating the simulation error: with three strategies, a separate construction uses polynomial roots to implement circuit gates exactly. This yields $\mathsf{FIXP}$-completeness of exact equilibrium computation under separable-linear reductions and $\mathsf{FIXP}_a$-completeness of approximation in distance to an exact equilibrium.

0.15

CLS Hardness of 2D Min-Max Optimization with Product Constraints

cs.GT cs.CC ·2026-10-13 ·Alkis Kalavasis, Panagiotis Patsilinakos, Stratis Skoulakis, Manolis Zampetakis
theory similarity 0.65
Abstract

We study the complexity of computing approximate first-order Nash equilibria in min-max optimization problems with one dimensional min and max players and product constraints. For black-box access to the objective, we prove that any algorithm requires $Ω(1/\sqrtε)$ queries to find an $ε$-first-order Nash point. In the white-box setting, we establish CLS-hardness by reducing from End-of-Potential-Line. These results show that even the simplest min-max setting with one dimensional min and max players is at least as hard as CLS and therefore does not admit polynomial-time algorithms unless $\mathsf{CLS}\subseteq \mathsf{P}$.

0.17

The Fine-Grained Complexity of Approximate Nash Equilibrium and Free Games

cs.GT cs.CC ·2026-09-07 ·Noah Golowich
theory similarity 0.65
Abstract

We study the fine-grained complexity of computing approximate Nash equilibria and approximating the value of free games in the regime where the approximation error vanishes. Under the PCP for PPAD and ETH for PPAD conjectures, we show that computing $\varepsilon$-approximate Nash equilibria in 2-player $N$-action normal-form games requires time $N^{(\log(N)/\varepsilon^2)^{1-o(1)}}$, thus showing that the classical Lipton-Markakis-Mehta algorithm (2003) is optimal through all regimes of $\varepsilon = ω(1/\sqrt{N})$. While such optimality was known in the constant-$\varepsilon$ regime (Rubinstein, 2016), previous work could only rule out significantly smaller running times of $N^{O(\log(N)/\varepsilon)}$ in the regime $\varepsilon = o(1)$. Using similar techniques, we then establish an analogous tight lower bound of $N^{(\log(N)/\varepsilon^2)^{1-o(1)}}$ under ETH for $\varepsilon$-additive value estimation in free games, when $\varepsilon \geq 2^{-o(\sqrt{\log N})}$, answering a question of Aaronson, Impagliazzo, and Moshkovitz (2014).

0.49