cs.GTOct 18, 2026

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

Authors: Ashkan Soleymani, Patrick Jaillet, Gabriele Farina

Organizations: MIT

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

We give the first unconditional family of polynomial-time algorithms that breaks the 1/31/3 approximation barrier for symmetric bimatrix games. For every fixed δ>0δ>0, an algorithm in this family computes a symmetric (1−1/2+δ)(1-1/\sqrt{2}+δ)-approximate Nash equilibrium, improving on the previous best guarantee of (1/3+δ)(1/3+δ) due to Kontogiannis and Spirakis [2011].

Figures & tables

 v=min⁡x∈Δnmax⁡(i,j)∈[n]2∑kxk(Aik−Akj)=max⁡σ∈Δn2min⁡k∈[n]∑i,jσij(Aik−Akj).\displaystyle v=\min_{x\in\Delta_{n}}\max_{(i,j)\in[n]^{2}}\sum_{k}x_{k}(A_{ik}-A_{kj})=\max_{\sigma\in\Delta_{n^{2}}}\min_{k\in[n]}\sum_{i,j}\sigma_{ij}(A_{ik}-A_{kj}). 
Algorithm 1 Saddle-Gap Algorithm with Single Repair
 v=min⁡x∈Δnmax⁡(i,j)∈[n]2∑kxk(Aik−Akj)=max⁡σ∈Δn2min⁡k∈[n]∑i,jσij(Aik−Akj).\displaystyle v=\min_{x\in\Delta_{n}}\max_{(i,j)\in[n]^{2}}\sum_{k}x_{k}(A_{ik}-A_{kj})=\max_{\sigma\in\Delta_{n^{2}}}\min_{k\in[n]}\sum_{i,j}\sigma_{ij}(A_{ik}-A_{kj}). 
Algorithm 2 Saddle-Gap Algorithm with Amortized Repairs
More in this topic

Game Theory

Game theory studies how interacting decision-makers choose strategies, form agreements, and shape outcomes under competition and cooperation.

See all 236 papers

Explore similar work

CardsList

  1. Quadratic Programming Approach for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games

    Sep 30, 2025Sam GanzfriedNash EquilibriumImperfect-Information Games

    Ganzfried Research

  2. Variable Bound Tightening for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games

    Jun 24, 2026Sam GanzfriedNash EquilibriumBranch and Bound

    Ganzfried Research, Cornell University

  3. Projected Exploitability Descent for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games

    Jun 28, 2026Sam GanzfriedImperfect-Information GamesGradient Descent

    Ganzfried Research, Cornell University