toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
  Record Links
Author (up) Colini-Baldeschi, R.; Cominetti, R.; Mertikopoulos, P.; Scarsini, M. doi  openurl
  Title When Is Selfish Routing Bad? The Price of Anarchy in Light and Heavy Traffic Type
  Year 2020 Publication Operations Research Abbreviated Journal Oper. Res.  
  Volume 68 Issue 2 Pages 411-434  
  Keywords nonatomic congestion games; price of anarchy; light traffic; heavy traffic; regular variation  
  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.  
  Address [Colini-Baldeschi, Riccardo] Facebook Inc, Core Data Sci Grp, London W1T 1FB, England, Email:;  
  Corporate Author Thesis  
  Publisher Informs Place of Publication Editor  
  Language English Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 0030-364x ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000521730200006 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 1128  
Permanent link to this record
Select All    Deselect All
 |   | 

Save Citations:
Export Records: