Computing Nash equilibria by iterated polymatrix approximation. (English) Zbl 1200.91019

Govindan, Srihari; Wilson, Robert

J. Econ. Dyn. Control 28, No. 7, 1229-1241 (2004).

Summary: This article develops a new algorithm for computing Nash equilibria of \(N\)-player games. The algorithm approximates a game by a sequence of polymatrix games in which the players interact bilaterally. We provide sufficient conditions for local convergence to an equilibrium and report computational experience. The algorithm convergences globally and rapidly on test problems, although in theory it is not failsafe because it can stall on a set of codimension 1. But it can stall only at an approximate equilibrium with index +1, thus allowing a switch to the global Newton method, which is slower but can fail only on a set of codimension 2. Thus, the algorithm can be used to obtain a fast start for the more reliable global Newton method.

MSC:

91A10	Noncooperative games
90C59	Approximation methods and heuristics in mathematical programming
90C53	Methods of quasi-Newton type
91A06	\(n\)-person games, \(n>2\)

Keywords:

game; equilibrium; algorithm; homotopy; polymatrix approximation

References:

[1]	Bochnak, J.; Coste, M.; Roy, M. F., Real Algebraic Geometry (1998), Springer: Springer Berlin · Zbl 0633.14016
[2]	Eaves, B. C., Homotopies for the computation of fixed points, Mathematical Programming Study, 3, 25-37 (1972)
[3]	Eaves, B. C., A Course in Triangulations for Solving Equations with Deformations (1984), Springer: Springer Berlin · Zbl 0558.65035
[4]	Eaves, B.; Lemke, C., Equivalence of LCPs and PLSs, Mathematics of Operations Research, 6, 475-494 (1981) · Zbl 0515.90073
[5]	Eaves, B. C.; Scarf, H., The solution of systems of piecewise linear equations, Mathematics of Operations Research, 1, 1-27 (1975) · Zbl 0458.65056
[6]	Eaves, B.; Schmedders, K., General equilibrium models and homotopy methods, Journal of Economic Dynamics and Control, 23, 1249-1279 (1999) · Zbl 1016.91074
[7]	Govindan, S.; Wilson, R., Structure theorems for game trees, Proceedings of the National Academy of Sciences, USA, 99, 9077-9080 (2002) · Zbl 1050.91006
[8]	Govindan, S.; Wilson, R., A global Newton method to compute Nash equilibria, Journal of Economic Theory, 110, 65-86 (2003) · Zbl 1042.91001
[9]	Gül, F.; Pearce, D.; Stacchetti, E., A bound on the proportion of pure strategy equilibria in generic games, Mathematics of Operations Research, 18, 548-552 (1993) · Zbl 0804.90144
[10]	Harsanyi, J., The tracing procedurea Bayesian approach to defining a solution for \(n\)-person noncooperative games, International Journal of Game Theory, 4, 61-94 (1975) · Zbl 0319.90078
[11]	Herings, P. J.J.; Peeters, R. J.A. P., A differentiable homotopy to compute Nash equilibria of \(n\)-person games, Economic Theory, 18, 159-186 (2001) · Zbl 0986.91001
[13]	Howson, J.; Rosenthal, R., Bayesian equilibria of finite two-person games with incomplete information, Management Science, 21, 313-315 (1974) · Zbl 0306.90088
[14]	Keenan, D., Further remarks on the global Newton method, Journal of Mathematical Economics, 8, 159-165 (1981) · Zbl 0455.90016
[15]	Kohlberg, E.; Mertens, J. F., On the strategic stability of equilibria, Econometrica, 54, 1003-1039 (1986) · Zbl 0616.90103
[17]	Lemke, C., Bimatrix equilibrium points and mathematical programming, Management Science, 11, 681-689 (1965) · Zbl 0139.13103
[18]	Lemke, C.; Howson, J., Equilibrium points of bimatrix games, Journal of the Society of Industrial and Applied Mathematics, 12, 413-423 (1964) · Zbl 0128.14804
[19]	Mathiesen, L., Computation of economic equilibria by a sequence of linear complementarity problems, Mathematical Programming Study, 23, 144-162 (1985) · Zbl 0579.90093
[21]	McKelvey, R.; Palfrey, T., Quantal response equilibria for normal form games, Games and Economic Behavior, 10, 6-38 (1995) · Zbl 0832.90126
[23]	Rosenmüller, J., On a generalization of the Lemke-Howson algorithm to noncooperative N-person Games, SIAM Journal of Applied Mathematics, 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
[25]	Shapley, L., A note on the Lemke-Howson algorithm, Mathematical Programming Study, 1, 175-189 (1974) · Zbl 0366.90133
[26]	Smale, S., A convergent process of price adjustment and global Newton methods, Journal of Mathematical Economics, 3, 107-120 (1976) · Zbl 0354.90018
[27]	van den Elzen, A.; Talman, D., A procedure for finding Nash equilibria in bi-matrix games, ZOR-Methods and Models of Operations Research, 35, 27-43 (1991) · Zbl 0729.90093
[28]	van den Elzen, A.; Talman, D., Finding a Nash equilibrium in noncooperative N-person games by solving a sequence of linear stationary point problems, ZOR-Mathematical Methods of Operations Research, 39, 365-375 (1994) · Zbl 0820.90133
[29]	von Stengel, B., New maximal numbers of equilibria in bimatrix games, Discrete and Computational Geometry, 21, 557-568 (1999) · Zbl 0956.91003
[30]	Wilson, R., Computing equilibria of N-person games, SIAM Journal of Applied Mathematics, 21, 80-87 (1971) · Zbl 0218.90077
[31]	Wilson, R., Computing simply stable equilibria, Econometrica, 60, 1039-1070 (1992) · Zbl 0768.90097