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

Selfishness Need Not Be Bad

Author

Listed:
  • Zijun Wu

    (Institute for Applied Optimization, School of Artificial Intelligence and Bigdata, Hefei University, 230091 Hefei, P. R. China;)

  • Rolf H. Möhring

    (Institute for Applied Optimization, School of Artificial Intelligence and Bigdata, Hefei University, 230091 Hefei, P. R. China; Institute of Mathematics, Technische Universität Berlin, 10623 Berlin, Germany;)

  • Yanyan Chen

    (Beijing Key Lab of Traffic Engineering, Beijing University of Technology, 100124 Beijing, P. R. China;)

  • Dachuan Xu

    (Department of Operations Research and Information Engineering, Beijing University of Technology, 100124 Beijing, P. R. China)

Abstract

We investigate the price of anarchy (PoA) in nonatomic congestion games when the total demand T gets very large. First results in this direction have recently been obtained by Colini-Baldeschi et al. (2016, 2017, 2020) for routing games and show that the PoA converges to one when the growth of the total demand T satisfies certain regularity conditions. We extend their results by developing a new framework for the limit analysis of the PoA that offers strong techniques such as the limit of games and applies to arbitrary growth patterns of T . We show that the PoA converges to one in the limit game regardless of the type of growth of T for a large class of cost functions that contains all polynomials and all regularly varying functions. For routing games with Bureau of Public Road (BPR) cost functions, we show in addition that socially optimal strategy profiles converge to equilibria in the limit game and that the PoA converges to one at a power law with exponent β , where β > 0 is the degree of the BPR functions. However, the precise convergence rate depends crucially on the the growth of T , which shows that a conjecture proposed by O’Hare et al. (2016) need not hold.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:oropre:v:69:y:2021:i:2:p:410-435
    DOI: 10.1287/opre.2020.2036
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/opre.2020.2036
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2020.2036?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. Smith, M. J., 1979. "The existence, uniqueness and stability of traffic equilibria," Transportation Research Part B: Methodological, Elsevier, vol. 13(4), pages 295-304, December.
    2. Fukushima, Masao, 1984. "A modified Frank-Wolfe algorithm for solving the traffic assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 18(2), pages 169-177, April.
    3. Olaf Jahn & Rolf H. Möhring & Andreas S. Schulz & Nicolás E. Stier-Moses, 2005. "System-Optimal Routing of Traffic Flows with User Constraints in Networks with Congestion," Operations Research, INFORMS, vol. 53(4), pages 600-616, August.
    4. 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.
    5. O'Hare, Steven J. & Connors, Richard D. & Watling, David P., 2016. "Mechanisms that govern how the Price of Anarchy varies with travel demand," Transportation Research Part B: Methodological, Elsevier, vol. 84(C), pages 55-80.
    6. 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.
    7. 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.
    8. Georgia Perakis, 2007. "The “Price of Anarchy” Under Nonlinear and Asymmetric Costs," Mathematics of Operations Research, INFORMS, vol. 32(3), pages 614-628, August.
    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. Cominetti, Roberto & Dose, Valerio & Scarsini, Marco, 2024. "Phase transitions of the price-of-anarchy function in multi-commodity routing games," Transportation Research Part B: Methodological, Elsevier, vol. 182(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. 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.
    2. Cominetti, Roberto & Dose, Valerio & Scarsini, Marco, 2024. "Phase transitions of the price-of-anarchy function in multi-commodity routing games," Transportation Research Part B: Methodological, Elsevier, vol. 182(C).
    3. 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.
    4. 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.
    5. 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.
    6. Mahdi Takalloo & Changhyun Kwon, 2019. "On the Price of Satisficing in Network User Equilibria," Papers 1911.07914, arXiv.org.
    7. Guo, Xiaolei & Yang, Hai & Liu, Tian-Liang, 2010. "Bounding the inefficiency of logit-based stochastic user equilibrium," European Journal of Operational Research, Elsevier, vol. 201(2), pages 463-469, March.
    8. Vincenzo Bonifaci & Tobias Harks & Guido Schäfer, 2010. "Stackelberg Routing in Arbitrary Networks," Mathematics of Operations Research, INFORMS, vol. 35(2), pages 330-346, May.
    9. 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.
    10. 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.
    11. 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.
    12. He, Zhidong & Navneet, Kumar & van Dam, Wirdmer & Van Mieghem, Piet, 2021. "Robustness assessment of multimodal freight transport networks," Reliability Engineering and System Safety, Elsevier, vol. 207(C).
    13. 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).
    14. Knight, Vincent A. & Harper, Paul R., 2013. "Selfish routing in public services," European Journal of Operational Research, Elsevier, vol. 230(1), pages 122-132.
    15. 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.
    16. Karakostas, George & Kim, Taeyon & Viglas, Anastasios & Xia, Hao, 2011. "On the degradation of performance for traffic networks with oblivious users," Transportation Research Part B: Methodological, Elsevier, vol. 45(2), pages 364-371, February.
    17. Oyama, Yuki & Hara, Yusuke & Akamatsu, Takashi, 2022. "Markovian traffic equilibrium assignment based on network generalized extreme value model," Transportation Research Part B: Methodological, Elsevier, vol. 155(C), pages 135-159.
    18. Sandholm, William H., 2015. "Population Games and Deterministic Evolutionary Dynamics," Handbook of Game Theory with Economic Applications,, Elsevier.
    19. Qiang Zhang & Shi Qiang Liu & Mahmoud Masoud, 2022. "A traffic congestion analysis by user equilibrium and system optimum with incomplete information," Journal of Combinatorial Optimization, Springer, vol. 43(5), pages 1391-1404, July.
    20. Georgia Perakis, 2007. "The “Price of Anarchy” Under Nonlinear and Asymmetric Costs," Mathematics of Operations Research, INFORMS, vol. 32(3), pages 614-628, August.

    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:69:y:2021:i:2:p:410-435. 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.