Document Open Access Logo

A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games

Authors Argyrios Deligkas, Michail Fasoulakis, Evangelos Markakis

PDF
Thumbnail PDF

File

LIPIcs.ESA.2022.41.pdf
  • Filesize: 0.7 MB
  • 14 pages

Document Identifiers

Author Details

Argyrios Deligkas
  • Royal Holloway, University of London, Egham, UK
Michail Fasoulakis
  • Foundation for Research and Technology-Hellas (FORTH), Heraklion, Greece
  • Athens University of Economics and Business, Greece
Evangelos Markakis
  • Athens University of Economics and Business, Greece

Funding

  • Markakis, Evangelos: This work has been supported by the Hellenic Foundation for Research and Innovation (H.F.R.I.) under the "First Call for H.F.R.I. Research Projects to support faculty members and researchers and the procurement of high-cost research equipment" grant (Project Number: HFRI-FM17-3512).

Acknowledgements

The authors would like to thank Marcin Jurdzi{ń}ski for some initial discussions on the Tsaknakis-Spirakis algorithm.

Cite AsGet BibTex

Argyrios Deligkas, Michail Fasoulakis, and Evangelos Markakis. A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 41:1-41:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ESA.2022.41

Abstract

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Exact and approximate computation of equilibria
Keywords
  • bimatrix games
  • approximate Nash equilibria

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Bharat Adsul, Jugal Garg, Ruta Mehta, and Milind Sohoni. Rank-1 bimatrix games: a homeomorphism and a polynomial time algorithm. In Proceedings of STOC, pages 195-204, 2011. Google Scholar
  2. Per Austrin, Mark Braverman, and Eden Chlamtáč. Inapproximability of np-complete variants of Nash equilibrium. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 13-25. Springer, 2011. Google Scholar
  3. Yakov Babichenko, Siddharth Barman, and Ron Peretz. Empirical distribution of equilibrium play and its testing application. Math. Oper. Res., 42(1):15-29, 2017. Google Scholar
  4. Imre Bárány, Santosh Vempala, and Adrian Vetta. Nash equilibria in random games. Random Structures & Algorithms, 31(4):391-405, 2007. Google Scholar
  5. Siddharth Barman. Approximating Nash equilibria and dense subgraphs via an approximate version of Carathéodory’s theorem. SIAM J. Comput., 47(3):960-981, 2018. Google Scholar
  6. Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins, and Aviad Rubinstein. Smoothed complexity of 2-player Nash equilibria. In Proceedings of FOCS, pages 271-282, 2020. Google Scholar
  7. Hartwig Bosse, Jaroslaw Byrka, and Evangelos Markakis. New algorithms for approximate Nash equilibria in bimatrix games. Theoretical Computer Science, 411(1):164-173, 2010. Google Scholar
  8. Mark Braverman, Young Kun-Ko, and Omri Weinstein. Approximating the best Nash equilibrium in n^o^(log n)-time breaks the exponential time hypothesis. In Proceedings of SODA, pages 970-982. SIAM, 2015. Google Scholar
  9. Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Sparse games are hard. In Proceedings of WINE, pages 262-273, 2006. Google Scholar
  10. Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM, 56(3), 2009. Google Scholar
  11. Xi Chen, Shang-Hua Teng, and Paul Valiant. The approximation complexity of win-lose games. In Proceedings of SODA, volume 7, pages 159-168, 2007. Google Scholar
  12. Zhaohua Chen, Xiaotie Deng, Wenhan Huang, Hanyu Li, and Yuhao Li. On tightness of the Tsaknakis-Spirakis algorithm for approximate Nash equilibrium. In Proceedings of SAGT, volume 12885, pages 97-111, 2021. Google Scholar
  13. Bruno Codenotti and Daniel Štefankovič. On the computational complexity of Nash equilibria for (0,1) bimatrix games. Information Processing Letters, 94(3):145-150, 2005. Google Scholar
  14. Artur Czumaj, Argyrios Deligkas, Michail Fasoulakis, John Fearnley, Marcin Jurdziński, and Rahul Savani. Distributed methods for computing approximate equilibria. Algorithmica, 81(3):1205-1231, 2019. Google Scholar
  15. Artur Czumaj, Michail Fasoulakis, and Marcin Jurdziński. Approximate well-supported Nash equilibria in symmetric bimatrix games. In Proceedings of SAGT, volume 8768, pages 244-254, 2014. Google Scholar
  16. Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The complexity of computing a Nash equilibrium. In Proceedings of STOC, pages 71-78, 2006. Google Scholar
  17. Constantinos Daskalakis, Aranyak Mehta, and Christos Papadimitriou. Progress in approximate Nash equilibria. In Proceedings of EC, pages 355-358, 2007. Google Scholar
  18. Constantinos Daskalakis, Aranyak Mehta, and Christos Papadimitriou. A note on approximate Nash equilibria. Theoretical Computer Science, 410(17):1581-1588, 2009. Google Scholar
  19. Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos, and Paul G. Spirakis. Approximating the existential theory of the reals. J. Comput. Syst. Sci., 125:106-128, 2022. URL: https://doi.org/10.1016/j.jcss.2021.11.002.
  20. Argyrios Deligkas, John Fearnley, and Rahul Savani. Inapproximability results for constrained approximate Nash equilibria. Inf. Comput., 262:40-56, 2018. Google Scholar
  21. John Fearnley, Paul W. Goldberg, Rahul Savani, and Troels Bjerre Sørensen. Approximate well-supported Nash equilibria below two-thirds. Algorithmica, 76(2):297-319, 2016. Google Scholar
  22. Ravi Kannan and Thorsten Theobald. Games of fixed rank: A hierarchy of bimatrix games. Economic Theory, 42(1):157-173, 2010. Google Scholar
  23. Spyros C. Kontogiannis, Panagiota N. Panagopoulou, and Paul G. Spirakis. Polynomial algorithms for approximating Nash equilibria of bimatrix games. In Proceedings of WINE, pages 286-296, 2006. Google Scholar
  24. Spyros C. Kontogiannis and Paul G. Spirakis. Well supported approximate equilibria in bimatrix games. Algorithmica, 57(4):653-667, 2010. Google Scholar
  25. Spyros C. Kontogiannis and Paul G. Spirakis. Approximability of symmetric bimatrix games and related experiments. In Proceedings of SEA, volume 6630, pages 1-20, 2011. Google Scholar
  26. Pravesh K. Kothari and Ruta Mehta. Sum-of-squares meets Nash: lower bounds for finding any equilibrium. In Proceedings of STOC, pages 1241-1248. ACM, 2018. Google Scholar
  27. Richard Lipton, Evangelos Markakis, and Aranyak Mehta. Playing large games using simple strategies. In Proceedings of EC, pages 36-41, 2003. Google Scholar
  28. Zhengyang Liu and Ying Sheng. On the approximation of Nash equilibria in sparse win-lose games. In Proceedings of AAAI, volume 32(1), 2018. Google Scholar
  29. Andrew McLennan and Rabee Tourky. Imitation games and computation. Games and Economic Behavior, 70(1):4-11, 2010. Google Scholar
  30. Andrew McLennan and Rabee Tourky. Simple complexity from imitation games. Games and Economic Behavior, 68(2):683-688, 2010. Google Scholar
  31. Ruta Mehta. Constant rank two-player games are PPAD-hard. SIAM J. Comput., 47(5):1858-1887, 2018. Google Scholar
  32. Aniket Murhekar and Ruta Mehta. Approximate Nash equilibria of imitation games: Algorithms and complexity. In Proceedings of AAMAS, pages 887-894, 2020. Google Scholar
  33. John Nash. Non-cooperative games. Annals of Mathematics, 54(2):286-295, 1951. Google Scholar
  34. Panagiota N. Panagopoulou and Paul G. Spirakis. Random bimatrix games are asymptotically easy to solve (a simple proof). Theory of Computing Systems, 54(3):479-490, 2014. Google Scholar
  35. Aviad Rubinstein. Settling the complexity of computing approximate two-player Nash equilibria. In Proceedings of FOCS, pages 258-265, 2016. Google Scholar
  36. Haralambos Tsaknakis and Paul G. Spirakis. An optimization approach for approximate Nash equilibria. Internet Mathematics, 5(4):365-382, 2008. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact