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

Davit Gondauri

EconStor Preprints from ZBW - Leibniz Information Centre for Economics

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

Keywords: approximate Nash equilibrium; bimatrix games; stationary descent; linear programming duality; exact interval certificates; computational game theory (search for similar items in EconPapers)
JEL-codes: C61 C62 C63 C72 (search for similar items in EconPapers)
Date: 2026
Note: This fourth version presents a strengthened deterministic polynomial-time approximation algorithm for Nash equilibria in rational normalized bimatrix games, refining the previously reported bound of 0.3092 + δ to 0.30919 + δ. The revision substantially expands the mathematical analysis, including the algorithmic correctness argument, polynomial bit-complexity bounds, and the game-to-scalar reduction. It also provides exact-arithmetic computational verification, reproducible proof-checking procedures, and numerical experiments on games of up to 1000 × 1000. The accompanying research package contains source code, computational data, verification scripts, and supporting documentation to facilitate independent examination and reproducibility.
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.econstor.eu/bitstream/10419/344144/1/Bimatrix_030919_arXiv.pdf (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:zbw:esprep:344144

Access Statistics for this paper

More papers in EconStor Preprints from ZBW - Leibniz Information Centre for Economics Contact information at EDIRC.
Bibliographic data for series maintained by ZBW - Leibniz Information Centre for Economics ().