TY - GEN
T1 - The asymptotic behavior of the price of anarchy
AU - Colini-Baldeschi, Riccardo
AU - Cominetti, Roberto
AU - Mertikopoulos, Panayotis
AU - Scarsini, Marco
N1 - Publisher Copyright:
© Springer International Publishing AG 2017.
PY - 2017
Y1 - 2017
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85037031151&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-71924-5_10
DO - 10.1007/978-3-319-71924-5_10
M3 - Conference contribution
AN - SCOPUS:85037031151
SN - 9783319719238
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 133
EP - 145
BT - Web and Internet Economics - 13th International Conference, WINE 2017, Proceedings
A2 - Devanur, Nikhil R.
A2 - Lu, Pinyan
PB - Springer Verlag
T2 - 13th International Conference on Web and Internet Economics, WINE 2017
Y2 - 17 December 2017 through 20 December 2017
ER -