Name
Title | ||
|---|---|---|
On the asymptotic behavior of the price of anarchy: Is selfish routing bad in highly congested networks? |
Abstract | ||
|---|---|---|
This paper examines the asymptotic behavior of the price of anarchy as a function of the total traffic inflow in nonatomic congestion games with multiple origin-destination pairs. We first show that the price of anarchy may remain bounded away from 1, even in simple three-link parallel networks with convex cost functions. On the other hand, empirical studies show that the price of anarchy is close to 1 in highly congested real-world networks, thus begging the question: under what assumptions can this behavior be justified analytically? To that end, we prove a general result showing that for a large class of cost functions (defined in terms of regular variation and including all polynomials), the price of anarchy converges to 1 in the high congestion limit. In particular, specializing to networks with polynomial costs, we show that this convergence follows a power law whose degree can be computed explicitly. |
Year | Venue | Field |
|---|---|---|
2017 | arXiv: Computer Science and Game Theory | Convergence (routing),Mathematical economics,Mathematical optimization,Polynomial,Price of stability,Regular polygon,Price of anarchy,Asymptotic analysis,Empirical research,Mathematics,Bounded function |
DocType | Volume | Citations |
Journal | abs/1703.00927 | 1 |
PageRank | References | Authors |
0.37 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Riccardo Colini-Baldeschi | 1 | 42 | 9.30 |
| R. Cominetti | 2 | 159 | 22.44 |
| Panayotis Mertikopoulos | 3 | 258 | 43.71 |
| Marco Scarsini | 4 | 164 | 33.96 |