×

Homotopy methods to compute equilibria in game theory. (English) Zbl 1185.91028

The referred paper deals with the analysis and survey of homotopy-based methods of computing the equilibria of strategic games. The main contribution to game theory consists in an overview and discussion of a wide scale of the existing computation methods with special regard to the strength of the homotopy-based approaches, and in the presentation of their further extension to extensive form and dynamic games.

MSC:

91A10 Noncooperative games
65H20 Global methods, including homotopy approaches to the numerical solution of nonlinear equations
91A25 Dynamic games
91A18 Games in extensive form

Software:

HOMPACK
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allgower E.L., Georg K.: Numerical Continuation Methods: An Introduction. Springer, Berlin (1990) · Zbl 0717.65030
[2] Avis, D., Rosenberg, G., Savani, R., von Stengel, B.: Enumeration of Nash equilibria for two-player games. Econ Theory (2009, this issue) · Zbl 1182.91013
[3] Balthasar, A.: Equilibrium tracing in strategic-form games. Econ Theory (2009, this issue) · Zbl 1182.91019
[4] Browder F.E.: On continuity of fixed points under deformations of continuous mappings. Summa Brasiliensis Math 4, 183–191 (1960) · Zbl 0102.37807
[5] Datta, R.S.: Finding all Nash equilibria of a finite game using polynomial algebra. Econ Theory (2009, this issue)
[6] Eaves B.C.: Polymatrix games with joint constraints. SIAM J Appl Math 24, 418–423 (1973) · Zbl 0253.90067 · doi:10.1137/0124043
[7] Eaves B.C., Schmedders K.: General equilibrium models and homotopy methods. J Econ Dyn Control 23, 1249–1279 (1999) · Zbl 1016.91074 · doi:10.1016/S0165-1889(98)00073-6
[8] van den Elzen A.H., Talman A.J.J.: A procedure for finding Nash equilibria in bi-matrix games. ZOR Methods Models Oper Res 35, 27–43 (1991) · Zbl 0729.90093 · doi:10.1007/BF01415958
[9] van den Elzen A.H., Talman A.J.J.: An algorithmic approach toward the tracing procedure for bi-matrix games. Games Econ Behav 28, 130–145 (1999) · Zbl 0939.91006 · doi:10.1006/game.1998.0688
[10] Filar J.A., Raghavan T.E.S.: A matrix game solution of a single controller stochastic game. Math Oper Res 9, 356–362 (1984) · Zbl 0549.90101 · doi:10.1287/moor.9.3.356
[11] Garcia C.B., Zangwill W.I.: Pathways to Solutions, Fixed Points, and Equilibria. Prentice Hall, Englewood Cliffs (1981) · Zbl 0512.90070
[12] Garcia C.B., Lemke C.E., Lüthi H.J.: Simplicial approximation of an equilibrium point of noncooperative n-person games. In: Hu, T.C., Robinson, S.M. (eds) Mathematical Programming, pp. 227–260. Academic Press, New York (1973)
[13] Geanakoplos J.D.: Nash and Walras equilibrium via Brouwer. Econ Theory 21, 585–603 (2003) · Zbl 1049.91105 · doi:10.1007/s001990000076
[14] 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
[15] Govindan S., Wilson R.: A global Newton method to compute Nash equilibria. J Econ Theory 110, 65–86 (2003) · Zbl 1042.91001
[16] Govindan S., Wilson R.: Computing Nash equilibria by iterated polymatrix approximation. J Econ Dyn Control 28, 1229–1241 (2004) · Zbl 1200.91019 · doi:10.1016/S0165-1889(03)00108-8
[17] Harsanyi J.C.: The tracing procedure: a Bayesian approach to defining a solution for n-person noncooperative games. Int J Game Theory 4, 61–94 (1975) · Zbl 0319.90078 · doi:10.1007/BF01766187
[18] Harsanyi J.C., Selten R.: A General Theory of Equilibrium Selection in Games. MIT Press, Cambridge (1988) · Zbl 0693.90098
[19] Herings P.J.J.: A globally and universally stable price adjustment process. J Math Econ 27, 163–193 (1997) · Zbl 0883.90031 · doi:10.1016/S0304-4068(96)00770-7
[20] Herings P.J.J.: Two simple proofs of the feasibility of the linear tracing procedure. Econ Theory 15, 485–490 (2000) · Zbl 0956.91008 · doi:10.1007/s001990050024
[21] Herings P.J.J.: Universally converging adjustment processes–a unifying approach. J Math Econ 38, 341–370 (2002) · Zbl 1035.91044 · doi:10.1016/S0304-4068(02)00060-5
[22] Herings P.J.J., van den Elzen A.H.: Computation of the Nash equilibrium selected by the tracing procedure in n-person games. Games Econ Behav 38, 89–117 (2002) · Zbl 1013.91004 · doi:10.1006/game.2001.0856
[23] Herings P.J.J., Peeters R.: A differentiable homotopy to compute Nash equilibria of n-person games. Econ Theory 18, 159–185 (2001) · Zbl 0986.91001 · doi:10.1007/PL00004129
[24] Herings P.J.J., Peeters R.: Stationary equilibria in stochastic games: structure, selection and computation. J Econ Theory 118, 32–60 (2004) · Zbl 1117.91009 · doi:10.1016/j.jet.2003.10.001
[25] Herings P.J.J., Peeters R.: A globally convergent algorithm to compute all Nash equilibria for n-person games. Ann Oper Res 137, 349–368 (2005) · Zbl 1138.91310 · doi:10.1007/s10479-005-2265-4
[26] Howson J.T. Jr: Equilibria of polymatrix games. Manag Sci 21, 313–315 (1972) · Zbl 0228.90058
[27] Howson J.T. Jr, Rosenthal R.W.: Bayesian equilibria of finite two-person games with incomplete information. Manag Sci 21, 313–315 (1974) · Zbl 0306.90088 · doi:10.1287/mnsc.21.3.313
[28] Jongen, H.Th., Jonker, P., Twilt, F.: Nonlinear optimization in \({\mathbb {R}^n}\) , I. Morse Theory, Chebyshev Approximation. Methoden und Verfahren der Mathematischen Physik, 29. Frankfurt: Peter Lang (1983) · Zbl 0527.90064
[29] Judd K.L.: Computational economics and economic theory: substitutes or complements?. J Econ Dyn Control 21, 907–942 (1997) · Zbl 0901.90084 · doi:10.1016/S0165-1889(97)00010-9
[30] Kohlberg E., Mertens J.F.: On the strategic stability of equilibria. Econometrica 54, 1003–1037 (1986) · Zbl 0616.90103 · doi:10.2307/1912320
[31] Koller D., Megiddo N., von Stengel B.: Efficient computation of equilibria for extensive two-person games. Games Econ Behav 14, 247–259 (1996) · Zbl 0859.90127 · doi:10.1006/game.1996.0051
[32] Kostreva M.M., Kinard L.A.: A differential homotopy approach for solving polynomial optimization problems and noncooperative games. Comput Math Appl 21, 135–143 (1991) · Zbl 0721.90071 · doi:10.1016/0898-1221(91)90168-4
[33] van der Laan G., Talman A.J.J., Heijden L.: Simplicial variable dimension algorithms for solving the nonlinear complementarity problem on a product of unit simplices using a general labelling. Math Oper Res 12, 377–397 (1987) · Zbl 0638.90096 · doi:10.1287/moor.12.3.377
[34] Lemke C.E.: Bimatrix equilibrium points and mathematical programming. Manag Sci 11, 681–689 (1965) · Zbl 0139.13103 · doi:10.1287/mnsc.11.7.681
[35] Lemke C.E., Howson J.T. Jr: Equilibrium points of bimatrix games. SIAM J Appl Math 12, 413–423 (1964) · Zbl 0128.14804 · doi:10.1137/0112033
[36] Mas-Colell A.: A note on a theorem of F. Browder. Math Program 6, 229–233 (1974) · Zbl 0285.90068 · doi:10.1007/BF01580239
[37] Mas-Colell A.: The Theory of General Economic Equilibrium, a Differentiable Approach. Cambridge University Press, Cambridge (1985) · Zbl 0569.90010
[38] McKelvey R.D., McLennan A.: Computation of equilibria in finite games. In: Amman, H.M., Kendrick, D.A., Rust, J. (eds) Handbook of Computational Economics, vol. I, pp. 87–142. Elsevier/North-Holland, Amsterdam (1996) · Zbl 1126.91304
[39] McKelvey R.D., Palfrey T.R.: Quantal response equilibria for normal form games. Games Econ Behav 10, 6–38 (1995) · Zbl 0832.90126 · doi:10.1006/game.1995.1023
[40] McKelvey R.D., Palfrey T.R.: Quantal response equilibria for extensive form games. Exp Econ 1, 9–41 (1998) · Zbl 0920.90141
[41] McLennan A.: The expected number of Nash equilibria of a normal form game. Econometrica 73, 141–174 (2005) · Zbl 1152.91326 · doi:10.1111/j.1468-0262.2005.00567.x
[42] Nowak A.S., Raghavan T.E.S.: A finite step algorithm via a bimatrix game to a single controller nonzero-sum stochastic game. Math Program 59, 249–259 (1993) · Zbl 0792.90095 · doi:10.1007/BF01581246
[43] Raghavan T.E.S., Syed Z.: Computing stationary Nsh equilibria of undiscounted single-controller stochastic games. Math Oper Res 22, 384–400 (2002) · Zbl 1082.91508 · doi:10.1287/moor.27.2.384.318
[44] Rosenmüller J.: On a generalization of the Lemke–Howson algorithm to noncooperative n-person games. SIAM J Appl Math 21, 73–79 (1971) · Zbl 0222.90053 · doi:10.1137/0121010
[45] Rosenthal R.W.: A bounded-rationality approach to the study of noncooperative games. Int J Game Theory 18, 273–292 (1989) · Zbl 0678.90100 · doi:10.1007/BF01254292
[46] Schanuel S.H., Simon L.K., Zame W.R.: The algebraic geometry of games and the tracing procedure. In: Selten, R. (eds) Game Equilibrium Models II: Methods, Morals and Markets, pp. 9–43. Springer, Berlin (1991) · Zbl 0813.90134
[47] Shapley L.S.: A note on the Lemke–Howson algorithm. Mathematical programming study. Pivoting Ext 1, 175–189 (1974) · Zbl 0366.90133
[48] von Stengel B.: Efficient computation of behavior strategies. Games Econ Behav 14, 220–246 (1996) · Zbl 0867.90131 · doi:10.1006/game.1996.0050
[49] von Stengel B.: Computing equilibria for two-person games. In: Aumann, R.J., Hart, S. (eds) Handbook of Game Theory, chap. 45, vol. 3, pp. 1723–1759. North-Holland, Amsterdam (2002)
[50] von Stengel B., van den Elzen A.H., Talman A.J.J.: Computing normal form perfect equilibria for extensive two-person games. Econometrica 70, 693–715 (2002) · Zbl 1103.91319 · doi:10.1111/1468-0262.00300
[51] Sturmfels, B.: Solving Systems of Polynomial Equations. American Mathematical Society, CBMS Regional Conferences Series, No. 97. Rhode Island, Providence (2002) · Zbl 1101.13040
[52] Todd M.J.: The computation of fixed points and applications. Lecture Notes in Economics and Mathematical Systems, vol. 124. Springer, Berlin (1976) · Zbl 0332.54003
[53] Turocy T.L.: A dynamic homotopy interpretation of the logistical quantal response equilibrium correspondence. Games Econ Behav 51, 243–263 (2005) · Zbl 1099.91005 · doi:10.1016/j.geb.2004.04.003
[54] Voorneveld M.: Probabilistic choice in games: properties of Rosenthal’s t-solutions. Int J Game Theory 34, 105–122 (2006) · Zbl 1151.91385 · doi:10.1007/s00182-005-0003-4
[55] Watson L.T., Billups S.C., Morgan A.P.: HOMPACK: a suite of codes for globally convergent homotopy algorithms. ACM Trans Math Softw 13, 281–310 (1987) · Zbl 0626.65049 · doi:10.1145/29380.214343
[56] Wilson R.: Computing equilibria of n-person games. SIAM J Appl Math 21, 80–87 (1971) · Zbl 0218.90077 · doi:10.1137/0121011
[57] Wilson R.: Computing equilibria of two-person games from the extensive form. Manag Sci 18, 448–460 (1972) · Zbl 0238.90083 · doi:10.1287/mnsc.18.7.448
[58] Wilson R.: Computing simply stable equilibria. Econometrica 60, 1039–1070 (1992) · Zbl 0768.90097 · doi:10.2307/2951538
[59] Yamamoto Y.: A path-following procedure to find a proper equilibrium of finite games. Int J Game Theory 22, 249–259 (1993) · Zbl 0788.90086 · doi:10.1007/BF01240056
[60] Yanovskaya E.B.: Equilibrium points in polymatrix games. Litovskii Matematicheskii Sbornik 8, 381–384 (1986) (in Russian) (see also Math Rev 39, # 3831)
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.