CS Paper Radar

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

Ashkan Soleymani, Patrick Jaillet, Gabriele Farina

cs.GT cs.LG ·submitted 2026-10-18 20:37 UTC · v1
published

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

Comment
ACM-SIAM Symposium on Discrete Algorithms (SODA), 2027

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.GT cs.DM ·2026-10-04 ·Dongchen Li, Hanyu Li
similarity 0.88
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.

0.49

On Existence and Computational Complexity of Quasi-strict Equilibria

cs.GT ·2026-11-04 ·Kristoffer Arnsfelt Hansen, Xinhao Nie
similarity 0.73
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.66
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

Average-and Last-Iterate Lower Bounds for Optimistic Matrix Mirror-Prox in Quantum Zero-Sum Games

cs.GT quant-phcs.LGmath.OC ·2026-09-30 ·Yiheng Su, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Pucheng Xiong
theory similarity 0.63
Abstract · 38 pages, 6 figures

Optimistic matrix mirror-prox (OMMP) computes $ε$-approximate Nash equilibria in quantum zero-sum games with an $O(1/\varepsilon)$ average-iterate guarantee [arXiv:2311.10859]. We investigate whether this dependence on accuracy is tight and whether geometric last-iterate convergence can be guaranteed. We study these questions through explicit games with one qubit per player. First, we prove an $Ω(1/\varepsilon)$ lower bound for the uniform-average output that includes the maximally mixed initial state, independently of the regularizer and step size. Second, we construct a fixed game on which optimistic gradient descent-ascent (OGDA), initialized at the maximally mixed state, has last-iterate Frobenius distance to equilibrium $Θ(1/t)$ and duality gap $Θ(1/t^3)$ for every sufficiently small fixed step size. A separate fixed game exhibits arbitrarily long delays in reducing the initial error by a constant factor across a family of initial states. Finally, we give a fixed game with a unique, strictly complementary equilibrium on which optimistic matrix multiplicative weights updates (OMMWU) converge only polynomially from the maximally mixed state for every fixed positive step size. The last-iterate Frobenius distance and quantum relative entropy from the equilibrium to the iterates decay as $Θ(1/t)$, while the duality gap decays as $Θ(1/t^2)$.

0.26

Equilibrium Numbers in Non-Square Bimatrix Games

cs.GT math.CO ·2026-09-21 ·Constantin Ickstadt, Thorsten Theobald, Bernhard von Stengel
theory similarity 0.63
Abstract · 32 pages

Bimatrix games may have an exponential number of mixed Nash equilibria if both dimensions of the game are allowed to grow. Bounds on their maximal number give structural insights that have been used to construct hard-to-solve games. We show new sharp or asymptotically sharp bounds on the (polynomial) number of equilibria for generic games where one dimension of the game is fixed and the number of strategies of the other player grows. These results go beyond the hitherto studied square games. Our methods employ combinatorial properties of polytopes, and recent obstructions that relate to the graph of those polytopes. For $n\ge5$, we construct $3\times n$ games that have all $2n+1$ vertices of the best-response polytope as equilibrium strategies, proved using a simple case of the 4-color theorem for planar graphs. Generic $4\times 5$ games are shown to have at most 17 equilibria, using computer calculations with existing datasets for all combinatorial types of the relevant polytopes. For $d\times n$ games, we construct games where all but a fraction of $O(1/n)$ of the maximum number of vertices are equilibrium strategies.

0.29

Arbitrarily Slow Polynomial Convergence of Fictitious Play

cs.GT ·2026-10-06 ·Jacob Abernethy, John Lazarsfeld, Andre Wibisono
similarity 0.62
Abstract

We show that fictitious play can converge at arbitrarily slow polynomial rates in two-player zero-sum games. For every integer $k \ge 2$, we construct a payoff matrix with $(k+1)^2 - 5$ actions per player for which the duality gap of the empirical strategies decays as $Θ(t^{-1/k})$ after $t$ steps. The family starts from the standard rock-paper-scissors matrix, with each higher-order game constructed recursively from the preceding one. After a prescribed common initial action, every subsequent best response under fictitious play is unique. For $k \ge 3$, these games give counterexamples to Karlin's conjectured $O(t^{-1/2})$ convergence rate, and they extend the recent $Θ(t^{-1/3})$ construction of Wang (2025) to arbitrarily slow polynomial rates.

0.42

Finding a Positive Index Nash Equilibrium is PPADS-Complete

cs.CC cs.GT ·2026-09-20 ·Andreas Kontogiannis, Ioannis Panageas, Vasilis Pollatos, Jingming Yan
theory similarity 0.62
Abstract · This version simplifies Section 4 using a two-dimensional embedding based on the construction of Chen and Deng (2009)

Every nondegenerate bimatrix game has a Nash equilibrium of Shapley index +1, since all equilibria are isolated, have index +1 or -1, and their indices sum to +1. We prove that the following promise search problem is PPADS-complete: given a rational bimatrix game promised to be nondegenerate, find an exact Nash equilibrium of index +1. The nondegeneracy promise can be removed if nonregular equilibria are also accepted: finding either a regular Nash equilibrium of index +1 or a nonregular Nash equilibrium in an arbitrary rational bimatrix game is also PPADS-complete. To our knowledge, this is the first PPADS-complete equilibrium search problem whose instances are explicit rational normal form payoff matrices, rather than succinct circuits or Turing machines, and thereby addresses an open question posed by Daskalakis [2019].

0.26

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