Bottleneck links, variable demand, and the tragedy of the commons
Abstract
We study the price of anarchy of selfish routing with variable traffic rates and when the path cost is a nonadditive function of the edge costs. Nonadditive path costs are important, for example, in networking applications, where a key performance metric is the achievable throughput along a path, which is controlled by its bottleneck (most congested) edge. We prove the following results. In multicommodity networks, the worst‐case price of anarchy under the ℓp path cost with 1 p ≤∞ can be dramatically larger than under the standard ℓ1 path cost.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Mar 01, 2012
- Source ID
- 10.1002/net.21458
Entities
People
- Richard Cole
- Tim Roughgarden
- Yevgeniy Dodis
Organizations
- Defense Advanced Research Projects Agency
- Office of Naval Research