{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,23]],"date-time":"2026-03-23T17:26:23Z","timestamp":1774286783860,"version":"3.50.1"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,8,8]],"date-time":"2023-08-08T00:00:00Z","timestamp":1691452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,10,31]]},"abstract":"<jats:p>\n            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 \u03b5-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 [\n            <jats:xref ref-type=\"bibr\">38<\/jats:xref>\n            ], with an approximation guarantee of (0.3393+\u03b4), 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\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\((\\frac{1}{3}+\\delta)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -Nash equilibrium, for any constant \u03b4 &gt; 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 [\n            <jats:xref ref-type=\"bibr\">38<\/jats:xref>\n            ], and enrich the pool of strategies from which we build the strategy profiles that we output in certain bottleneck cases of the algorithm.\n          <\/jats:p>","DOI":"10.1145\/3606697","type":"journal-article","created":{"date-parts":[[2023,7,8]],"date-time":"2023-07-08T11:32:58Z","timestamp":1688815978000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["A Polynomial-Time Algorithm\u00a0for 1\/3-Approximate Nash Equilibria in Bimatrix Games"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6513-6748","authenticated-orcid":false,"given":"Argyrios","family":"Deligkas","sequence":"first","affiliation":[{"name":"Royal Holloway University of London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1870-3444","authenticated-orcid":false,"given":"Michail","family":"Fasoulakis","sequence":"additional","affiliation":[{"name":"Foundation for Research and Technology-Hellas (FORTH), Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1855-141X","authenticated-orcid":false,"given":"Evangelos","family":"Markakis","sequence":"additional","affiliation":[{"name":"Athens University of Economics and Business, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,8,8]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993664"},{"key":"e_1_3_2_3_2","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/978-3-642-22935-0_2","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Austrin Per","year":"2011","unstructured":"Per Austrin, Mark Braverman, and Eden Chlamt\u00e1\u010d. 2011. Inapproximability of NP-complete variants of Nash equilibrium. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer, 13\u201325."},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2016.0794"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.5555\/1315958.1315964"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1050574"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00034"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.09.023"},{"key":"e_1_3_2_9_2","first-page":"970","volume-title":"Proceedings of SODA","author":"Braverman Mark","year":"2015","unstructured":"Mark Braverman, Young Kun-Ko, and Omri Weinstein. 2015. Approximating the best Nash equilibrium in n \\({}^{\\mbox{o}}\\) \\({}^{{(\\log {n})}}\\) -time breaks the exponential time hypothesis. In Proceedings of SODA. SIAM, 970\u2013982."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/11944874_24"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516516"},{"key":"e_1_3_2_12_2","first-page":"159","volume-title":"Proceedings of SODA","volume":"7","author":"Chen Xi","year":"2007","unstructured":"Xi Chen, Shang-Hua Teng, and Paul Valiant. 2007. The approximation complexity of win-lose games. In Proceedings of SODA, Vol. 7. 159\u2013168."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-85947-3_7"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.5555\/1073673.1710922"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0465-y"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44803-8_21"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132527"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/1250910.1250962"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.031"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch146"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2021.11.002"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2018.06.001"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0078-7"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0029-3"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00199-009-0436-2"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/11944874_26"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9227-6"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20662-7_1"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188892"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/779928.779933"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v32i1.11439"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2009.08.003"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2009.10.003"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1032338"},{"key":"e_1_3_2_35_2","first-page":"887","volume-title":"Proceedings of AAMAS","author":"Murhekar Aniket","year":"2020","unstructured":"Aniket Murhekar and Ruta Mehta. 2020. Approximate Nash equilibria of imitation games: Algorithms and complexity. In Proceedings of AAMAS. 887\u2013894."},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.2307\/1969529"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-013-9446-3"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.35"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2008.10129172"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3606697","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3606697","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:51Z","timestamp":1750182531000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3606697"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,8]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,10,31]]}},"alternative-id":["10.1145\/3606697"],"URL":"https:\/\/doi.org\/10.1145\/3606697","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8,8]]},"assertion":[{"value":"2022-09-28","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-06-15","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-08-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}