| |
Record |
Links |
|
Author  |
Colini-Baldeschi, R.; Cominetti, R.; Mertikopoulos, P.; Scarsini, M. |
|
| |
Title |
When Is Selfish Routing Bad? The Price of Anarchy in Light and Heavy Traffic |
Type |
|
| |
Year |
2020 |
Publication |
Operations Research |
Abbreviated Journal |
Oper. Res. |
|
| |
Volume |
68 |
Issue |
2 |
Pages |
411-434 |
|
| |
Keywords |
nonatomic congestion games; price of anarchy; light traffic; heavy traffic; regular variation |
|
| |
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 following question: can these observations be justified theoretically? We first 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 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) and inflow patterns, the price of anarchy does converge to 1 in both heavy and light traffic, 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. |
|
| |
Address |
[Colini-Baldeschi, Riccardo] Facebook Inc, Core Data Sci Grp, London W1T 1FB, England, Email: rickuz@fb.com; |
|
| |
Corporate Author |
|
Thesis |
|
|
| |
Publisher |
Informs |
Place of Publication |
|
Editor |
|
|
| |
Language |
English |
Summary Language |
|
Original Title |
|
|
| |
Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
|
| |
Series Volume |
|
Series Issue |
|
Edition |
|
|
| |
ISSN |
0030-364x |
ISBN |
|
Medium |
|
|
| |
Area |
|
Expedition |
|
Conference |
|
|
| |
Notes |
WOS:000521730200006 |
Approved |
|
|
| |
Call Number |
UAI @ eduardo.moreno @ |
Serial |
1128 |
|
| Permanent link to this record |
