×
Govindan, Srihari; Wilson, Robert

A global Newton method to compute Nash equilibria. (English) Zbl 1042.91001

J. Econ. Theory 110, No. 1, 65-86 (2003).
Summary: A new algorithm is presented for computing Nash equilibria of finite games. Using E. Kohlberg and J.-F. Mertens’ structure theorem [Econometrica 54, 1003–1037 (1986; Zbl 0616.90130)] we show that a homotopy method can be represented as a dynamical system and implemented by Smale’s global Newton method. The algorithm is outlined and computational experience is reported.

Cited in 30 Documents

MSC:

91A10 Noncooperative games
65H20 Global methods, including homotopy approaches to the numerical solution of nonlinear equations

Keywords:

Noncooperative game; Nash equilibrium; algorithm; global Newton method; homotopy

Citations:

Zbl 0616.90130
PDF BibTeX XML Cite
\textit{S. Govindan} and \textit{R. Wilson}, J. Econ. Theory 110, No. 1, 65--86 (2003; Zbl 1042.91001)
Full Text: DOI

References:

[1] Balasko, Y., Foundations of the Theory of General Equilibrium (1988), Academic Press: Academic Press Orlando, FL · Zbl 0644.90001
[2] Dold, A., Lectures on Algebraic Topology (1972), Springer: Springer New York · Zbl 0234.55001
[3] Eaves, B., The linear complementarity problem, Management Sci., 17, 612-634 (1971) · Zbl 0228.15004
[4] Eaves, B., Homotopies for the computation of fixed points, Math. Program., 3, 25-237 (1972) · Zbl 0258.65060
[5] Eaves, B., A Course in Triangulations for Solving Equations with Deformations (1984), Springer: Springer Berlin · Zbl 0558.65035
[6] Eaves, B.; Scarf, H., Equivalence of LCPs and PLS, Math. Methods Oper. Res., 6, 475-494 (1981)
[7] Eaves, B.; Schmedders, K., General equilibrium models and homotopy methods, J. Econom. Dyn. Control, 23, 1249-1279 (1999) · Zbl 1016.91074
[8] Govindan, S.; Wilson, R., Equivalence and invariance of degree and index of Nash equilibria, Games Econom. Behav., 26, 56-61 (1997) · Zbl 0891.90175
[9] Govindan, S.; Wilson, R., Direct proofs of generic finiteness of Nash equilibrium outcomes, Econometrica, 69, 765-769 (2001) · Zbl 1020.91008
[11] Govindan, S.; Wilson, R., Structure theorems for game trees, Proc. Natl. Acad. Sci., 99, 9077-9080 (2002), Available online at www.pnas.org · Zbl 1050.91006
[12] Gül, F.; Pearce, D.; Stacchetti, E., A bound on the proportion of pure strategy equilibria in generic games, Math. Methods Oper. Res., 18, 548-552 (1993) · Zbl 0804.90144
[13] Harsanyi, J.; Selten, R., A General Theory of Equilibrium Selection in Games (1988), MIT Press: MIT Press Cambridge, MA · Zbl 0693.90098
[14] Herings, P.; Peeters, R., A differentiable homotopy to compute Nash equilibria of \(n\)-person games, Econom. Theory, 18, 159-185 (2001) · Zbl 0986.91001
[15] Hirsch, M., A proof of the non-retractability of a cell onto its boundary, Proc. Amer. Math. Soc., 14, 364-365 (1963) · Zbl 0113.16704
[16] Hirsch, M.; Smale, S., On algorithms for solving \(f(x)=0\), Commun. Pure Appl. Math., 32, 281-312 (1979) · Zbl 0408.65032
[17] Howson, J.; Rosenthal, R., Bayesian equilibria of finite two-person games with incomplete information, Management Sci., 21, 313-315 (1974) · Zbl 0306.90088
[18] Keenan, D., Further remarks on the global Newton method, J. Math. Econom., 8, 159-165 (1981) · Zbl 0455.90016
[19] Kohlberg, E.; Mertens, J.-F., On the strategic stability of equilibria, Econometrica, 54, 1003-1039 (1986) · Zbl 0616.90103
[20] Lemke, C., Bimatrix equilibrium points and mathematical programming, Management Sci., 11, 681-689 (1965) · Zbl 0139.13103
[21] Lemke, C.; Howson, J., Equilibrium points of bimatrix games, J. Soc. Ind. Appl. Math., 12, 413-423 (1964) · Zbl 0128.14804
[22] Mertens, J., Stable equilibria—a reformulation, Part Idefinition and basic properties, Math. Methods Oper. Res., 14, 575-625 (1989) · Zbl 0687.90097
[23] 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
[24] Scarf, H.; Hansen, T., The Computation of Economic Equilibrium (1973), Yale University Press: Yale University Press New Haven, CT
[25] Shapley, L., A note on the Lemke-Howson algorithm, Math. Program. Stud., 1, 175-189 (1974) · Zbl 0366.90133
[26] Smale, S., A convergent process of price adjustment and global Newton methods, J. Math. Econom., 3, 107-120 (1976) · Zbl 0354.90018
[27] Tomlin, J., Robust implementation of Lemke’s method for the linear complementarity problem, Math. Program. Stud., 7, 55-60 (1978) · Zbl 0378.90055
[30] Wilson, R., Computing equilibria of \(n\)-person games, SIAM J. Appl. Math., 21, 80-87 (1971) · Zbl 0218.90077
[31] Wilson, R., Computing equilibria of two-person games from the extensive form, Management Sci., 18, 448-460 (1972) · Zbl 0238.90083
[32] Wilson, R., Computing simply stable equilibria, Econometrica, 60, 1039-1070 (1972) · Zbl 0768.90097
[33] Wilson, R., The bilinear complementarity problem and competitive equilibria of piecewise-linear economic models, Econometrica, 46, 87-103 (1978) · Zbl 0372.90025
[34] 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
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.