PaperfootJoin free
arXiv

Algorithm improves a guarantee for two-player game strategies

The algorithm guaranteed error of approximately 0.30954, with an additional term, improving on the longstanding one-third barrier.

Paper by Dongchen Li, Hanyu Li
Preprint: method

Edited by Boris Djordjevic · Paperfoot

Paper

The paper introduced an algorithm for approximate Nash equilibria in bimatrix games, where two players’ payoffs are listed in two tables. These equilibria limit how much either player can gain by changing strategy alone. The algorithm used no random choices or tunable settings. Its running time had a polynomial bound, meaning a bound expressed through fixed powers of the input size.

The algorithm guaranteed an approximation error of about 0.30954 plus delta, crossing the longstanding one-third barrier. Lower error means less incentive for either player to change strategy alone. The method expanded an earlier optimization framework by Tsaknakis and Spirakis. It incorporated techniques for mixing strategies and automatically analyzing approximation guarantees.

Why it matters

The theoretical guarantee addressed a longstanding open question: whether an algorithm with polynomial running time could cross the one-third approximation barrier for these games.

Caveats

The abstract reports a theoretical guarantee for bimatrix games, not practical running-time measurements. It does not define delta, and the paper is an arXiv preprint.

In this paper

approximate Nash equilibria in bimatrix games

Methods
optimization framework of Tsaknakis and Spirakis

Results

optimization framework of Tsaknakis and Spirakis, approximation guarantee: approximately 0.30954+δ

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+δ.

Abstract

What it shows

The proposed simple, symmetric deterministic polynomial-time algorithm has no tunable hyperparameters and achieves an approximation guarantee of approximately 0.30954+δ for approximate Nash equilibria in bimatrix games.

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+δ.

Abstract

Quoted word for word from the abstract on arXiv.

The paper

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

Dongchen Li, Hanyu Li

arXiv, Oct 4, 2026, Open access, Preprint, not peer-reviewed

doi.org/10.48550/arxiv.2610.05317

arXiv:2610.05317v1 in cs.GT, also cs.DM

AbstractPDFHTML

Cite as BibTeX
@misc{li2026simple,
  title = {A Simple Algorithm Breaking the 1/3 Barrier for Approximate Nash Equilibria in Bimatrix Games},
  author = {Li, Dongchen and Li, Hanyu},
  year = {2026},
  eprint = {2610.05317},
  archivePrefix = {arXiv},
  primaryClass = {cs.GT},
  doi = {10.48550/arxiv.2610.05317},
  url = {https://arxiv.org/abs/2610.05317}
}

Related