×

Enumeration of Nash equilibria for two-player games. (English) Zbl 1182.91013

Summary: This paper describes algorithms for finding all Nash equilibria of a two-player game in strategic form. We present two algorithms that extend earlier work. Our presentation is self-contained, and explains the two methods in a unified framework using faces of best-response polyhedra. The first method \(lrsNash\) is based on the known vertex enumeration program \(lrs\), for “lexicographic reverse search”. It enumerates the vertices of only one best-response polytope, and the vertices of the complementary faces that correspond to these vertices (if they are not empty) in the other polytope. The second method is a modification of the known \(EEE\) algorithm, for “enumeration of extreme equilibria”. We also describe a second, as yet not implemented, variant that is space efficient. We discuss details of implementations of \(lrsNash\) and \(EEE\), and report on computational experiments that compare the two algorithms, which show that both have their strengths and weaknesses.

MSC:

91A05 2-person games
91A10 Noncooperative games
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C05 Linear programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Audet C., Belhaï za S., Hansen P.: Enumeration of all extreme equilibria in game theory: bimatrix and polymatrix games. J Optim Theory Appl 129, 349–372 (2006) · Zbl 1122.91009 · doi:10.1007/s10957-006-9070-3
[2] Audet, C., Belhaï za, S., Hansen, P.: A new sequence form approach for the enumeration of all extreme Nash equilibria for extensive form games. Int Game Theory Rev, to appear (2009) · Zbl 1193.91019
[3] Audet C., Hansen P., Jaumard B., Savard G.: Enumeration of all extreme equilibria of bimatrix games. SIAM J Sci Comput 23, 323–338 (2001) · Zbl 0996.91004 · doi:10.1137/S1064827598339086
[4] Avis, D. lrs: a revised implementation of the reverse search vertex enumeration algorithm. In: Kalai, G., Ziegler, G. (eds.): Polytopes–Combinatorics and Computation, DMV Seminar Band 29, pp. 177–198. Basel: Birkhäuser (2000) · Zbl 0960.68171
[5] Avis, D.: User’s Guide for lrs. http://cgm.cs.mcgill.ca/\(\sim\)avis (2006)
[6] Avis D., Fukuda K.: A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. Discrete Comput Geom 8, 295–313 (1992) · Zbl 0752.68082 · doi:10.1007/BF02293050
[7] Avis D., Bremner D., Seidel R.: How good are convex hull algorithms?. Comput Geom 7, 265–301 (1997) · Zbl 0877.68119 · doi:10.1016/S0925-7721(96)00023-5
[8] Azulay D.-O., Pique J.-F.: A revised simplex method with integer Q-matrices. ACM Trans Math Softw 27, 350–360 (2001) · Zbl 1070.65545 · doi:10.1145/502800.502804
[9] Bron C., Kerbosch J.: Finding all cliques of an undirected graph. Comm ACM 16, 575–577 (1973) · Zbl 0261.68018 · doi:10.1145/362342.362367
[10] Canty M.J.: Resolving Conflicts with Mathematica: Algorithms for Two-Person Games. Academic Press, Amsterdam (2003)
[11] Chvátal V.: Linear Programming. Freeman, New York (1983) · Zbl 0537.90067
[12] Cormen T.H., Leiserson C.E., Rivest R.L., Stein C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge, Mass (2001) · Zbl 1047.68161
[13] Dickhaut J., Kaplan T.: A program for finding Nash equilibria. Mathematica J 1(4), 87–93 (1991)
[14] Fukuda K., Prodon A. et al.: Double description method revisited. In: Deza, M. (eds) Combinatorics and Computer Science, Lecture Notes in Computer Science, vol 1120., pp. 91–121. Springer, Berlin (1996)
[15] Gilboa I., Zemel E.: Nash and correlated equilibria: some complexity considerations. Games Econ Behav 1, 80–93 (1989) · Zbl 0755.90093 · doi:10.1016/0899-8256(89)90006-7
[16] Jansen M.J.M.: Maximal Nash subsets for bimatrix games. Naval Res Logist Quart 28, 147–152 (1981) · Zbl 0454.90093 · doi:10.1002/nav.3800280111
[17] Kohlberg E., Mertens J.-F.: On the strategic stability of equilibria. Econometrica 54, 1003–1037 (1986) · Zbl 0616.90103 · doi:10.2307/1912320
[18] Kuhn H.W.: An algorithm for equilibrium points in bimatrix games. Proc Nat Acad Sci USA 47, 1657–1662 (1961) · Zbl 0171.40902 · doi:10.1073/pnas.47.10.1657
[19] Lemke C.E., Howson J.T. Jr: Equilibrium points of bimatrix games. J Soc Ind Appl Math 12, 413–423 (1964) · Zbl 0128.14804 · doi:10.1137/0112033
[20] Mangasarian O.L.: Equilibrium points in bimatrix games. J Soc Ind Appl Math 12, 778–780 (1964) · Zbl 0132.14002 · doi:10.1137/0112064
[21] McKelvey, R.D., McLennan, A.M., Turocy, T.L.: Gambit: Software Tools for Game Theory, Version 0.2007.01.30 http://econweb.tamu.edu/gambit (2007)
[22] Millham C.B.: On Nash subsets of bimatrix games. Naval Res Logist Quart 21, 307–317 (1974) · Zbl 0366.90132 · doi:10.1002/nav.3800210210
[23] Motzkin, T.S., Raiffa, H., Thompson, G.L., Thrall, R.M.: The double description method. In: Kuhn, H.W., Tucker, A.W. (eds.) Contributions to the Theory of Games II, pp. 51–73. Annals of Mathematics Studies 28, Princeton: Princeton University Press (1953) · Zbl 0050.14201
[24] Nash J.F.: Non-cooperative games. Ann Math 54, 286–295 (1951) · Zbl 0045.08202 · doi:10.2307/1969529
[25] Rosenberg, G.D.: Enumeration of All Extreme Equilibria of Bimatrix Games with Integer Pivoting and Improved Degeneracy Check. CDAM Research Report LSE-CDAM-2005-18, London School of Economics (2005)
[26] Savani, R.: Solve a bimatrix game. Interactive website. http://banach.lse.ac.uk/form.html (2005)
[27] Shapley, L.S.: A note on the Lemke–Howson algorithm. Mathematical Programming Study 1: Pivoting and Extensions, pp. 175–189 (1974)
[28] van den Elzen A.H., Talman A.J.J.: A procedure for finding Nash equilibria in bi-matrix games. Math Meth Oper Res 35, 27–43 (1991) · Zbl 0729.90093 · doi:10.1007/BF01415958
[29] von Schemde A., von Stengel B.: Strategic characterization of the index of an equilibrium. In: Monien, B., Schroeder, U.-P. (eds) Symposium on Algorithmic Game Theory (SAGT) 2008, Lecture Notes in Computer Science, vol. 4997, pp. 242–254. Springer, Berlin (2008) · Zbl 1136.91344
[30] von Stengel B.: Efficient computation of behavior strategies. Games Econ Behav 14, 220–246 (1996) · Zbl 0867.90131 · doi:10.1006/game.1996.0050
[31] von Stengel, B.: Improved equilibrium enumeration for bimatrix games. Extended Abstract, In: International Conference on Operations Research, ETH Zurich, 31 Aug–3 Sept. http://www.maths.lse.ac.uk/Personal/stengel/TEXTE/complement-enum.pdf (1998)
[32] von Stengel B.: New maximal numbers of equilibria in bimatrix games. Discrete Comput Geom 21, 557–568 (1999) · Zbl 0956.91003 · doi:10.1007/PL00009438
[33] von Stengel B.: Computing equilibria for two-person games. In: Aumann, R.J., Hart, S. (eds) Handbook of Game Theory, vol. 3., pp. 1723–1759. North-Holland, Amsterdam (2002)
[34] Vorob’ev N.N.: Equilibrium points in bimatrix games. Theory Prob Appl 3, 297–309 (1958) · doi:10.1137/1103024
[35] Winkels H.-M.: An algorithm to determine all equilibrium points of a bimatrix game. In: Moeschlin, O., Pallaschke, D. (eds) Game Theory and Related Topics., pp. 137–148. North-Holland, Amsterdam (1979) · Zbl 0424.90090
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.