Routing Without Regret: On Convergence to Nash Equilibria of Regret-Minimizing Algorithms in Routing Games

by Avrim Blum, Eyal Even-Dar, and Katrina Ligett

Theory of Computing, Volume 6(8), pp. 179-199, 2010

Bibliography with links to cited articles

[1]   Jacob Abernethy, Elad Hazan, and Alexander Rakhlin: Competing in the dark: An efficient algorithm for bandit linear optimization. In Proc. 21st Ann. Conf. Learning Theory (COLT). Springer, 2008.

[2]   Baruch Awerbuch, Yossi Azar, Amir Epstein, Vahab Seyed Mirrokni, and Alexander Skopalik: Fast convergence to nearly optimal solutions in potential games. In Proc. 9th ACM Conf. Electronic Commerce (EC), pp. 264–273. ACM Press, 2008. [doi:10.1145/1386790.1386832].

[3]   Baruch Awerbuch and Robert D. Kleinberg: Adaptive routing with end-to-end feedback: Distributed learning and geometric approaches. In Proc. 36th STOC, pp. 45–53. ACM Press, 2004. [doi:10.1145/1007352.1007367].

[4]   Yossi Azar: Online Algorithms: The State of the Art, chapter “On-line load balancing”, pp. 178–195. Springer, 1998.

[5]   M. Beckmann, C. B. McGuire, and C. B. Winsten: Studies in the Economics of Transportation. Yale University Press, 1956.

[6]   Petra Berenbrink, Tom Friedetzky, Leslie Ann Goldberg, Paul W. Goldberg, Zengjian Hu, and Russell Martin: Distributed selfish load balancing. SIAM J. Comput., 37(4):1163–1181, 2007. [doi:10.1137/060660345].

[7]   Avrim Blum, MohammadTaghi Hajiaghayi, Katrina Ligett, and Aaron Roth: Regret minimization and the price of total anarchy. In Proc. 40th STOC, pp. 373–382. ACM Press, 2008. [doi:10.1145/1374376.1374430].

[8]   Nicolò Cesa-Bianchi, Yoav Freund, David Haussler, David P. Helmbold, Robert E. Schapire, and Manfred K. Warmuth: How to use expert advice. J. ACM, 44(3):427–485, 1997. [doi:10.1145/258128.258179].

[9]   George Christodoulou, Elias Koutsoupias, and Paul G. Spirakis: On the performance of approximate equilibria in congestion games. In Proc. 17th European Symp. Algorithms (ESA’09), pp. 251–262. Springer, 2009. [doi:10.1007/978-3-642-04128-0_22].

[10]   Artur Czumaj, Piotr Krysta, and Berthold Vöcking: Selfish traffic allocation for server farms. SIAM J. Comput., 39:1957–1987, 2010. [doi:10.1137/070693862].

[11]   Artur Czumaj and Berthold Vöcking: Tight bounds for worst-case equilibria. ACM Trans. Algorithms, 3(1):4, 2007. [doi:10.1145/1186810.1186814].

[12]   Eyal Even-Dar, Alex Kesselman, and Yishay Mansour: Convergence time to Nash equilibria. In Proc. 30th Intern. Colloq. Autom. Lang. Program. (ICALP), number 2719 in LNCS, pp. 193–193. Springer, 2003. [doi:10.1007/3-540-45061-0_41].

[13]   Eyal Even-Dar and Yishay Mansour: Fast convergence of selfish rerouting. In Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms (SODA), pp. 772–781. ACM Press, 2005. [ACM:1070432.1070541].

[14]   Eyal Even-Dar, Yishay Mansour, and Uri Nadav: On the convergence of regret minimization dynamics in concave games. In Proc. 41st STOC, pp. 523–532. ACM Press, 2009. [doi:10.1145/1536414.1536486].

[15]   Alex Fabrikant, Ankur Luthra, Elitza Maneva, Christos H. Papadimitriou, and Scott Shenker: On a network creation game. In Proc. 22nd Symp. Principles of Distrib. Comput. (PODC), pp. 347–351. ACM Press, 2003. [doi:10.1145/872035.872088].

[16]   Simon Fischer, Harald Räcke, and Berthold Vöcking: Fast convergence to Wardrop equilibria by adaptive sampling methods. In Proc. 38th STOC, pp. 653–662. ACM Press, 2006. [doi:10.1145/1132516.1132608].

[17]   Simon Fischer and Berthold Vöcking: On the evolution of selfish routing. In Proc. 12th European Symp. Algorithms (ESA), number 3221 in LNCS, pp. 323–334. Springer, 2004. [doi:10.1007/978-3-540-30140-0_30].

[18]   Simon Fischer and Berthold Vöcking: Adaptive routing with stale information. Theoretical Computer Science, 410(36):3357–3371, 2009. [doi:10.1016/j.tcs.2008.01.055].

[19]   Dean P. Foster and Rakesh V. Vohra: Calibrated learning and correlated equilibrium. Games Econom. Behav., 21(1–2):40–55, 1997. [doi:10.1006/game.1997.0595].

[20]    Yoav Freund and Robert E. Schapire: A decision-theoretic generalization of on-line learning and an application to boosting. J. Comput. System Sci., 55(1):119–139, 1997. [doi:10.1006/jcss.1997.1504].

[21]   Yoav Freund and Robert E. Schapire: Adaptive game playing using multiplicative weights. Games Econom. Behav., 29:79–103, 1999. [doi:10.1006/game.1999.0738].

[22]   Paul W. Goldberg: Bounds for the convergence rate of randomized local search in a multiplayer load-balancing game. In Proc. 23rd Ann. ACM Symp. Principles of Distrib. Comput. (PODC), pp. 131–140. ACM Press, 2004. [doi:10.1145/1011767.1011787].

[23]   J.F. Hannan: Approximation to Bayes risk in repeated play. In M. Dresher, A.W. Tucker, and P. Wolfe, editors, Contributions to the Theory of Games, volume III, pp. 97–139. Princeton University Press, 1957.

[24]   Sergiu Hart and Andreu Mas-Colell: A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68(5):1127–1150, 2000. [doi:10.1111/1468-0262.00153].

[25]   Adam Kalai and Santosh Vempala: Efficient algorithms for online decision problems. J. Comput. System Sci., 71(3):291–307, 2005. [doi:10.1016/j.jcss.2004.10.016].

[26]   Robert Kleinberg, Georgios Pillouras, and Éva Tardos: Multiplicative updates outperform generic no-regret learning in congestion games. In Proc. 41st STOC. ACM Press, 2009. [doi:10.1145/1536414.1536487].

[27]   Elias Koutsoupias and Christos Papadimitriou: Worst-case equilibria. Comput. Sci. Rev., 3(2):65–69, 2009. [doi:10.1016/j.cosrev.2009.04.003].

[28]   N. Littlestone and M. K. Warmuth: The weighted majority algorithm. Inform. and Comput., 108(2):212–261, 1994. [doi:10.1006/inco.1994.1009].

[29]    H. Brendan McMahan and Avrim Blum: Online geometric optimization in the bandit setting against an adaptive adversary. In Proc. 17th Ann. Conf. Learning Theory (COLT), number 3120 in LNCS, pp. 109–123. Springer, 2004. [Springer:38p3f4h61cgy7gg7].

[30]   Igal Milchtaich: Congestion games with player-specific payoff functions. Games Econom. Behav., 13(1):111–124, 1996. [doi:10.1006/game.1996.0027].

[31]   Igal Milchtaich: Generic uniqueness of equilibrium in large crowding games. Math. Oper. Res., 25(3):349–364, 2000. [doi:10.1287/moor.25.3.349.12220].

[32]   Abraham Neyman: Correlated equilibrium and potential games. Internat. J. Game Theory, 26(2):223–227, 1997. [doi:10.1007/BF01295851].

[33]   Tim Roughgarden: Intrinsic robustness of the price of anarchy. In Proc. 41st STOC, pp. 513–522. ACM Press, 2009. [doi:10.1145/1536414.1536485].

[34]   Tim Roughgarden and Éva Tardos: How bad is selfish routing? J. ACM, 49(2):236–259, 2002. [doi:10.1145/506147.506153].

[35]   Tim Roughgarden and Éva Tardos: Bounding the inefficiency of equilibria in nonatomic congestion games. Games Econom. Behav., 47(2):389–403, 2004. [doi:10.1016/j.geb.2003.06.004].

[36]   William H. Sandholm: Potential games with continuous player sets. J. Econom. Theory, 97(1):81–108, 2001. [doi:10.1006/jeth.2000.2696].

[37]   David Schmeidler: Equilibrium points of nonatomic games. J. Stat. Phys., 7(4):295–300, 1973. [doi:10.1007/BF01014905].

[38]   Eiji Takimoto and Manfred K. Warmuth: Path kernels and multiplicative updates. J. Mach. Learn. Res., 4:818, 2003.

[39]   Martin Zinkevich: Online convex programming and generalized infinitesimal gradient ascent. In Proc. 20th Intern. Conf. Mach. Learn. (ICML), pp. 928–936. AAAI Press, 2003.

[40]   Martin Zinkevich: Theoretical guarantees for algorithms in multi-agent settings. Technical Report CMU-CS-04-161, Carnegie Mellon University, 2004.