When is selfish routing bad? The price of anarchy in light and heavy traffic - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Operations Research Année : 2020

When is selfish routing bad? The price of anarchy in light and heavy traffic

Résumé

This paper examines the behavior of the price of anarchy as a function of the traac innow 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 traac, thus raising the question: can these observations be justiied theoretically? We rst 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 traac innow, 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 traac, 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.
Fichier principal
Vignette du fichier
AsymptoticPoA.pdf (1012.8 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01891558 , version 1 (09-10-2018)

Identifiants

Citer

Riccardo Colini-Baldeschi, Roberto Cominetti, Panayotis Mertikopoulos, Marco Scarsini. When is selfish routing bad? The price of anarchy in light and heavy traffic. Operations Research, 2020, 68 (2), pp.411-434. ⟨10.1287/opre.2019.1894⟩. ⟨hal-01891558⟩
218 Consultations
62 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More