Pure Nash Equilibria and Best-Response Dynamics in Random Games

References

• [1] Arratia R, Goldstein L, Gordon L (1989) Two moments suffice for Poisson approximations: The Chen-Stein method. Ann. Probab. 17(1):9–25.Crossref, Google Scholar
• [2] Bernheim BD (1984) Rationalizable strategic behavior. Econometrica 52(4):1007–1028.Crossref, Google Scholar
• [3] Blum A, Mansour Y (2007) Learning, regret minimization, and equilibria. Nisan N, Roughgarden T, Tardos É, Vazirani VV, eds. Algorithmic Game Theory (Cambridge University Press, Cambridge, UK), 79–101.Google Scholar
• [4] Blume LE (1993) The statistical mechanics of strategic interaction. Games Econom. Behav. 5(3):387–424.Crossref, Google Scholar
• [5] Bollobás B (2001) Random Graphs, 2nd ed. (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [6] Borel E (1921) La théorie du jeu et les équations intégrales à noyau symétrique. Comptes Rendus Acad. Sci. Paris 173:1304–1308.Google Scholar
• [7] Broadbent SR, Hammersley JM (1957) Percolation processes. I. Crystals and mazes. Proc. Cambridge Philosophical Soc. 53:629–641.Google Scholar
• [8] Candogan O, Menache I, Ozdaglar A, Parrilo PA (2011) Flows and decompositions of games: harmonic and potential games. Math. Oper. Res. 36(3):474–503.Link, Google Scholar
• [9] Christodoulou G, Mirrokni VS, Sidiropoulos A (2012) Convergence and approximation in potential games. Theoret. Comput. Sci. 438:13–27.Crossref, Google Scholar
• [10] Cohen JE (1998) Cooperation and self-interest: Pareto-inefficiency of Nash equilibria in finite random games. Proc. National Acad. Sci. USA 95(17):9724–9731.Crossref, Google Scholar
• [11] Coucheney P, Durand S, Gaujal B, Touati C (2014) General revision protocols in best response algorithms for potential games. Bagagiolo F, Shimkin N, eds., Netwok Games, Control and OPtimization (NetGCoop) (IEEE Explore, Trento, Italy), 239–246.Google Scholar
• [12] Daskalakis C, Dimakis AG, Mossel E (2011) Connectivity and equilibrium in random games. Ann. Appl. Probab. 21(3):987–1016.Crossref, Google Scholar
• [13] Daskalakis C, Goldberg PW, Papadimitriou CH (2009) The complexity of computing a Nash equilibrium. SIAM J. Comput. 39(1):195–259.Crossref, Google Scholar
• [14] Dresher M (1970) Probability of a pure equilibrium point in n-person games. J. Combinatorial Theory 8:134–145.Crossref, Google Scholar
• [16] Durand S, Gaujal B (2016) Complexity and optimality of the best response algorithm in random potential games. Algorithmic Game Theory, vol. 9928 of Lecture Notes in Computer Science (Springer, Berlin), 40–51.Google Scholar
• [15] Durand S, Garin F, Gaujal B (2019) Distributed best response dynamics with high playing rates in potential games. Performance Evaluation 129:40–59.Crossref, Google Scholar
• [17] Durrett R (2019) Probability—Theory and Examples, 5th ed. (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [18] Dütting P, Kesselheim T (2021) Best-response dynamics in combinatorial auctions with item bidding. Games Econom. Behav. Forthcoming.Google Scholar
• [19] Erdős P, Spencer J (1979) Evolution of the n-cube. Comput. Math. Appl. 5(1):33–39.Crossref, Google Scholar
• [20] Fabrikant A, Jaggard AD, Schapira M (2013) On the structure of weakly acyclic games. Theory Comput. Systems 53(1):107–122.Crossref, Google Scholar
• [21] Friedman JW, Mezzetti C (2001) Learning in games by random sampling. J. Econom. Theory 98(1):55–84.Crossref, Google Scholar
• [22] Galla T, Farmer JD (2013) Complex dynamics in learning complicated games. Proc. National Acad. Sci. USA 110(4):1232–1236.Crossref, Google Scholar
• [23] Goemans M, Mirrokni V, Vetta A (2005) Sink equilibria and convergence. Tardos E, ed., 46th Annual IEEE Sympos. on Foundations of Comput. Sci. (IEEE, Pittsburgh, PA), 142–151.Google Scholar
• [24] Goldberg K, Goldman AJ, Newman M (1968) The probability of an equilibrium point. J. Res. National Bureau Standards Section B 72B:93–101.Crossref, Google Scholar
• [25] Goldman AJ (1957) The probability of a saddlepoint. Amer. Math. Monthly 64:729–730.Crossref, Google Scholar
• [26] Grimmett G (1999) Percolation, 2nd ed. (Springer-Verlag, Berlin).Crossref, Google Scholar
• [27] Linusson S (2009) A note on correlations in randomly oriented graphs. Technical report. Preprint, submitted May 24, https://arxiv.org/abs/0905.2881.Google Scholar
• [28] McDiarmid C, Scott A, Withers P (2020) The component structure of dense random subgraphs of the hypercube. Technical report. Preprint, submitted April 1, https://arxiv.org/abs/1806.06433.Google Scholar
• [29] Monderer D, Shapley LS (1996) Potential games. Games Econom. Behav. 14(1):124–143.Crossref, Google Scholar
• [30] Nash J (1951) Non-cooperative games. Ann. Math. 54(2):286–295.Crossref, Google Scholar
• [31] Nash JF Jr (1950) Equilibrium points in n-person games. Proc. National Acad. Sci. USA 36:48–49.Crossref, Google Scholar
• [32] Osborne MJ, Rubinstein A (1994) A Course in Game Theory (MIT Press, Cambridge, MA).Google Scholar
• [33] Pangallo M, Heinrich T, Doyne Farmer J (2019) Best reply structure and equilibrium convergence in generic games. Sci. Adv. 5(2):eaat1328.Crossref, Google Scholar
• [34] Pei T, Takahashi S (2019) Rationalizable strategies in random games. Games Econom. Behav. 118:110–125.Crossref, Google Scholar
• [35] Powers IY (1990) Limiting distributions of the number of pure strategy Nash equilibria in N-person games. Internat. J. Game Theory 19(3):277–286.Crossref, Google Scholar
• [36] Raič M (2003) Normal approximation by Stein’s method. Mrvar A, ed. Proc. 7th Young Statisticians Meeting (Faculty of Social Sciences, University of Ljubljana, Ljubljana, Slovenia), 71–97.Google Scholar
• [37] Rinott Y, Scarsini M (2000) On the number of pure strategy Nash equilibria in random games. Games Econom. Behav. 33(2):274–293.Crossref, Google Scholar
• [38] Stanford W (1995) A note on the probability of k pure Nash equilibria in matrix games. Games Econom. Behav. 9(2):238–246.Crossref, Google Scholar
• [39] Stanford W (1996) The limit distribution of pure strategy Nash equilibria in symmetric bimatrix games. Math. Oper. Res. 21(3):726–733.Link, Google Scholar
• [40] Stanford W (1997) On the distribution of pure strategy equilibria in finite games with vector payoffs. Math. Social Sci. 33(2):115–127.Crossref, Google Scholar
• [41] Stanford W (1999) On the number of pure strategy Nash equilibria in finite common payoffs games. Econom. Lett. 62(1):29–34.Crossref, Google Scholar
• [42] Takahashi S (2008) The number of pure Nash equilibria in a random game with nondecreasing best responses. Games Econom. Behav. 63(1):328–340.Crossref, Google Scholar
• [43] Takahashi S, Yamamori T (2002) The pure Nash equilibrium property and the quasi-acyclic condition. Econom. Bull. 3(22):1–6.Google Scholar
• [44] Tardos E, Vazirani VV (2007) Basic solution concepts and computational issues. Nisan N, Roughgarden T, Tardos É, Vazirani VV, eds. Algorithmic Game Theory (Cambridge University Press, Cambridge, UK), 3–28.Google Scholar
• [45] von Neumann J (1928) Zur theorie der gesellschaftsspiele. Math. Ann. 100(1):295–320.Crossref, Google Scholar
• [46] Watson GN (1995) A Treatise on the Theory of Bessel Functions (Cambridge University Press, Cambridge, UK).Google Scholar
• [47] Young HP (1993) The evolution of conventions. Econometrica 61(1):57–84.Crossref, Google Scholar