A Deterministic 0.3092 + δ Approximation for Bimatrix Games: Six Candidates and Exact Global Certification

This paper establishes a deterministic polynomial-time algorithm for computing a (0.3092+\delta)-approximate Nash equilibrium in every two-player bimatrix game with rational payoffs normalized to [0,1], for any rational accuracy parameter (\delta>0). The result strengthens the approximately (0.30954+\delta) global guarantee of Dongchen Li and Hanyu Li. At the same accuracy parameter, the improvement in the guaranteed approximation bound is approximately (0.0003399654). The construction adds a sixth candidate to the existing stationarity-and-mixing framework. This candidate combines retained linear-programming dual strategies from two successive mixing rounds. Universal dual inequalities bound its best-response payoffs, while bilinearity supplies bounds on its expected payoffs. The manuscript specifies the algorithm’s behavior for degenerate normalizers, deterministic selection of compatible primal and dual data, and the complete finite-error budget. Its running time is polynomial in the input encoding length and (1/\delta). The global guarantee is supported by a complete exact exclusion certificate at the rational threshold (773/2500=0.3092). The certificate covers the full five-dimensional necessary failure system and contains 238,705 nodes and 119,353 excluded leaves, with no unresolved cells. A separately implemented checker replays every contraction, terminal inequality, and domain partition using arbitrary-precision integers and outward rational rounding. Exact symbolic identities connect the certified scalar constraints to the game-theoretic argument, and player-exchange symmetry covers both regret branches. The research continues the sequence initiated by Davit Gondauri’s earlier Zenodo preprint, which reported the strict sub-one-third guarantee (1/3-7.5\times10^{-45}). Li and Li’s subsequent paper acknowledges that correspondence concerning this preprint motivated their independently developed construction. The present work extends that construction and establishes the stronger (0.3092+\delta) global guarantee. The accompanying verification package provides the manuscript, LaTeX source, exact certificate, replay checker, symbolic verification scripts, and reproducibility information. The manuscript also investigates the sharper local numerical candidate (0.309143346402673\ldots), whose global optimality remains open. The certified result combines a reproducible exact arithmetic certificate with a human-readable mathematical proof.