# A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games

arXiv: https://arxiv.org/abs/2204.11525 · HTML: https://mlsanity.com/paper/2204.11525/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Apr 2022.

## Built on by (most cited first, 5 of 5)

- [A Survey of Decision Making in Adversarial Games](https://mlsanity.com/paper/2207.07971/) (2022)
- [Are Equivariant Equilibrium Approximators Beneficial?](https://mlsanity.com/paper/2301.11481/) (2023)
- [Approximating Nash Equilibria in General-Sum Games via Meta-Learning](https://mlsanity.com/paper/2504.18868/) (2025)
- [Discovering Expert-Level Nash Equilibrium Algorithms with Large Language Models](https://mlsanity.com/paper/2508.11874/) (2025)
- [The Search-and-Mix Paradigm in Approximate Nash Equilibrium Algorithms](https://mlsanity.com/paper/2310.08066/) (2023)

## Abstract (arXiv)

Since the celebrated PPAD-completeness result for Nash equilibria in bimatrix games, a long line of research has focused on polynomial-time algorithms that compute varepsilon-approximate Nash equilibria. Finding the best possible approximation guarantee that we can have in polynomial time has been a fundamental and non-trivial pursuit on settling the complexity of approximate equilibria. Despite a significant amount of effort, the algorithm of Tsaknakis and Spirakis, with an approximation guarantee of (0.3393+δ), remains the state of the art over the last 15 years. In this paper, we propose a new refinement of the Tsaknakis-Spirakis algorithm, resulting in a polynomial-time algorithm that computes a (frac13+δ)-Nash equilibrium, for any constant δ>0. The main idea of our approach is to go beyond the use of convex combinations of primal and dual strategies, as defined in the optimization framework of Tsaknakis and Spirakis, and enrich the pool of strategies from which we build the strategy profiles that we output in certain bottleneck cases of the algorithm.