Best-response dynamics, playing sequences, and convergence to equilibrium in random games. (English) Zbl 1522.91037
Summary: We analyze the performance of the best-response dynamic across all normal-form games using a random games approach. The playing sequence – the order in which players update their actions – is essentially irrelevant in determining whether the dynamic converges to a Nash equilibrium in certain classes of games (e.g. in potential games) but, when evaluated across all possible games, convergence to equilibrium depends on the playing sequence in an extreme way. Our main asymptotic result shows that the best-response dynamic converges to a pure Nash equilibrium in a vanishingly small fraction of all (large) games when players take turns according to a fixed cyclic order. By contrast, when the playing sequence is random, the dynamic converges to a pure Nash equilibrium if one exists in almost all (large) games.
References:
| [1] | Alon N, Rudov K, Yariv L (2021) Dominance solvability in random games. arXiv:2105.10743 (arXiv preprint) |
| [2] | Amiet, B.; Collevecchio, A.; Hamza, K., When better is better than best, Oper Res Lett, 49, 2, 260-264 (2021) · Zbl 1525.91040 · doi:10.1016/j.orl.2021.01.009 |
| [3] | Amiet, B.; Collevecchio, A.; Scarsini, M.; Zhong, Z., Pure nash equilibria and best-response dynamics in random games, Math Oper Res, 20, 20 (2021) |
| [4] | Apt, KR; Simon, S., A classification of weakly acyclic games, Theory Decis, 78, 4, 501-524 (2015) · Zbl 1380.91013 · doi:10.1007/s11238-014-9436-1 |
| [5] | Arieli, I.; Babichenko, Y., Random extensive form games, J Econ Theory, 166, 517-535 (2016) · Zbl 1372.91009 · doi:10.1016/j.jet.2016.09.010 |
| [6] | Arratia, R.; Goldstein, L.; Gordon, L., Two moments suffice for Poisson approximations: the Chen-Stein method, Ann Probab, 17, 1, 9-25 (1989) · doi:10.1214/aop/1176991491 |
| [7] | Babichenko, Y., Best-reply dynamics in large binary-choice anonymous games, Games Econ Behav, 81, 130-144 (2013) · Zbl 1282.91038 · doi:10.1016/j.geb.2013.04.007 |
| [8] | Berg, J.; Weigt, M., Entropy and typical properties of nash equilibria in two-player games, EPL (Europhys Lett), 48, 2, 129-135 (1999) · doi:10.1209/epl/i1999-00456-2 |
| [9] | Berger N, Feldman M, Neiman O, Rosenthal M (2011) Dynamic inefficiency: Anarchy without stability. In: International symposium on algorithmic game theory. Springer, pp 57-68 · Zbl 1233.91065 |
| [10] | Blume, LE, The statistical mechanics of strategic interaction, Games Econ Behav, 5, 3, 387-424 (1993) · Zbl 0797.90123 · doi:10.1006/game.1993.1023 |
| [11] | Boucher, V., Selecting equilibria using best-response dynamics, Econ Bull, 37, 4, 2728-2734 (2017) |
| [12] | Candogan, O.; Ozdaglar, A.; Parrilo, PA, Dynamics in near-potential games, Games Econo Behav, 82, 66-90 (2013) · Zbl 1282.91048 · doi:10.1016/j.geb.2013.07.001 |
| [13] | Chauhan A, Lenzner P, Melnichenko A, Molitor L (2017) Selfish network creation with non-uniform edge cost. In: International symposium on algorithmic game theory. Springer, pp 160-172 · Zbl 1403.91062 |
| [14] | Christodoulou, G.; Mirrokni, VS; Sidiropoulos, A., Convergence and approximation in potential games, Theoret Comput Sci, 438, 13-27 (2012) · Zbl 1251.91008 · doi:10.1016/j.tcs.2012.02.033 |
| [15] | Cohen, JE, Cooperation and self-interest: pareto-inefficiency of Nash equilibria in finite random games, Proc Natl Acad Sci, 95, 17, 9724-9731 (1998) · Zbl 0911.90369 · doi:10.1073/pnas.95.17.9724 |
| [16] | Coucheney P, Durand S, Gaujal B, Touati C (2014) General revision protocols in best response algorithms for potential games. In: 2014 7th international conference on NETwork Games, COntrol and OPtimization (NetGCoop). IEEE, pp 239-246 · Zbl 1410.91020 |
| [17] | Daskalakis, C.; Dimakis, AG; Mossel, E., Connectivity and equilibrium in random games, Ann Appl Probab, 21, 3, 987-1016 (2011) · Zbl 1229.91079 · doi:10.1214/10-AAP715 |
| [18] | Dindoš, M.; Mezzetti, C., Better-reply dynamics and global convergence to Nash equilibrium in aggregative games, Games Econ Behav, 54, 2, 261-292 (2006) · Zbl 1125.91004 · doi:10.1016/j.geb.2004.12.001 |
| [19] | Dresher, M., Probability of a pure equilibrium point in \(n\)-person games, J Combin Theory, 8, 1, 134-145 (1970) · Zbl 0226.90048 · doi:10.1016/S0021-9800(70)80015-1 |
| [20] | Durand, S.; Garin, F.; Gaujal, B., Distributed best response dynamics with high playing rates in potential games, Perform Eval, 129, 40-59 (2019) · doi:10.1016/j.peva.2018.09.007 |
| [21] | Durand S, Gaujal B (2016) Complexity and optimality of the best response algorithm in random potential games. In: International symposium on algorithmic game theory. Springer, pp 40-51 · Zbl 1403.91025 |
| [22] | Fabrikant, A.; Jaggard, AD; Schapira, M., On the structure of weakly acyclic games, Theory Comput Syst, 53, 1, 107-122 (2013) · Zbl 1290.91016 · doi:10.1007/s00224-013-9457-0 |
| [23] | Feldman M, Snappir Y, Tamir T (2017) The efficiency of best-response dynamics. In: International symposium on algorithmic game theory. Springer, pp 186-198 · Zbl 1403.91066 |
| [24] | Feldman M, Tamir T (2012) Convergence of best-response dynamics in games with conflicting congestion effects. In: International workshop on internet and network economics. Springer, pp 496-503 |
| [25] | Friedman, JW; Mezzetti, C., Learning in games by random sampling, J Econ Theory, 98, 1, 55-84 (2001) · Zbl 0994.91006 · doi:10.1006/jeth.2000.2694 |
| [26] | Galla, T.; Farmer, JD, Complex dynamics in learning complicated games, Proc Natl Acad Sci, 110, 4, 1232-1236 (2013) · Zbl 1292.91033 · doi:10.1073/pnas.1109672110 |
| [27] | Goemans M, Mirrokni V, Vetta A (2005) Sink equilibria and convergence. In: 46th annual IEEE symposium on foundations of computer science (FOCS’05). IEEE, pp 142-151 |
| [28] | Goldberg, K.; Goldman, A.; Newman, M., The probability of an equilibrium point, J Res Natl Bureau Standards, 72, 2, 93-101 (1968) · Zbl 0164.20203 |
| [29] | Goldman, A., The probability of a saddlepoint, Am Math Mon, 64, 10, 729-730 (1957) · Zbl 0087.33804 · doi:10.2307/2309755 |
| [30] | Kash, IA; Friedman, EJ; Halpern, JY, Multiagent learning in large anonymous games, J Artif Intell Res, 40, 571-598 (2011) · Zbl 1216.68304 · doi:10.1613/jair.3213 |
| [31] | Kultti K, Salonen H, Vartiainen H (2011) Distribution of pure Nash equilibria in n-person games with random best responses. Technical Report 71, Aboa Centre for Economics. Discussion Papers |
| [32] | McLennan, A., The expected number of Nash equilibria of a normal form game, Econometrica, 73, 1, 141-174 (2005) · Zbl 1152.91326 · doi:10.1111/j.1468-0262.2005.00567.x |
| [33] | McLennan, A.; Berg, J., Asymptotic expected number of Nash equilibria of two-player normal form games, Games Econ Behav, 51, 2, 264-295 (2005) · Zbl 1139.91303 · doi:10.1016/j.geb.2004.10.008 |
| [34] | Mirrokni VS, Skopalik A (2009) On the complexity of Nash dynamics and sink equilibria. In: Proceedings of the 10th ACM conference on Electronic commerce, pp 1-10 |
| [35] | Monderer, D.; Shapley, LS, Potential games, Games Econ Behav, 14, 1, 124-143 (1996) · Zbl 0862.90137 · doi:10.1006/game.1996.0044 |
| [36] | Nisan N, Schapira M, Valiant G, Zohar A (2011) Best-response auctions. In: Proceedings of the 12th ACM conference on Electronic Commerce, pp 351-360 |
| [37] | Pangallo M, Heinrich T, Farmer JD (2019) Best reply structure and equilibrium convergence in generic games. Sci Adv 5(2):eaat1328 |
| [38] | Pei, T.; Takahashi, S., Rationalizable strategies in random games, Games Econ Behav, 118, 110-125 (2019) · Zbl 1429.91010 · doi:10.1016/j.geb.2019.08.011 |
| [39] | Powers, IY, Limiting distributions of the number of pure strategy Nash equilibria in \(n\)-person games, Int J Game Theory, 19, 3, 277-286 (1990) · Zbl 0725.90105 · doi:10.1007/BF01755478 |
| [40] | Quattropani M, Scarsini M (2020) Efficiency of equilibria in games with random payoffs. arXiv:2007.08518 (arXiv preprint) |
| [41] | Quint, T.; Shubik, M.; Yan, D.; Albers, W.; Güth, W.; Hammerstein, P.; Moldvanu, B.; van Damme, E., Dumb bugs vs. bright noncooperative players: a comparison, Understanding strategic interaction, 185-197 (1997), Berlin: Springer, Berlin · Zbl 0876.90107 · doi:10.1007/978-3-642-60495-9_15 |
| [42] | Rinott, Y.; Scarsini, M., On the number of pure strategy Nash equilibria in random games, Games Econ Behav, 33, 2, 274-293 (2000) · Zbl 0972.91011 · doi:10.1006/game.1999.0775 |
| [43] | Sanders, JB; Farmer, JD; Galla, T., The prevalence of chaotic dynamics in games with many players, Sci Rep, 8, 1, 4902 (2018) · doi:10.1038/s41598-018-22013-5 |
| [44] | Sandholm, WH, Population games and evolutionary dynamics (2010), New York: MIT Press, New York · Zbl 1208.91003 |
| [45] | Stanford, W., A note on the probability of \(k\) pure Nash equilibria in matrix games, Games Econ Behav, 9, 2, 238-246 (1995) · Zbl 0829.90139 · doi:10.1006/game.1995.1019 |
| [46] | Stanford, W., The limit distribution of pure strategy Nash equilibria in symmetric bimatrix games, Math Oper Res, 21, 3, 726-733 (1996) · Zbl 0871.90113 · doi:10.1287/moor.21.3.726 |
| [47] | Stanford, W., On the distribution of pure strategy equilibria in finite games with vector payoffs, Math Soc Sci, 33, 2, 115-127 (1997) · Zbl 0916.90285 · doi:10.1016/S0165-4896(96)00826-8 |
| [48] | Stanford, W., On the number of pure strategy Nash equilibria in finite common payoffs games, Econ Lett, 62, 1, 29-34 (1999) · Zbl 0916.90275 · doi:10.1016/S0165-1765(98)00219-5 |
| [49] | Swenson, B.; Murray, R.; Kar, S., On best-response dynamics in potential games, SIAM J Control Optim, 56, 4, 2734-2767 (2018) · Zbl 1391.93020 · doi:10.1137/17M1139461 |
| [50] | Takahashi, S., The number of pure Nash equilibria in a random game with nondecreasing best responses, Games Econ Behav, 63, 1, 328-340 (2008) · Zbl 1134.91326 · doi:10.1016/j.geb.2007.10.003 |
| [51] | Takahashi, S.; Yamamori, T., The pure Nash equilibrium property and the quasi-acyclic condition, Econ Bull, 3, 22, 1-6 (2002) |
| [52] | Wiese, SC; Heinrich, T., The frequency of convergent games under best-response dynamics, Dyn Games Appl, 12, 2, 689-700 (2022) · Zbl 1494.91012 · doi:10.1007/s13235-021-00401-3 |
| [53] | Young, HP, Individual strategy and social structure (1998), Princeton: Princeton University Press, Princeton · doi:10.1515/9780691214252 |
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.
