 A One-Saddle 1/5 Approximation Algorithm for Common-Kernel Bimatrix Games: Recognition, Exact Segment Optimization, Sharp Selector Bounds, and Certified RobustnessDavit Gondauri EconStor Preprints from ZBW - Leibniz Information Centre for Economics Abstract: This paper develops an algorithmic, structural, and certification theory for a fixed-normalization class of symmetric bimatrix games generated by a common kernel. The class arose from a broader investigation of approximation-threshold reductions for bimatrix Nash equilibria, but the principal results are unconditional and form an independent structured-game approximation framework. The central result is a polynomial-time algorithm that computes a rational \(1/5\)-approximate Nash equilibrium for every rational game in the common-kernel class using a single auxiliary zero-sum saddle problem. The saddle value yields two complementary symmetric regret bounds, \(v/3\) and \((1-v)/2\), whose crossing at \(v=3/5\) gives the \(1/5\) guarantee. The constant is proved tight for the stated endpoint-selection policy, but is not claimed to be the optimal approximation constant attainable by all polynomial-time algorithms on the class. The paper further develops an exact polynomial-time post-processing procedure, Segment-Optimize, for any selected optimal saddle pair. It minimizes regret exactly along the segment joining the row-maximin and column-minimizing strategies by exploiting the piecewise-affine best-response envelope and the resulting piecewise-quadratic regret function. This optimization can strictly improve the endpoint solution while preserving the same worst-case \(1/5\) guarantee. The dependence of this post-processing step on the selected saddle pair is made explicit. The common-kernel representation is fully algorithmic. The paper gives an exact recognition procedure, proves uniqueness of kernel recovery, and characterizes the class as an affine image of the kernel cube. A symmetric/antisymmetric decomposition explains the structural origin of the factor-three directional matrix used by the saddle algorithm. The paper also proves that every normalized symmetric bimatrix game has a positive-affine representative in the common-kernel class, while carefully tracking the resulting factor-three rescaling of additive regret. Consequently, the \(1/5\) result is a fixed-normalization theorem and is not a scale-invariant \(1/5\) approximation result for arbitrary symmetric games. Exact symmetric-equilibrium computation nevertheless remains PPAD-hard within the class. For arbitrary square rational games, the theory extends beyond exact membership through a nearest-class projection in the entrywise maximum norm. The projection is formulated as a rational linear program and is accompanied by an explicit dual representation, yielding a directly checkable primal-dual optimality certificate. Combining the nearest common-kernel representative with the saddle algorithm gives a certified \((1/5+2\eta^\*)\)-approximate equilibrium, where \(\eta^\*\) is the exact projection distance. An a posteriori certificate is also provided for arbitrary feasible approximate kernels and exactly evaluated candidate profiles. A separate sharp selector theorem analyzes the declared full-subset selector family. It proves the exact optimal regret-to-uniformity coefficient \(3-1/q\) and provides a matching construction. The result is explicitly limited to the full-subset representation and is not asserted to transfer automatically to compressed or restricted selector families. The reduction-theoretic consequences are deliberately isolated from the unconditional approximation theory. Under an explicit parameter-controlled fine-grained source-hardness premise, the paper derives conditional exclusions for threshold-bridge compilers whose outputs lie in the common-kernel class or in a sufficiently small certified neighborhood of it. Additional structural diagnostics show that diffuse semantic validity need not force a heavy decodable witness and that a semantic high region cannot simultaneously be nonempty, uniformly subexponentially searchable, and guaranteed to decode to a valid source solution. These statements are local design constraints for reduction architectures, not a solution of the general deterministic \(1/3\)-approximation-threshold problem. The paper provides four explicit computational procedures: Recognize-and-Recover, Common-Kernel Saddle Solver, Segment-Optimize, and Project-and-Solve. The reproducibility package separates exact finite-instance verification from floating-point numerical consistency checks. In particular, an exhaustive exact audit covers all \(65{,}536\) binary \(4\times4\) kernels, with zero missing saddle certificates, zero branch-bound failures, and zero selected-\(1/5\)-bound failures. A separate exact-rational Segment-Optimize audit covers all 528 binary kernels in dimensions \(m=2,3\), verifying breakpoint, active-envelope, stationary-point, interval-membership, endpoint-comparison, and nonnegative-regret conditions. Overall, the paper contributes a unified structured-game framework combining polynomial-time approximation, exact recognition and kernel recovery, affine geometry, exact segment optimization, robust nearest-class projection, primal-dual certification, sharp selector calibration, and carefully delimited conditional implications for Nash-equilibrium reduction design. It does not claim to resolve the global deterministic approximation-threshold problem; rather, it identifies and fully analyzes a tractable and certifiable common-kernel regime. Keywords: Approximate Nash Equilibrium; Bimatrix Games; Symmetric Games; Common-Kernel Games; Algorithmic Game Theory; Computational Game Theory; Polynomial-Time Algorithms; Zero-Sum Games; Minimax; Linear Programming; Regret; Exact Recognition; Kernel Recovery; Segment Optimization; Robustness Certification; Primal-Dual Certification; Selector Games; PPAD; Computational Complexity; Hardness Reductions (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:zbw:esprep:344034 Access Statistics for this paper More papers in EconStor Preprints from ZBW - Leibniz Information Centre for Economics Contact information at EDIRC. |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.