A Deterministic 0.3092 + δ Approximation for Bimatrix Games: Six Candidates and Exact Global Certification
Davit Gondauri
Abstract
Gondauri’s earlier Zenodo preprint [1] reported a deterministic approximation guarantee of \(1/3 - 7.5 \times 10^{-45}\), strictly below one third. Li and Li [2] acknowledge that correspondence concerning this preprint motivated their independently developed construction, which achieves an approximation constant of approximately \(0.30954\). The present paper improves this guarantee by introducing a sixth candidate formed from a pair of cross-round dual mixtures. Universal LP-dual inequalities bound the best-response payoffs against these mixtures, while bilinearity combines four corner payoff bounds. We prove that, for every normalized bimatrix game with rational payoffs and every rational \(\delta>0\), the resulting six-candidate algorithm returns a \((0.3092+\delta)\)-approximate Nash equilibrium in polynomial time. The global guarantee follows from the infeasibility of the full five-dimensional system of necessary failure conditions at the exact rational threshold \(773/2500\). A finite certificate contains 238,705 nodes, 119,353 excluded leaves, and no unresolved cells. An independently implemented Python checker replays every contraction, terminal inequality, and partition using arbitrary-precision integer arithmetic and outward rational rounding. Exact symbolic identities connect the checked constraints to the game-theoretic failure projection, and exchanging the players covers both new regret branches. We specify how degenerate normalizers are handled, which dual data are retained, and how the complete finite-error budget is allocated. The numerical value \(0.309143346402673\ldots\) remains a local candidate and is not claimed to be the exact global optimum. The certificate verifies the arithmetic; the mathematical implications are presented in a human-readable proof without proof-assistant formalization.