A Stable-Set Bound and Maximal Numbers of Nash Equilibria in Bimatrix Games

References

• [1] Adsul B, Garg J, Mehta R, Sohoni M, von Stengel B (2021) Fast algorithms for rank-1 bimatrix games. Oper. Res. 69(2):613–631.Link, Google Scholar
• [2] Allamigeon X, Gaubert S, Meunier F (2023) Tropical complementarity problems and Nash equilibria. SIAM J. Discrete Math. 37(3):1645–1665.Crossref, Google Scholar
• [3] Bostanci J, Watrous J (2022) Quantum game theory and the complexity of approximating quantum Nash equilibria. Quantum 6:882. Crossref, Google Scholar
• [4] Firsching M (2017) Realizability and inscribability for simplicial polytopes via nonlinear optimization. Math. Programming 166(1–2):273–295.Crossref, Google Scholar
• [5] Grünbaum B (2003) Convex Polytopes, Graduate Texts in Mathematics, 2nd ed., vol. 221 (Springer, New York).Crossref, Google Scholar
• [6] Grünbaum B, Sreedharan VP (1967) An enumeration of simplicial 4-polytopes with 8 vertices. J. Combinatorial Theory 2(4):437–465. Crossref, Google Scholar
• [7] Ickstadt C, Theobald T, Tsigaridas E (2024) Semidefinite games. Internat. J. Game Theory 53(3):827–857.Crossref, Google Scholar
• [8] Ickstadt C, Theobald T, von Stengel B (2025) Stable-set bounds for 5x5-games. https://doi.org/10.5281/zenodo.17064079.Google Scholar
• [9] Ickstadt C, Theobald T, Tsigaridas E, Varvitsiotis A (2023) Semidefinite network games: Multiplayer minimax and complementarity problems. Preprint, submitted October 31, https://arxiv.org/abs/2310.20333.Google Scholar
• [10] Joswig M, Theobald T (2013) Polyhedral and Algebraic Methods in Computational Geometry (Springer, London).Crossref, Google Scholar
• [11] Kannan R, Theobald T (2010) Games of fixed rank: A hierarchy of bimatrix games. Econom. Theory 42(1):157–173.Crossref, Google Scholar
• [12] Keiding H (1997) On the maximal number of Nash equilibria in an n×n bimatrix game. Games Econom. Behav. 21(1–2):148–160.Crossref, Google Scholar
• [13] Lemke CE, Howson JT Jr (1964) Equilibrium points of bimatrix games. J. Soc. Indust. Appl. Math. 12(2):413–423.Crossref, Google Scholar
• [14] McKelvey RD, McLennan A (1997) The maximal number of regular totally mixed Nash equilibria. J. Econom. Theory 72(2):411–425.Crossref, Google Scholar
• [15] McLennan A, Park IU (1999) Generic 4×4 two person games have at most 15 Nash equilibria. Games Econom. Behav. 26(1):111–130.Crossref, Google Scholar
• [16] Miyata H, Padrol A (2015) Enumerating neighborly polytopes and oriented matroids. Experiment. Math. 24(4):489–505.Crossref, Google Scholar
• [17] Nash J (1951) Non-cooperative games. Ann. Math. 54(2):286–295.Crossref, Google Scholar
• [18] Quint T, Shubik M (1997) A theorem on the number of Nash equilibria in a bimatrix game. Internat. J. Game Theory 26(3):353–359.Crossref, Google Scholar
• [19] Savani R, von Stengel B (2006) Hard-to-solve bimatrix games. Econometrica 74(2):397–429.Crossref, Google Scholar
• [20] Savani R, von Stengel B (2016) Unit vector games. Internat. J. Econom. Theory 12(1):7–27.Crossref, Google Scholar
• [21] Shapley L (1974) A note on the Lemke–Howson algorithm. Balinski ML, ed. Pivoting and Extensions, Mathematical Programming Studies 1 (Springer, Berlin), 175–189.Crossref, Google Scholar
• [22] von Stengel B (1999) New maximal numbers of equilibria in bimatrix games. Discrete Comput. Geometry 21(4):557–568.Crossref, Google Scholar
• [23] von Stengel B (2002) Computing equilibria for two-person games. Aumann RJ, Hart S, eds. Handbook of Game Theory with Economic Applications, vol. 3 (North-Holland, Amsterdam), 1723–1759.Google Scholar
• [24] von Stengel B (2021) Finding Nash equilibria of two-player games. Preprint, submitted February 8, https://arxiv.org/abs/2102.04580.Google Scholar
• [25] von Stengel B (2022) Game Theory Basics (Cambridge University Press, Cambridge, UK).Google Scholar
• [26] Vujić M (2022) Geometry of the sets of Nash equilibria in mixed extensions of finite games. PhD thesis, University of Mannheim, Mannheim, Germany.Google Scholar
• [27] Ziegler GM (1995) Lectures on Polytopes, Graduate Texts in Mathematics, vol. 152 (Springer, New York).Crossref, Google Scholar