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

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.


91A15 Stochastic games, stochastic differential games
91A05 2-person games
Full Text: DOI


[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
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.