A Deterministic (0.3092 + δ)-Approximation Algorithm for Bimatrix Games: A Certified Refinement to 0.30919 + δ

We develop a deterministic approximation algorithm for rational bimatrix games with payoffs in [0, 1] and prove a universal (0.30919 + δ)-approximate Nash equilibrium guarantee, for every rational δ > 0, with bit complexity polynomial in the input length and 1/δ. The result refines the algorithm's original 0.3092 + δ bound without changing its six-candidate construction. The method retains one enlarged stationary dual certificate, solves four fixed-side linear programs in two rounds, searches a rational strategy rectangle, and evaluates a joint cross-round candidate. A same-execution reduction preserves all five retained dual masses. New guarded discriminant and supporting inequalities permit a complete global exclusion at the exact rational threshold 30919/100000. A separate integer interval implementation accepts all 850,267 records, including every contraction and closed subdivision, with no unresolved region. Exact general-sum examples establish that the sixth candidate can improve on the entire continuous stationary rectangle. Full certified executions complete 22 of 24 scheduled trials at sizes 100, 200, 500, and 1000, including all six 1000 × 1000 trials; their median core time is 30.771 seconds. Two repetitions of one 200×200 input remain censored. An explicit finite-accuracy reconstruction of Tsaknakis-Spirakis, with a proved error ledger, supports 52 certified comparisons at a common guaranteed target. The archive contains the proof trees, independent checkers, protocols, and exact execution records. Exact game worst-case sharpness and uniform practical throughput remain open.