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.
|Titolo:||The asymptotic behavior of the price of anarchy|
|Data di pubblicazione:||2017|
|Appare nelle tipologie:||02.1 - Capitolo o saggio su monografia (Monograph’s Chapter/Essay)|
File in questo prodotto:
|WINE2017CCMS.pdf||Versione dell'editore||Tutti i diritti riservati||Administrator|