Approximating Bimatrix Nash Equilibria: A Polynomial-Time Bound below 0.2985 and Two Guarantees at 0.28

How far can the approximation threshold for Nash equilibria be pushed while preserving deterministic computational efficiency and mathematical verifiability? This research investigates that question through three complementary approximation guarantees for general two-player bimatrix games, combining stationary-point optimization, retained linear-programming dual certificates, exact interval arithmetic, geometric support reduction, and exhaustive empirical-strategy enumeration. The central contribution is a computer-assisted polynomial-time approximation result claiming a strict worst-case regret bound below 0.2985, with the explicit threshold: ε < 2503999/8388608 = 0.29849994182586669921875. The proposed algorithm operates in arbitrary game dimensions. Its proof framework transforms the hypothetical failure of the algorithm into necessary inequalities involving dual variables obtained from the same computational execution. An outward-rounded integer verifier is then used to exclude the resulting parameter domain through eleven certified regions. The study presents two additional guarantees at the 0.28 approximation threshold: Polynomial-time guarantee for games with at most six strategies on one side: A geometric argument combining four-support best-response vertices, equilibrium probability concentration, and total-variation bounds yields maximum regret at most 7/25 = 0.28. Deterministic quasipolynomial-time guarantee for arbitrary dimensions: A constructive specialization of the classical small-support method achieves the same 7/25 = 0.28 bound through exhaustive enumeration of logarithmic-size empirical strategies. Together, these results distinguish three computational regimes and clarify the unresolved challenge of obtaining a universal deterministic polynomial-time guarantee of 0.28. A defining feature of this research is its commitment to reproducibility and proof transparency. The accompanying research dossier includes the mathematical manuscript, LaTeX sources, C++ verification code, Python diagnostic tests, eleven recorded interval-certificate regions, exact-arithmetic checks, reproducibility instructions, SHA-256 integrity records, and a dedicated Guarantee Audit Supplement. The supplement documents the examined mathematical reductions, exact-arithmetic tests, and a successful independent recomputation of one certificate region. It also identifies outstanding verification requirements: a complete independent replay of all eleven regions and an independent review of every certificate acceptance condition have not yet been completed. This work presents a proposed improvement below the 0.30 threshold for deterministic polynomial-time Nash-equilibrium approximation, alongside two analytically supported 0.28 guarantees. It provides a reproducible mathematical and computational foundation for further research in algorithmic game theory, computational complexity, and certified optimization.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-19
DOI
https://doi.org/10.5281/zenodo.24377780
Primary Topic
Game Theory and Applications
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Approximating Bimatrix Nash Equilibria: A Polynomial-Time Bound below 0.2985 and Two Guarantees at 0.28

Davit Gondauri
Zenodo (CERN European Organization for Nuclear Research)
Game Theory and Applications
preprint

Approximating Bimatrix Nash Equilibria: A Polynomial-Time Bound below 0.2985 and Two Guarantees at 0.28

Davit Gondauri
preprint en

Abstract

How far can the approximation threshold for Nash equilibria be pushed while preserving deterministic computational efficiency and mathematical verifiability? This research investigates that question through three complementary approximation guarantees for general two-player bimatrix games, combining stationary-point optimization, retained linear-programming dual certificates, exact interval arithmetic, geometric support reduction, and exhaustive empirical-strategy enumeration. The central contribution is a computer-assisted polynomial-time approximation result claiming a strict worst-case regret bound below 0.2985, with the explicit threshold: ε < 2503999/8388608 = 0.29849994182586669921875. The proposed algorithm operates in arbitrary game dimensions. Its proof framework transforms the hypothetical failure of the algorithm into necessary inequalities involving dual variables obtained from the same computational execution. An outward-rounded integer verifier is then used to exclude the resulting parameter domain through eleven certified regions. The study presents two additional guarantees at the 0.28 approximation threshold: Polynomial-time guarantee for games with at most six strategies on one side: A geometric argument combining four-support best-response vertices, equilibrium probability concentration, and total-variation bounds yields maximum regret at most 7/25 = 0.28. Deterministic quasipolynomial-time guarantee for arbitrary dimensions: A constructive specialization of the classical small-support method achieves the same 7/25 = 0.28 bound through exhaustive enumeration of logarithmic-size empirical strategies. Together, these results distinguish three computational regimes and clarify the unresolved challenge of obtaining a universal deterministic polynomial-time guarantee of 0.28. A defining feature of this research is its commitment to reproducibility and proof transparency. The accompanying research dossier includes the mathematical manuscript, LaTeX sources, C++ verification code, Python diagnostic tests, eleven recorded interval-certificate regions, exact-arithmetic checks, reproducibility instructions, SHA-256 integrity records, and a dedicated Guarantee Audit Supplement. The supplement documents the examined mathematical reductions, exact-arithmetic tests, and a successful independent recomputation of one certificate region. It also identifies outstanding verification requirements: a complete independent replay of all eleven regions and an independent review of every certificate acceptance condition have not yet been completed. This work presents a proposed improvement below the 0.30 threshold for deterministic polynomial-time Nash-equilibrium approximation, alongside two analytically supported 0.28 guarantees. It provides a reproducible mathematical and computational foundation for further research in algorithmic game theory, computational complexity, and certified optimization.

Zenodo (CERN European Organization for Nuclear Research)
Game Theory and Applications
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon