skip to main content
10.1145/1146381.1146392acmconferencesArticle/Chapter ViewAbstractPublication PagespodcConference Proceedingsconference-collections
Article

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

Published: 23 July 2006 Publication History

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]
B. Awerbuch and R. Kleinberg. Adaptive routing with end-to-end feedback: Distributed learning and geometric approaches. In Proceedings of the 36th ACM Symposium on Theory of Computing, 2004.
[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]
P. Berenbrink, T. Friedetzky, L. A. Goldberg, P. Goldberg, Z. Hu, and R. Martin. Distributed selfish load balancing. In Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006.
[5]
N. Cesa-Bianchi, Y. Freund, D. Helmbold, D. Haussler, R. Schapire, and M. Warmuth. How to use expert advice. JACM, 44(3):427--485, 1997.
[6]
A. Czumaj, P. Krysta, and B. Vöcking. Selfish traffic allocation for server farms. In Proc. 34th Annual ACM Symp. Theory of Computing, pages 287--296, 2002.
[7]
A. Czumaj and B. Vöcking. Tight bounds on worst case equilibria. In Proc. 13th Annual ACM-SIAM Symp. Discrete Algorithms, pages 413--420, 2002.
[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]
E. Even-Dar and Y. Mansour. Fast convergence of selfish rerouting. In Proc. 16th Annual ACM-SIAM Symp. Discrete Algorithms, pages 772--781, 2005.
[10]
A. Fabrikant, A. Luthra, E. Maneva, C. H. Papadimitriou, and S. Shenker. On a network creation game. In Proceedings of the 22nd Annual Symposium on Principles of Distributed Computing (PODC), pages 347--351, 2003.
[11]
S. Fischer, H. Raecke, and B. Vöcking. Fast convergence to Wardrop equilibria by adaptive sampling methods. In Proceedings of 38th ACM Symposium on Theory of Computing (STOC), 2006.
[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]
S. Fischer and B. Vöcking. Adaptive routing with stale information. In Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing (PODC), 2005.
[14]
D. P. Foster and R. V. Vohra. Calibrated learning and correlated equilibrium. Games and Economic Behavior, 1997.
[15]
Y. Freund and R. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. J. Comput. Syst. Sci., 55(1):119--139, 1997.
[16]
Y. Freund and R. Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29:79--103, 1999.
[17]
P. Goldberg. Bounds for the convergence rate of randomized local search in multiplayer games, uniform resource sharing game. In Proceedings of the Twenty-Third PODC, pages 131--144, 2004.
[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]
A. Kalai and S. Vempala. Efficient algorithms for on-line optimization. In Journal of Computer and System Sciences, 71(3): 291--307, 2005.
[21]
E. Koutsoupias and C. H. Papadimitriou. Worst-case equilibria. In Proceedings of 16th STACS, pages 404--413, 1999.
[22]
N. Littlestone and M. K. Warmuth. The weighted majority algorithm. Information and Computation, 108(2):212--261, 1994.
[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. On the severity of Braess's paradox: Designing networks for selfish users is hard. In 42nd Annual IEEE Symposium on Foundations of Computer Science, 2001.
[26]
T. Roughgarden and E. Tardos. How bad is selfish routing? Journal of the ACM, 49(2):236--259, 2002.
[27]
E. Takimoto and M. K. Warmuth. Path kernels and multiplicative updates. In Proc. 15th Annual Conference on Learning Theory (COLT), 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.

Cited By

View all
  • (2023)Efficient Stackelberg Strategies for Finitely Repeated GamesProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598695(643-651)Online publication date: 30-May-2023
  • (2023)On the Resilience of Traffic Networks under Non-Equilibrium Learning2023 American Control Conference (ACC)10.23919/ACC55779.2023.10156139(3484-3489)Online publication date: 31-May-2023
  • (2022)Solutions to the routing problem: towards trustworthy autonomous vehiclesArtificial Intelligence Review10.1007/s10462-021-10131-y55:7(5445-5484)Online publication date: 8-Jan-2022
  • Show More Cited By

Index Terms

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

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing
    July 2006
    230 pages
    ISBN:1595933840
    DOI:10.1145/1146381
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 23 July 2006

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. game theory
    2. network games

    Qualifiers

    • Article

    Conference

    PODC06

    Acceptance Rates

    Overall Acceptance Rate 740 of 2,477 submissions, 30%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)17
    • Downloads (Last 6 weeks)1
    Reflects downloads up to 13 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2023)Efficient Stackelberg Strategies for Finitely Repeated GamesProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598695(643-651)Online publication date: 30-May-2023
    • (2023)On the Resilience of Traffic Networks under Non-Equilibrium Learning2023 American Control Conference (ACC)10.23919/ACC55779.2023.10156139(3484-3489)Online publication date: 31-May-2023
    • (2022)Solutions to the routing problem: towards trustworthy autonomous vehiclesArtificial Intelligence Review10.1007/s10462-021-10131-y55:7(5445-5484)Online publication date: 8-Jan-2022
    • (2021)The convergence rate of regularized learning in gamesProceedings of the 35th International Conference on Neural Information Processing Systems10.5555/3540261.3541996(22655-22666)Online publication date: 6-Dec-2021
    • (2021)Who leads and who follows in strategic classification?Proceedings of the 35th International Conference on Neural Information Processing Systems10.5555/3540261.3541430(15257-15269)Online publication date: 6-Dec-2021
    • (2021)Fast routing under uncertaintyProceedings of the 35th International Conference on Neural Information Processing Systems10.5555/3540261.3541388(14708-14720)Online publication date: 6-Dec-2021
    • (2020)Tight last-iterate convergence rates for no-regret learning in multi-player gamesProceedings of the 34th International Conference on Neural Information Processing Systems10.5555/3495724.3497468(20766-20778)Online publication date: 6-Dec-2020
    • (2020)Intention-Aware Model to Support Agent Deliberation in a Large-Scale Dynamic Multi-Agent ApplicationArtificial Intelligence XXXVII10.1007/978-3-030-63799-6_23(301-314)Online publication date: 8-Dec-2020
    • (2020)Routing Model EvaluatorAdvances in Practical Applications of Agents, Multi-Agent Systems, and Trustworthiness. The PAAMS Collection10.1007/978-3-030-49778-1_3(30-41)Online publication date: 7-Oct-2020
    • (2019)Online Optimisation for Online Learning and Control - From No-Regret to Generalised Error Convergence2019 18th European Control Conference (ECC)10.23919/ECC.2019.8795939(2480-2485)Online publication date: Jun-2019
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media