2026-08-10T13:31:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16979 2024-03-06T10:58:52Z ddc:004 open_access

A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games Deligkas, Argyrios Fasoulakis, Michail Markakis, Evangelos bimatrix games approximate Nash equilibria Since the celebrated PPAD-completeness result for Nash equilibria in bimatrix games, a long line of research has focused on polynomial-time algorithms that compute ε-approximate Nash equilibria. Finding the best possible approximation guarantee that we can have in polynomial time has been a fundamental and non-trivial pursuit on settling the complexity of approximate equilibria. Despite a significant amount of effort, the algorithm of Tsaknakis and Spirakis [Tsaknakis and Spirakis, 2008], with an approximation guarantee of (0.3393+δ), remains the state of the art over the last 15 years. In this paper, we propose a new refinement of the Tsaknakis-Spirakis algorithm, resulting in a polynomial-time algorithm that computes a (1/3+δ)-Nash equilibrium, for any constant δ > 0. The main idea of our approach is to go beyond the use of convex combinations of primal and dual strategies, as defined in the optimization framework of [Tsaknakis and Spirakis, 2008], and enrich the pool of strategies from which we build the strategy profiles that we output in certain bottleneck cases of the algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Argyrios Deligkas and Michail Fasoulakis and Evangelos Markakis 2022 Is Part Of LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2022.41 urn:nbn:de:0030-drops-169790 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.41 eng https://creativecommons.org/licenses/by/4.0/legalcode