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. http://colt2008.cs.helsinki.fi/papers/123-Abernethy.pdf.
[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. http://mlr.csail.mit.edu/papers/volume4/takimoto03a/takimoto03a.pdf.
[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.