Premium
Bottleneck links, variable demand, and the tragedy of the commons
Author(s) -
Cole Richard,
Dodis Yevgeniy,
Roughgarden Tim
Publication year - 2012
Publication title -
networks
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
ISBN - 0-89871-605-5
DOI - 10.1002/net.21458
Subject(s) - price of anarchy , bottleneck , shortest path problem , mathematical optimization , constrained shortest path first , path (computing) , computer science , mathematics , economics , computer network , price of stability , combinatorics , k shortest path routing , monetary policy , graph , monetary economics , embedded system
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. In single‐commodity networks, the worst‐case price of anarchy under the ℓ p path cost with 1 < p < ∞ is no more than with the standard ℓ 1 path norm. (A matching lower bound follows trivially from known results.) This upper bound also applies to the ℓ ∞ path cost if and only if attention is restricted to the natural subclass of equilibria generated by distributed shortest path routing protocols. For a natural cost‐minimization objective function, the price of anarchy with endogenous traffic rates (and under any ℓ p path cost) is no larger than that in fixed‐demand networks. Intuitively, the worst‐case inefficiency arising from the “tragedy of the commons” is no more severe than that from routing inefficiencies. © 2012 Wiley Periodicals, Inc. NETWORKS, 2012