×

The price of anarchy and stability in general noisy best-response dynamics. (English) Zbl 1417.91105

Summary: Logit-response dynamics [C. Alós-Ferrer and N. Netzer, Games Econ. Behav. 68, No. 2, 413–427 (2010; Zbl 1207.91017)] are a rich and natural class of noisy best-response dynamics. In this work we revise the price of anarchy and the price of stability by considering the quality of long-run equilibria in these dynamics. Our results show that prior studies on simpler dynamics of this type can strongly depend on a sequential schedule of the players’ moves. In particular, a small noise by itself is not enough to improve the quality of equilibria as soon as other very natural schedules are used.

MSC:

91A22 Evolutionary games
91A10 Noncooperative games
91A43 Games involving graphs

Citations:

Zbl 1207.91017
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ackermann, H.; Berenbrink, P.; Fischer, S.; Hoefer, M., Concurrent imitation dynamics in congestion games, Distrib Comput, 29, 105-125, (2016) · Zbl 1358.91008 · doi:10.1007/s00446-014-0223-6
[2] Alós-Ferrer, C.; Netzer, N., The logit-response dynamics, Games Econ Behav, 68, 413-427, (2010) · Zbl 1207.91017 · doi:10.1016/j.geb.2009.08.004
[3] Alós-Ferrer, C.; Netzer, N., On the convergence of logit-response to (strict) Nash equilibria, Econ Theory Bull, 5, 1-8, (2017) · doi:10.1007/s40505-016-0104-1
[4] Anshelevich, E.; Dasgupta, A.; Kleinberg, J.; Tardos, É; Wexler, T.; Roughgarden, T., The price of stability for network design with fair cost allocation, SIAM J Comput, 38, 1602-1623, (2008) · Zbl 1173.91321 · doi:10.1137/070680096
[5] Asadpour, Arash; Saberi, Amin, On the Inefficiency Ratio of Stable Equilibria in Congestion Games, 545-552, (2009), Berlin, Heidelberg
[6] Auletta, V.; Ferraioli, D.; Pasquale, F.; Persiano, G., Mixing time and stationary expected social welfare of logit dynamics, Theory Comput Syst, 53, 3-40, (2013) · Zbl 1291.91026 · doi:10.1007/s00224-013-9458-z
[7] Auletta, V.; Ferraioli, D.; Pasquale, F.; Penna, P.; Persiano, G., Logit dynamics with concurrent updates for local interaction potential games, Algorithmica, 73, 511-546, (2015) · Zbl 1338.91035 · doi:10.1007/s00453-014-9959-4
[8] Blume, LE, The statistical mechanics of strategic interaction, Games Econ Behav, 5, 387-424, (1993) · Zbl 0797.90123 · doi:10.1006/game.1993.1023
[9] Blume LE (1998) Population games. Addison-Wesley, Reading
[10] Christodoulou, G.; Koutsoupias, E.; Spirakis, PG, On the performance of approximate equilibria in congestion games, Algorithmica, 61, 116-140, (2011) · Zbl 1219.91009 · doi:10.1007/s00453-010-9449-2
[11] Chung, Christine; Pyrga, Evangelia, Stochastic Stability in Internet Router Congestion Games, 183-195, (2009), Berlin, Heidelberg · Zbl 1262.91015 · doi:10.1007/978-3-642-04645-2_17
[12] Chung, Christine; Ligett, Katrina; Pruhs, Kirk; Roth, Aaron, The Price of Stochastic Anarchy, 303-314, (2008), Berlin, Heidelberg · Zbl 1136.91323 · doi:10.1007/978-3-540-79309-0_27
[13] Coucheney P, Durand S, Gaujal B, Touati C (2014) General revision protocols in best response algorithms for potential games. In: Network games, control and optimization (NetGCoop)
[14] Fanelli, Angelo; Moscardelli, Luca; Skopalik, Alexander, On the Impact of Fair Best Response Dynamics, 360-371, (2012), Berlin, Heidelberg · Zbl 1366.91007 · doi:10.1007/978-3-642-32589-2_33
[15] Finn, G.; Horowitz, E., A linear time approximation algorithm for multiprocessor scheduling, BIT Numer Math, 19, 312-320, (1979) · Zbl 0413.68038 · doi:10.1007/BF01930985
[16] Fotakis, D.; Kaporis, AC; Spirakis, PG, Atomic congestion games: fast, myopic and concurrent, Theory Comput Syst, 47, 38-59, (2010) · Zbl 1203.91119 · doi:10.1007/s00224-009-9198-2
[17] Kawase, Y.; Makino, K., Nash equilibria with minimum potential in undirected broadcast games, Theor Comput Sci, 482, 33-47, (2013) · Zbl 1291.91038 · doi:10.1016/j.tcs.2013.02.031
[18] Kleinberg R, Piliouras G, Tardos É (2009) Multiplicative updates outperform generic no-regret learning in congestion games. In: Proceedings of the 41st annual ACM symposium on theory of computing (STOC), pp 533-542 · Zbl 1304.91017
[19] Koutsoupias, E.; Papadimitriou, CH, Worst-case equilibria, Comput Sci Rev, 3, 65-69, (2009) · Zbl 1303.91012 · doi:10.1016/j.cosrev.2009.04.003
[20] Mamageishvili, Akaki; Mihalák, Matúš, Multicast Network Design Game on a Ring, 439-451, (2015), Cham · Zbl 1474.91024 · doi:10.1007/978-3-319-26626-8_32
[21] Mamageishvili, A.; Penna, P., Tighter bounds on the inefficiency ratio of stable equilibria in load balancing games, Oper. Res. Lett., 44, 645-648, (2016) · doi:10.1016/j.orl.2016.07.014
[22] Marden, JR; Shamma, JS, Revisiting log-linear learning: asynchrony, completeness and payoff-based implementation, Games Econ Behav, 75, 788-808, (2012) · Zbl 1239.91017 · doi:10.1016/j.geb.2012.03.006
[23] Pradelski, BSR; Young, HP, Learning efficient Nash equilibria in distributed systems, Games Econ Behav, 75, 882-897, (2012) · Zbl 1239.91018 · doi:10.1016/j.geb.2012.02.017
[24] Roughgarden T (2009) Intrinsic robustness of the price of anarchy. In: Proceedings of the 41st ACM symposium on theory of computing (STOC), pp 513-522 · Zbl 1304.91019
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.