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 question: can these observations be justified theoretically? We first show that this is not always the case: the price of anarchy may remain bounded 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), the price of anarchy does converge to 1 in both heavy and light traffic conditions, and irrespective of the network topology and the number of O/D pairs in the network.

The asymptotic behavior of the price of anarchy / Colini-Baldeschi, Riccardo; Cominetti, Roberto; Mertikopoulos, Panayotis; Scarsini, Marco. - 10660:(2017), pp. 133-145. [10.1007/978-3-319-71924-5_10]

The asymptotic behavior of the price of anarchy

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

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 question: can these observations be justified theoretically? We first show that this is not always the case: the price of anarchy may remain bounded 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), the price of anarchy does converge to 1 in both heavy and light traffic conditions, and irrespective of the network topology and the number of O/D pairs in the network.
9783319719238
Theoretical Computer Science; Computer Science (all)
The asymptotic behavior of the price of anarchy / Colini-Baldeschi, Riccardo; Cominetti, Roberto; Mertikopoulos, Panayotis; Scarsini, Marco. - 10660:(2017), pp. 133-145. [10.1007/978-3-319-71924-5_10]
File in questo prodotto:
File Dimensione Formato  
WINE2017CCMS.pdf

Solo gestori archivio

Tipologia: Versione dell'editore
Licenza: Tutti i diritti riservati
Dimensione 305.56 kB
Formato Adobe PDF
305.56 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Caricamento 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/177127
Citazioni
  • Scopus 9
  • ???jsp.display-item.citation.isi??? ND
social impact