IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v68y2020i2p411-434.html
   My bibliography  Save this article

When Is Selfish Routing Bad? The Price of Anarchy in Light and Heavy Traffic

Author

Listed:
  • Riccardo Colini-Baldeschi

    (Core Data Science Group, Facebook, Inc., London W1T 1FB, United Kingdom)

  • Roberto Cominetti

    (Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibáñez, 7941169 Santiago, Chile)

  • Panayotis Mertikopoulos

    (Université Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France)

  • Marco Scarsini

    (Dipartimento di Economia e Finanza, Libera Università Internazionale degli Studi Sociali “Guido Carli,” 00197 Rome, Italy)

Abstract

This paper examines the behavior of the price of anarchy as a function of the traffic inflow in nonatomic congestion games with multiple origin/destination (O/D) pairs. Empirical studies in real-world networks show that the price of anarchy is close to 1 in both light and heavy traffic, thus raising the following question: can these observations be justified theoretically? We first show that this is not always the case: the price of anarchy may remain a positive distance away from 1 for all values of the traffic inflow, even in simple three-link networks with a single O/D pair and smooth, convex costs. On the other hand, for a large class of cost functions (including all polynomials) and inflow patterns, the price of anarchy does converge to 1 in both heavy and light traffic, irrespective of the network topology and the number of O/D pairs in the network. We also examine the rate of convergence of the price of anarchy, and we show that it follows a power law whose degree can be computed explicitly when the network’s cost functions are polynomials.

Suggested Citation

  • Riccardo Colini-Baldeschi & Roberto Cominetti & Panayotis Mertikopoulos & Marco Scarsini, 2020. "When Is Selfish Routing Bad? The Price of Anarchy in Light and Heavy Traffic," Operations Research, INFORMS, vol. 68(2), pages 411-434, March.
    • Handle: RePEc:inm:oropre:v:68:y:2020:i:2:p:411-434
    DOI: 10.1287/opre.2019.1894
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/opre.2019.1894
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2019.1894?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Roughgarden, Tim & Tardos, Eva, 2004. "Bounding the inefficiency of equilibria in nonatomic congestion games," Games and Economic Behavior, Elsevier, vol. 47(2), pages 389-403, May.
    2. José R. Correa & Andreas S. Schulz & Nicolás E. Stier-Moses, 2007. "Fast, Fair, and Efficient Flows in Networks," Operations Research, INFORMS, vol. 55(2), pages 215-225, April.
    3. José R. Correa & Andreas S. Schulz & Nicolás E. Stier-Moses, 2004. "Selfish Routing in Capacitated Networks," Mathematics of Operations Research, INFORMS, vol. 29(4), pages 961-976, November.
    4. Correa, José R. & Schulz, Andreas S. & Stier-Moses, Nicolás E., 2008. "A geometric approach to the price of anarchy in nonatomic congestion games," Games and Economic Behavior, Elsevier, vol. 64(2), pages 457-469, November.
    5. Shaler Stidham, 2014. "The Price of Anarchy for a Network of Queues in Heavy Traffic," International Series in Operations Research & Management Science, in: P. Simin Pulat & Subhash C. Sarin & Reha Uzsoy (ed.), Essays in Production, Project Planning and Scheduling, edition 127, chapter 5, pages 91-121, Springer.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Chen, Enxian & Qiao, Lei & Sun, Xiang & Sun, Yeneng, 2022. "Robust perfect equilibrium in large games," Journal of Economic Theory, Elsevier, vol. 201(C).
    2. Chinmay Maheshwari & Kshitij Kulkarni & Druv Pai & Jiarui Yang & Manxi Wu & Shankar Sastry, 2024. "Congestion Pricing for Efficiency and Equity: Theory and Applications to the San Francisco Bay Area," Papers 2401.16844, arXiv.org.
    3. Zijun Wu & Rolf H. Möhring & Yanyan Chen & Dachuan Xu, 2021. "Selfishness Need Not Be Bad," Operations Research, INFORMS, vol. 69(2), pages 410-435, March.
    4. Cheng, Qixiu & Lin, Yuqian & Zhou, Xuesong (Simon) & Liu, Zhiyuan, 2024. "Analytical formulation for explaining the variations in traffic states: A fundamental diagram modeling perspective with stochastic parameters," European Journal of Operational Research, Elsevier, vol. 312(1), pages 182-197.
    5. Zijun Wu & Rolf H. Moehring & Chunying Ren & Dachuan Xu, 2020. "A convergence analysis of the price of anarchy in atomic congestion games," Papers 2007.14769, arXiv.org, revised Dec 2021.
    6. Wang, Aihu & Tang, Yuanhua & Mohmand, Yasir Tariq & Xu, Pei, 2022. "Modifying link capacity to avoid Braess Paradox considering elastic demand," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 605(C).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Gaëtan Fournier & Marco Scarsini, 2014. "Hotelling Games on Networks: Efficiency of Equilibria," Documents de travail du Centre d'Economie de la Sorbonne 14033, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne.
    2. Feng, Zengzhe & Gao, Ziyou & Sun, Huijun, 2014. "Bounding the inefficiency of atomic splittable selfish traffic equilibria with elastic demands," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 63(C), pages 31-43.
    3. José R. Correa & Nicolás Figueroa & Nicolás E. Stier-Moses, 2008. "Pricing with markups in industries with increasing marginal costs," Documentos de Trabajo 256, Centro de Economía Aplicada, Universidad de Chile.
    4. Correa, José R. & Schulz, Andreas S. & Stier-Moses, Nicolás E., 2008. "A geometric approach to the price of anarchy in nonatomic congestion games," Games and Economic Behavior, Elsevier, vol. 64(2), pages 457-469, November.
    5. Roberto Cominetti & José R. Correa & Nicolás E. Stier-Moses, 2009. "The Impact of Oligopolistic Competition in Networks," Operations Research, INFORMS, vol. 57(6), pages 1421-1437, December.
    6. Knight, Vincent A. & Harper, Paul R., 2013. "Selfish routing in public services," European Journal of Operational Research, Elsevier, vol. 230(1), pages 122-132.
    7. Wang, Chenlan & Doan, Xuan Vinh & Chen, Bo, 2014. "Price of anarchy for non-atomic congestion games with stochastic demands," Transportation Research Part B: Methodological, Elsevier, vol. 70(C), pages 90-111.
    8. Chenlan Wang & Xuan Vinh Doan & Bo Chen, 2022. "Atomic congestion games with random players: network equilibrium and the price of anarchy," Journal of Combinatorial Optimization, Springer, vol. 44(3), pages 2123-2142, October.
    9. Chenlan Wang & Xuan Vinh Doan & Bo Chen, 0. "Atomic congestion games with random players: network equilibrium and the price of anarchy," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-20.
    10. Sandholm, William H., 2015. "Population Games and Deterministic Evolutionary Dynamics," Handbook of Game Theory with Economic Applications,, Elsevier.
    11. E. Nikolova & N. E. Stier-Moses, 2014. "A Mean-Risk Model for the Traffic Assignment Problem with Stochastic Travel Times," Operations Research, INFORMS, vol. 62(2), pages 366-382, April.
    12. Raimondo, Roberto, 2020. "Pathwise smooth splittable congestion games and inefficiency," Journal of Mathematical Economics, Elsevier, vol. 86(C), pages 15-23.
    13. Parilina, Elena & Sedakov, Artem & Zaccour, Georges, 2017. "Price of anarchy in a linear-state stochastic dynamic game," European Journal of Operational Research, Elsevier, vol. 258(2), pages 790-800.
    14. Balmaceda, Felipe & Balseiro, Santiago R. & Correa, José R. & Stier-Moses, Nicolás E., 2016. "Bounds on the welfare loss from moral hazard with limited liability," Games and Economic Behavior, Elsevier, vol. 95(C), pages 137-155.
    15. Marco Scarsini & Tristan Tomala, 2012. "Repeated congestion games with bounded rationality," International Journal of Game Theory, Springer;Game Theory Society, vol. 41(3), pages 651-669, August.
    16. Jonathan Kluberg & Georgia Perakis, 2012. "Generalized Quantity Competition for Multiple Products and Loss of Efficiency," Operations Research, INFORMS, vol. 60(2), pages 335-350, April.
    17. Zijun Wu & Rolf H. Möhring & Yanyan Chen & Dachuan Xu, 2021. "Selfishness Need Not Be Bad," Operations Research, INFORMS, vol. 69(2), pages 410-435, March.
    18. Thanasis Lianeas & Evdokia Nikolova & Nicolas E. Stier-Moses, 2019. "Risk-Averse Selfish Routing," Mathematics of Operations Research, INFORMS, vol. 44(1), pages 38-57, February.
    19. Roughgarden, Tim & Schoppmann, Florian, 2015. "Local smoothness and the price of anarchy in splittable congestion games," Journal of Economic Theory, Elsevier, vol. 156(C), pages 317-342.
    20. Qi, Jin & Sim, Melvyn & Sun, Defeng & Yuan, Xiaoming, 2016. "Preferences for travel time under risk and ambiguity: Implications in path selection and network equilibrium," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 264-284.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:68:y:2020:i:2:p:411-434. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.