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

Davit Gondauri

Papers from arXiv.org

Abstract: 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.

Date: 2026-09
New Economics Papers: this item is included in nep-gth
References: Add references at CitEc
Citations:

Downloads: (external link)
https://arxiv.org/pdf/2609.33471 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2609.33471

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().