arXiv · Oct 4, 2026
A Simple Algorithm Breaking the 1/3 Barrier for Approximate Nash Equilibria in Bimatrix Games
By Dongchen Li, Hanyu Li
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.