Best-response dynamics in two-person random games with correlated payoffs. (English) Zbl 07874123
Summary: We consider finite two-player normal form games with random payoffs. Player A’s payoffs are i.i.d. from a uniform distribution. Given \(p\in [0,1]\), for any action profile, player B’s payoff coincides with player A’s payoff with probability \(p\) and is i.i.d. from the same uniform distribution with probability \(1-p\). This model interpolates the model of i.i.d. random payoff used in most of the literature and the model of random potential games. First we study the number of pure Nash equilibria in the above class of games. Then we show that, for any positive \(p\), asymptotically in the number of available actions, best response dynamics reaches a pure Nash equilibrium with high probability.
MSC:
| 91A05 | 2-person games |
| 91A14 | Potential and congestion games |
| 91A15 | Stochastic games, stochastic differential games |
References:
| [1] | Alon, N.; Rudov, K.; Yariv, L., Dominance solvability in random games, 2021, Technical report |
| [2] | Amiet, B.; Collevecchio, A.; Hamza, K., When “better” is better than “best”, Oper. Res. Lett., 49, 2, 260-264, 2021 · Zbl 1525.91040 |
| [3] | Amiet, B.; Collevecchio, A.; Scarsini, M.; Zhong, Z., Pure Nash equilibria and best-response dynamics in random games, Math. Oper. Res., 46, 4, 1552-1572, 2021 · Zbl 1483.91028 |
| [4] | Baldi, P.; Rinott, Y.; Stein, C., A normal approximation for the number of local maxima of a random function on a graph, (Probability, Statistics, and Mathematics, 1989, Academic Press, Inc.), 59-81 · Zbl 0704.62018 |
| [5] | Candogan, O.; Menache, I.; Ozdaglar, A.; Parrilo, P. A., Flows and decompositions of games: harmonic and potential games, Math. Oper. Res., 36, 3, 474-503, 2011 · Zbl 1239.91006 |
| [6] | Candogan, O.; Ozdaglar, A.; Parrilo, P. A., Dynamics in near-potential games, Games Econ. Behav., 82, 66-90, 2013 · Zbl 1282.91048 |
| [7] | Coucheney, P.; Durand, S.; Gaujal, B.; Touati, C., General revision protocols in best response algorithms for potential games, (Netwok Games, Control and OPtimization (NetGCoop), 2014, IEEE Explore: IEEE Explore Trento, Italy) |
| [8] | Durand, S.; Garin, F.; Gaujal, B., Distributed best response dynamics with high playing rates in potential games, Perform. Eval., 129, 40-59, 2019 |
| [9] | Durand, S.; Gaujal, B., Complexity and optimality of the best response algorithm in random potential games, (Algorithmic Game Theory. Algorithmic Game Theory, Lecture Notes in Comput. Sci., vol. 9928, 2016, Springer: Springer Berlin), 40-51 · Zbl 1403.91025 |
| [10] | Fabrikant, A.; Jaggard, A. D.; Schapira, M., On the structure of weakly acyclic games, Theory Comput. Syst., 53, 1, 107-122, 2013 · Zbl 1290.91016 |
| [11] | Galla, T.; Farmer, J. D., Complex dynamics in learning complicated games, Proc. Natl. Acad. Sci. USA, 110, 4, 1232-1236, 2013 · Zbl 1292.91033 |
| [12] | Goemans, M.; Mirrokni, V.; Vetta, A., Sink equilibria and convergence, (46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05), 2005), 142-151 |
| [13] | Harsanyi, J. C., Oddness of the number of equilibrium points: a new proof, Int. J. Game Theory, 2, 235-250, 1973 · Zbl 0274.90085 |
| [14] | Heinrich, T.; Jang, Y.; Mungo, L.; Pangallo, M.; Scott, A.; Tarbush, B.; Wiese, S., Best-response dynamics, playing sequences, and convergence to equilibrium in random games, Int. J. Game Theory, 52, 3, 703-735, 2023 · Zbl 1522.91037 |
| [15] | Johnston, T.; Savery, M.; Scott, A.; Tarbush, B., Game connectivity and adaptive dynamics, 2023, Technical report |
| [16] | Karlin, A. R.; Peres, Y., Game Theory, Alive, 2017, American Mathematical Society: American Mathematical Society Providence, RI · Zbl 1416.91001 |
| [17] | Monderer, D.; Shapley, L. S., Potential games, Games Econ. Behav., 14, 1, 124-143, 1996 · Zbl 0862.90137 |
| [18] | Nash, J., Non-cooperative games, Ann. Math. (2), 54, 286-295, 1951 · Zbl 0045.08202 |
| [19] | Nash, J. F., Equilibrium points in n-person games, Proc. Natl. Acad. Sci. USA, 36, 48-49, 1950 · Zbl 0036.01104 |
| [20] | Ogryczak, W.; Ruszczyński, A., From stochastic dominance to mean-risk models: semideviations as risk measures, Eur. J. Oper. Res., 116, 1, 33-50, 1999 · Zbl 1007.91513 |
| [21] | Pangallo, M.; Heinrich, T.; Farmer, J. D., Best reply structure and equilibrium convergence in generic games, Sci. Adv., 5, 2, Article eaat1328 pp., 2019 |
| [22] | Pei, T.; Takahashi, S., Rationalizable strategies in random games, Games Econ. Behav., 118, 110-125, 2019 · Zbl 1429.91010 |
| [23] | Powers, I. Y., 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 |
| [24] | 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 |
| [25] | Rosenthal, R. W., A class of games possessing pure-strategy Nash equilibria, Int. J. Game Theory, 2, 65-67, 1973 · Zbl 0259.90059 |
| [26] | Sanders, J. B.T.; Farmer, J. D.; Galla, T., The prevalence of chaotic dynamics in games with many players, Sci. Rep., 8, 1, 4902, 2018 |
| [27] | 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 |
| [28] | Wiese, S. C.; Heinrich, T., The frequency of convergent games under best-response dynamics, Dyn. Games Appl., 12, 2, 689-700, 2022 · Zbl 1494.91012 |
| [29] | Wilson, R., Computing equilibria of N-person games, SIAM J. Appl. Math., 21, 80-87, 1971 · Zbl 0205.23204 |
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.
