2012/03/01 by Richard Cole, Yevgeniy Dodis, Tim Roughgarden
Computer Science · Decision Sciences · #Game Theory and Applications #Network Traffic and Congestion Control #Optimization and Search Problems
paper · doi:10.1002/net.21458
crossref issued 2012/03/01 · crossref published 2012/03/01 · crossref published-online 2012/03/01 · openalex publication_date 2012/03/01 · crossref created 2012/03/03 · crossref published-print 2012/10/01 · crossref deposited 2023/10/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/05/21 · crossref indexed 2026/08/01
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. 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