A Deterministic (0.3092 + δ)-Approximation Algorithm for Bimatrix Games

This manuscript presents a deterministic algorithm for computing a (0.3092 + δ)-approximate Nash equilibrium in every two-player rational bimatrix game with payoffs in [0, 1], for every rational δ > 0. Its running time is polynomial in the total binary input length and 1/δ. The approximation threshold is the exact rational constant 773/2500, yielding a guarantee strictly below one third whenever 0 < δ < 181/7500. Building on the stationary-descent and fixed-side mixing framework of Li and Li, the construction combines one approximate stationary profile, four exact linear programs, an explicit rational rectangle search, and an additional strategy profile formed from the retained dual outputs of two successive mixing rounds. The analysis derives necessary failure conditions from a single algorithm execution, retaining all five dual weights and explicitly accounting for near-best-response errors, deterministic choices, and degenerate cases. The proof combines mathematical derivations with a finite exact interval calculation that excludes the resulting five-variable failure system over its full parameter domain. The documented replay checks all 238,705 records of a closed domain partition using arbitrary-precision integer arithmetic and outward rounding. Exact player-exchange identities cover both regret branches. The manuscript provides the failure reduction, stationary-value projection, soundness arguments for the computational rules, and polynomial bit-complexity analysis, with the stationary-descent theorem identified as an explicit literature dependency. A smaller numerical candidate, approximately 0.309143346402673, is discussed as an exploratory result. Its global optimality and realization as an algorithmic worst-case game remain open; the approximation guarantee established in the manuscript is 0.3092 + δ.