A Deterministic (0.3092 + δ)-Approximation Algorithm for Bimatrix Games: A Refined Guarantee of 0.30919 + δ

This work develops a deterministic algorithm for computing approximate Nash equilibria in two-player bimatrix games with rational payoffs normalized to [0,1]. For every positive rational δ, the algorithm achieves an additive approximation guarantee of 0.30919 + δ, refining the preceding 0.3092 + δ bound. Its running time is polynomial in the game dimensions, the rational input length, and 1/δ. The principal contribution is a six-candidate construction that extends the Li–Li stationarity-and-mixing framework through an additional candidate formed from cross-round linear-programming dual mixtures. The analysis retains enlarged near-best-response sets and explicitly propagates their approximation deficits. Fixed-side optimization, rectangle mixing, and joint scalar constraints connect the algorithm’s outputs to a finite system of necessary failure inequalities. A refined global exclusion establishes the improved guarantee through exact rational arithmetic, using a reproducible partition tree containing 850,267 nodes and 425,134 terminal leaves. The manuscript integrates the approximation analysis with proofs of algorithmic correctness and polynomial bit complexity. The accompanying research package provides source code, verification programs, exact arithmetic records, experimental data, and file manifests, enabling the computational components of the argument to be reproduced and inspected. The experimental study separately examines games of sizes 100 × 100, 200 × 200, 500 × 500, and 1000 × 1000. Across 24 executions on 12 distinct games, 22 runs were completed within the specified 45-second computational limit. All six executions on the three 1000 × 1000 instances completed, with a median core runtime of approximately 30.77 seconds and maximum observed regret below 0.003082 at δ = 0.01. Two executions on one 200 × 200 instance reached the time limit. Runtime, memory consumption, optimization workload, and regret are reported together to characterize performance under the stated experimental conditions. Additional experiments compare the six-candidate method with a specification-based reconstruction of the Tsaknakis–Spirakis algorithm under a common approximation target. Exact examples establish that the sixth candidate can strictly improve on the first five candidates at the same terminal profile. A separate block-lifting analysis identifies transformations that preserve regret and supports structured scalability experiments. Together, the theoretical results and reproducible experiments advance approximation methods for general-sum bimatrix games by combining a refined universal guarantee, an explicit implementation framework, and a systematic analysis of computational performance.