toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
Details
   print
  Records Links
Author Colini-Baldeschi, R.; Cominetti, R.; Scarsini, M. pdf  doi
openurl 
  Title Price of Anarchy for Highly Congested Routing Games in Parallel Networks Type
  Year 2019 Publication Theory Of Computing Systems Abbreviated Journal Theor. Comput. Syst.  
  Volume 63 Issue 1 Pages 90-113  
  Keywords Nonatomic routing games; Price of Anarchy; Regularly varying functions; Wardrop equilibrium; Parallel networks; High congestion  
  Abstract We consider nonatomic routing games with one source and one destination connected by multiple parallel edges. We examine the asymptotic behavior of the price of anarchy as the inflow increases. In accordance with some empirical observations, we prove that under suitable conditions on the costs the price of anarchy is asymptotic to one. We show with some counterexamples that this is not always the case, and that these counterexamples already occur in simple networks with only 2 parallel links.  
  Address [Colini-Baldeschi, Riccardo; Scarsini, Marco] LUISS, Dipartimento Econ & Finanza, Viale Romania 32, I-00197 Rome, Italy, Email: rcolini@luiss.it;  
  Corporate Author Thesis  
  Publisher Springer Place of Publication Editor  
  Language English Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 1432-4350 ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000456320200005 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 974  
Permanent link to this record
 

 
Author Cominetti, R.; Dose, V.; Scarsini, M. doi  openurl
  Title The price of anarchy in routing games as a function of the demand Type
  Year 2022 Publication Mathematical Programming Abbreviated Journal Math. Program.  
  Volume Early Access Issue Pages  
  Keywords Nonatomic routing games; Price of anarchy; Affine cost functions; Variable demand  
  Abstract The price of anarchy has become a standard measure of the efficiency of equilibria in games. Most of the literature in this area has focused on establishing worst-case bounds for specific classes of games, such as routing games or more general congestion games. Recently, the price of anarchy in routing games has been studied as a function of the traffic demand, providing asymptotic results in light and heavy traffic. The aim of this paper is to study the price of anarchy in nonatomic routing games in the intermediate region of the demand. To achieve this goal, we begin by establishing some smoothness properties of Wardrop equilibria and social optima for general smooth costs. In the case of affine costs we show that the equilibrium is piecewise linear, with break points at the demand levels at which the set of active paths changes. We prove that the number of such break points is finite, although it can be exponential in the size of the network. Exploiting a scaling law between the equilibrium and the social optimum, we derive a similar behavior for the optimal flows. We then prove that in any interval between break points the price of anarchy is smooth and it is either monotone (decreasing or increasing) over the full interval, or it decreases up to a certain minimum point in the interior of the interval and increases afterwards. We deduce that for affine costs the maximum of the price of anarchy can only occur at the break points. For general costs we provide counterexamples showing that the set of break points is not always finite.  
  Address  
  Corporate Author Thesis  
  Publisher Place of Publication Editor  
  Language Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 0025-5610 ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000693858200001 Approved  
  Call Number UAI @ alexi.delcanto @ Serial 1468  
Permanent link to this record
Select All    Deselect All
 |   | 
Details
   print

Save Citations:
Export Records: