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.

Price of Anarchy for Highly Congested Routing Games in Parallel Networks / COLINI BALDESCHI, Riccardo; Cominetti, Roberto; Scarsini, Marco. - In: THEORY OF COMPUTING SYSTEMS. - ISSN 1432-4350. - 63:1(2019), pp. 90-113. [10.1007/s00224-017-9834-1]

Price of Anarchy for Highly Congested Routing Games in Parallel Networks

Colini-Baldeschi, Riccardo;Cominetti, Roberto;Scarsini, Marco
2019

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.
2019
Nonatomic routing games, Price of Anarchy, Regularly varying functions, Wardrop equilibrium, Parallel networks, High congestion
Price of Anarchy for Highly Congested Routing Games in Parallel Networks / COLINI BALDESCHI, Riccardo; Cominetti, Roberto; Scarsini, Marco. - In: THEORY OF COMPUTING SYSTEMS. - ISSN 1432-4350. - 63:1(2019), pp. 90-113. [10.1007/s00224-017-9834-1]
File in questo prodotto:
File Dimensione Formato  
TCS2019CCS.pdf

Solo gestori archivio

Tipologia: Versione dell'editore
Licenza: DRM (Digital rights management) non definiti
Dimensione 947.57 kB
Formato Adobe PDF
947.57 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11385/177265
Citazioni
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 11
  • OpenAlex ND
social impact