×

On the number of pure strategy Nash equilibria in random games. (English) Zbl 0972.91011

Authors’ summary: How many pure Nash equilibria can we expect to have in a finite game chosen at random? Solutions to the above problem have been proposed in some special cases. In this paper we assume independence among the profiles, but we allow either positive or negative dependence among the players’ payoffs in a same profile. We provide asymptotic results for the distribution of the number of Nash equilibria when either the number of players or the number of strategies increases. We show that different dependence assumptions lead to different asymptotic results.

MSC:

91A10 Noncooperative games
91A60 Probabilistic games; gambling
91A06 \(n\)-person games, \(n>2\)
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Arratia, R.; Goldstein, L.; Gordon, L., Two Moments Suffice for Poisson Approximations: The Chen-Stein Method, Ann. Probab., 17, 9-25 (1989) · Zbl 0675.60017
[2] Baldi, P.; Rinott, Y., Asymptotic Normality of Some Graph-Related Statistics, J. Appl. Probab., 26, 171-175 (1989) · Zbl 0671.60018
[3] Baldi, P.; Rinott, Y., On Normal Approximations of Distributions in Terms of Dependency Graphs, Ann. Probab., 17, 1646-1650 (1989) · Zbl 0691.60020
[4] Baldi, P.; Rinott, Y.; Stein, C., A Normal Approximation for the Number of Local Maxima of a Random Function on a Graph, (Anderson, T. W.; Athreya, K. B.; Iglehart, D. L., Probability, Statistics, and Mathematics. Papers in Honor of Samuel Karlin (1989), Academic Press: Academic Press San Diego), 59-81 · Zbl 0704.62018
[5] Dembo, A.; Rinott, Y., Some Examples of Normal Approximations by Stein’s Method, (Aldous, D.; Pemantle, R., Random Discrete Structures. Random Discrete Structures, IMA, 76 (1996), Springer-Verlag: Springer-Verlag Berlin), 25-44 · Zbl 0847.60015
[6] Dresher, M., Probability of a Pure Equilibrium Point in \(n\)-Person Games, J. Combin. Theory, 8, 134-145 (1970) · Zbl 0226.90048
[7] Goldberg, K.; Goldman, A. J.; Newman, M., The Probability of an Equilibrium Point, J. Res. Natl. Bur. Stand., Sect. B, 72B, 93-101 (1968) · Zbl 0164.20203
[8] Goldman, A. J., The Probability of a Saddlepoint, Amer. Math. Monthly, 64, 729-730 (1957) · Zbl 0087.33804
[9] Gordon, R. D., Values of Mills’ Ratio of Area to Bounding Ordinate and of the Normal Probability Integral for Large Values of the Argument, Ann. Math. Stat., 12, 364-366 (1941) · JFM 67.0467.03
[10] Klaassen, A. J.; Wellner, J., Efficient Estimation in the Bivariate Normal Copula Model: Normal Margins are Least Favorable, Bernoulli, 3, 55-77 (1997) · Zbl 0877.62055
[11] Nash, J. F., Equilibrium Points in \(n\)-Person Games, Proc. Natl. Acad. Sci. USA, 36, 48-49 (1950) · Zbl 0036.01104
[12] Nash, J. F., Noncooperative Games, Ann. of Math., 54, 286-295 (1951) · Zbl 0045.08202
[13] Papavassilopoulos, G. P., On the Probability of Existence of Pure Equilibria in Matrix Games, J. Optim. Theory Appl., 87, 419-439 (1995) · Zbl 0839.90141
[14] Papavassilopoulos, G. P., On the probability of existence of pure equilibria in matrix games, J. Optim. Theory Appl., 91, 729-730 (1996) · Zbl 0869.90091
[15] Powers, I. Y., Limiting Distributions of the Number of Pure Strategy Nash Equilibria in \(N\)-Person Games, Internat. J. Game Theory, 19, 277-286 (1990) · Zbl 0725.90105
[16] Rinott, Y, and, Rotar, V. 1999, A Remark on Quadrant Normal Probabilities in High Dimensions, preprint.; Rinott, Y, and, Rotar, V. 1999, A Remark on Quadrant Normal Probabilities in High Dimensions, preprint. · Zbl 0979.62006
[17] Slepian, D., The One-Sided Barrier Problem for Gaussian Noise, Bell Syst. Tech. J., 41, 463-550 (1962)
[18] Stanford, W., A Note on the Probability of \(k\) Pure Nash Equilibria in Matrix Games, Games Econom. Behavior, 9, 238-246 (1995) · Zbl 0829.90139
[19] Stanford, W., The Limit Distribution of Pure Strategy Nash Equilibria in Symmetric Bimatrix Games, Math. Oper. Res., 21, 726-733 (1996) · Zbl 0871.90113
[20] 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
[21] Stanford, W., On the Number of Pure Strategy Nash Equilibria in Finite Common Payoffs Games, Econ. Lett., 62, 29-34 (1999) · Zbl 0916.90275
[22] Stein, C., Approximate Computation of Expectations. Approximate Computation of Expectations, Institute of Mathematical Statistics Lecture Notes/Monograph Series, 7 (1986), Institute of Mathematical Statistics: Institute of Mathematical Statistics California · Zbl 0721.60016
[23] Tong, Y. L., Probability Inequalities in Multivariate Distributions (1980), Academic Press: Academic Press New York · Zbl 0455.60003
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.