A One-Saddle 1/5 Approximation Algorithm for Common-Kernel Bimatrix Games: Recognition, Exact Segment Optimization, Sharp Selector Bounds, and Certified Robustness

We study a fixed-normalization class of symmetric bimatrix games generated by a common kernel and show that it admits efficient approximation despite exact symmetric-equilibrium computation remaining PPAD-hard. For every rational game in the class, a single auxiliary zero-sum saddle computation yields a rational symmetric \(1/5\)-approximate Nash equilibrium in polynomial time. We also give exact recognition and unique kernel recovery, and an exact polynomial-time post-processing algorithm that minimizes regret along the segment joining the selected saddle strategies. For arbitrary rational square games, we formulate the nearest common-kernel projection as a linear program with an explicit dual certificate, obtaining a certified \((1/5+2\eta^*)\)-approximation guarantee. A separate selector result proves a sharp regret-to-uniformity constant for the full-subset construction. The results provide a tractable and certifiable structured-game regime and clarify which common-kernel reduction architectures cannot support certain fine-grained approximation-hardness objectives.