The number of pure Nash equilibria in a random game with nondecreasing best responses. (English) Zbl 1134.91326

Takahashi, Satoru

Games Econ. Behav. 63, No. 1, 328-340 (2008).

Summary: We randomly draw a game from a distribution on the set of two-player games with a given size. We compute the distribution and the expectation of the number of pure-strategy Nash equilibria of the game conditional on the game having nondecreasing best-response functions. The conditional expected number of pure-strategy Nash equilibria becomes much larger than the unconditional expected number as the size of the game grows.

MSC:

91A15	Stochastic games, stochastic differential games
91A05	2-person games

Keywords:

number of Nash equilibria; random game; strategic complementarity; increasing difference; single crossing

References:

[1]	Chu, W., Inverse series relations, formal power series and Blodgett-Gessel’s type binomial identities, Sém. Lothar. Combin., B29c (1992) · Zbl 0965.05019
[2]	Dresher, M., Probability of a pure equilibrium point in \(n\)-person games, J. Combin. Theory, 8, 134-145 (1970) · Zbl 0226.90048
[3]	Echenique, F., A characterization of strategic complementarities, Games Econ. Behav., 46, 325-347 (2004) · Zbl 1085.91502
[4]	Echenique, F.; Edlin, A., Mixed equilibria are unstable in games of strategic complements, J. Econ. Theory, 118, 61-79 (2004) · Zbl 1117.91005
[5]	Frankel, D. M.; Morris, S.; Pauzner, A., Equilibrium selection in global games with strategic complementarities, J. Econ. Theory, 108, 1-44 (2003) · Zbl 1044.91005
[6]	Goldberg, K.; Goldman, A. J.; Newman, M., The probability of an equilibrium point, J. Res. Nat. Bureau Standards-B. Math. Sci., 72B, 93-101 (1968) · Zbl 0164.20203
[7]	Goldman, A. J., The probability of a saddlepoint, Amer. Math. Monthly, 64, 729-730 (1957) · Zbl 0087.33804
[8]	McLennan, A., The expected number of Nash equilibria of a normal form game, Econometrica, 73, 141-174 (2005) · Zbl 1152.91326
[9]	McLennan, A.; Berg, J., The asymptotic expected number of Nash equilibria of two-player normal form games, Games Econ. Behav., 51, 264-295 (2005) · Zbl 1139.91303
[11]	Powers, I. Y., Limiting distributions of the number of pure strategy Nash equilibria in \(n\)-person games, Int. J. Game Theory, 19, 277-286 (1990) · Zbl 0725.90105
[12]	Rinott, Y.; Scarsini, M., On the number of pure strategy Nash equilibria in random games, Games Econ. Behav., 33, 274-293 (2000) · Zbl 0972.91011
[13]	Roberts, D. P., Pure Nash equilibria of coordination matrix games, Econ. Letters, 89, 7-11 (2005) · Zbl 1254.91018
[14]	Stanford, W., A note on the probability of \(k\) pure Nash equilibria in matrix games, Games Econ. Behav., 9, 238-246 (1995) · Zbl 0829.90139
[15]	Stanford, W., The limit distribution of pure strategy Nash equilibria in symmetric bimatrix games, Math. Operations Res., 21, 726-733 (1996) · Zbl 0871.90113
[16]	Stanford, W., On the distribution of pure strategy equilibria in finite games with vector payoffs, Math. Soc. Sci., 33, 115-127 (1997) · Zbl 0916.90285
[17]	Stanford, W., On the number of pure strategy Nash equilibria in finite common payoffs games, Econ. Letters, 62, 29-34 (1999) · Zbl 0916.90275
[18]	Stanley, R. P., Enumerative Combinatorics, vol. 1 (1997), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0889.05001
[20]	Topkis, D. M., Equilibrium points in zonzero-sum \(n\)-person submodular games, SIAM J. Control Optim., 17, 773-787 (1979) · Zbl 0433.90091
[21]	Young, H. P., Individual Strategy and Social Structure (1998), Princeton Univ. Press: Princeton Univ. Press Princeton