Routing without regret: on convergence to nash equilibria of regret-minimizing algorithms in routing games

ABSTRACT

There has been substantial work developing simple, efficient no-regret algorithms for a wide class of repeated decision-making problems including online routing. These are adaptive strategies an individual can use that give strong guarantees on performance even in adversarially-changing environments. There has also been substantial work on analyzing properties of Nash equilibria in routing games. In this paper, we consider the question: if each player in a routing game uses a no-regret strategy, will behavior converge to a Nash equilibrium? In general games the answer to this question is known to be no in a strong sense, but routing games have substantially more structure.In this paper we show that in the Wardrop setting of multicommodity flow and infinitesimal agents, behavior will approach Nash equilibrium (formally, on most days, the cost of the flow will be close to the cost of the cheapest paths possible given that flow) at a rate that depends polynomially on the players' regret bounds and the maximum slope of any latency function. We also show that price-of-anarchy results may be applied to these approximate equilibria, and also consider the finite-size (non-infinitesimal) load-balancing model of Azar [2].

REFERENCES

• 1: Baruch Awerbuch , Robert D. Kleinberg, Adaptive routing with end-to-end feedback: distributed learning and geometric approaches, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007367]
• 2: Y. Azar. On-line Load Balancing. Online Algorithms - The State of the Art, pages 178--195, Springer, 1998.
• 3: M. Beckmann, C. B. McGuire, and C. B. Winsten. Studies in the Economics of Transportation. Yale University Press, 1956.
• 4: Petra Berenbrink , Tom Friedetzky , Leslie Ann Goldberg , Paul Goldberg , Zengjian Hu , Russell Martin, Distributed selfish load balancing, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.354-363, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109597]
• 5: Nicolò Cesa-Bianchi , Yoav Freund , David Haussler , David P. Helmbold , Robert E. Schapire , Manfred K. Warmuth, How to use expert advice, Journal of the ACM (JACM), v.44 n.3, p.427-485, May 1997 [doi>10.1145/258128.258179]
• 6: Artur Czumaj , Piotr Krysta , Berthold Vöcking, Selfish traffic allocation for server farms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509952]
• 7: Artur Czumaj , Berthold Vöcking, Tight bounds for worst-case equilibria, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.413-420, January 06-08, 2002, San Francisco, California
• 8: E. Even-Dar, A. Kesselman, and Y. Mansour. Convergence time to Nash equilibria. In 30th International Conference on Automata, Languages and Programming (ICALP), pages 502--513, 2003.
• 9: Eyal Even-Dar , Yishay Mansour, Fast convergence of selfish rerouting, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 10: Alex Fabrikant , Ankur Luthra , Elitza Maneva , Christos H. Papadimitriou , Scott Shenker, On a network creation game, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.347-351, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872088]
• 11: Simon Fischer , Harald Räcke , Berthold Vöcking, Fast convergence to Wardrop equilibria by adaptive sampling methods, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132608]
• 12: S. Fischer and B. Vöcking. On the evolution of selfish routing. In Proc. 12th Annural European Symposium on Algorithms (ESA), pages 323--334, 2004.
• 13: Simon Fischer , Berthold Vöcking, Adaptive routing with stale information, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073868]
• 14: D. P. Foster and R. V. Vohra. Calibrated learning and correlated equilibrium. Games and Economic Behavior, 1997.
• 15: Yoav Freund , Robert E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences, v.55 n.1, p.119-139, Aug. 1997 [doi>10.1006/jcss.1997.1504 ]
• 16: Y. Freund and R. Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29:79--103, 1999.
• 17: Paul W. Goldberg, Bounds for the convergence rate of randomized local search in a multiplayer load-balancing game, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011787]
• 18: J. Hannan. Approximation to Bayes risk in repeated play. In M. Dresher, A. Tucker, and P. Wolfe, editors, Contributions to the Theory of Games, volume III, pages 97--139. Princeton University Press, 1957.
• 19: S. Hart and A. Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 2000.
• 20: Adam Kalai , Santosh Vempala, Efficient algorithms for online decision problems, Journal of Computer and System Sciences, v.71 n.3, p.291-307, October 2005 [doi>10.1016/j.jcss.2004.10.016]
• 21: E. Koutsoupias and C. H. Papadimitriou. Worst-case equilibria. In Proceedings of 16th STACS, pages 404--413, 1999.
• 22: Nick Littlestone , Manfred K. Warmuth, The weighted majority algorithm, Information and Computation, v.108 n.2, p.212-261, Feb. 1, 1994 [doi>10.1006/inco.1994.1009 ]
• 23: H. McMahan and A. Blum. Online geometric optimization in the bandit setting against an adaptive adversary. In Proc. 17th Annual Conference on Learning Theory (COLT), pages 109--123, 2004.
• 24: I. Milchtaich. Congestion games with player-specific payoff functions. Games and Economic Behavior, 13:111--124, 1996.
• 25: T. Roughgarden, Designing Networks for Selfish Users is Hard, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.472, October 14-17, 2001
• 26: Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002 [doi>10.1145/506147.506153]
• 27: Eiji Takimoto , Manfred K. Warmuth, Path Kernels and Multiplicative Updates, Proceedings of the 15th Annual Conference on Computational Learning Theory, p.74-89, July 08-10, 2002
• 28: J. G. Wardrop. Some theoretical aspects of road traffic research. In Proceedings of the Institute of Civil Engineers, Pt. II, volume 1, pages 325--378, 1952.
• 29: M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning, pages 928--936, 2003.
• 30: M. Zinkevich. Theoretical guarantees for algorithms in multi-agent settings. Technical Report CMU-CS-04-161, Carnegie Mellon University, 2004.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Theory

Keywords:
game theory, network games