Selfishness Need Not Be Bad

Zijun Wu (), Rolf H. Möhring (), Yanyan Chen () and Dachuan Xu ()
Additional contact information
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

Operations Research, 2021, vol. 69, issue 2, 410-435

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.

Keywords: price of anarchy; routing game; user behavior; selfish routing; nonatomic congestion game; static traffic (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/opre.2020.2036 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:69:y:2021:i:2:p:410-435

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().