A Polynomial-Time Strict-Sub-One-Third Approximation Theorem for Bimatrix Games

Abstract

This paper establishes a strict deterministic polynomial-time approximation guarantee below the one-third frontier for general two-player rational bimatrix games with payoffs normalized to the unit interval. The result addresses the long-standing upper-bound question of whether the universal worst-case approximation guarantee can be separated strictly from one third rather than merely approached from above. Building on the stationary framework of Deligkas, Fasoulakis, and Markakis, the paper introduces an enriched fixed-side completion architecture that extracts additional algorithmic information from the DFM stationary configuration. Each side is augmented by a midpoint best response, producing a three-strategy fixed-side hull over which completion is optimized. The analysis converts the DFM stationary dual certificate into pointwise pure-action inequalities, providing a direct bridge from stationary duality to fixed-anchor regret control. The proof develops a complete quantitative localization of the DFM parameter space. The difficult Case 4.2 equality-set analysis is robustified through explicit threshold-perturbed residual functions, a uniform perturbation envelope, and exact separation margins away from the critical zero sets. Noncentral high-face and asymmetric endpoint configurations are excluded using explicit derivative, denominator, and stationary bounds rather than qualitative continuity arguments. The central obstruction is resolved by a new two-point fixed-anchor completion theorem. After the direct-mixing branch fails, the construction produces a profile with regret below 0.308, eliminating the need for the earlier near-one-twelfth saturation and thirteen-fortieths cross-mixing mechanism. Together with the exhaustive parameter partition, this closes every possible obstruction to a strict improvement below one third. The resulting enriched-hull theorem establishes an explicit universal positive gap below one third at the exact candidate level. A self-contained fixed-side discretization argument then converts the structural theorem into a fully specified deterministic polynomial-time algorithm that, for every normalized rational bimatrix game, returns an approximate Nash equilibrium with a worst-case regret strictly below one third. Consequently, the deterministic polynomial-time approximation threshold is strictly smaller than one third. The significance of the result is qualitative rather than numerical: the explicit constant is deliberately nonoptimized, but its positivity establishes that one third is not a terminal deterministic polynomial-time upper-bound frontier. Beyond the final approximation constant, the paper contributes a reusable methodological framework combining stationary primal-dual certificates, enriched strategy hulls, equality-set localization, fixed-anchor completion, finite candidate extraction, rational linear programming, and controlled discretization. These mechanisms provide concrete directions for sharper approximation constants, automated theorem search, symbolic verification, computational benchmarking, and further investigation of the true approximation threshold for bimatrix Nash equilibria. The result does not determine the exact approximation threshold, establish optimality of the displayed gap, provide a matching hardness lower bound, or solve exact Nash equilibrium computation in polynomial time. Its precise contribution is the strict crossing of the one-third deterministic polynomial-time upper-bound frontier for general normalized rational bimatrix games.