Bottleneck links, variable demand, and the tragedy of the commons

Richard Cole, Yevgeniy Dodis, Tim Roughgarden

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The price of anarchy, a measure of the inefficiency of selfish behavior, has been successfully analyzed in a diverse array of models over the past five years. The overwhelming majority of this work has studied optimization problems that sought an optimal way to allocate a fixed demand to resources whose performance degrades with increasing congestion. While fundamental, such problems overlook a crucial feature of many applications: the intrinsic coupling of the quality or cost of a resource and the demand for that resource. This coupling motivates allowing demand to vary with congestion, which in turn can lead to "the tragedy of the commons" - severe inefficiency caused by the overconsumption of a shared resource. Allowing the demand for resources to vary with their congestion illuminates a second issue with existing studies of the price of anarchy: the standard additive method of aggregating the costs of different resources in a player's strategy is inappropriate for some important applications, including many of those with variable demand. For example, in networking applications a key performance metric is the achievable throughput along a path, which is controlled by its bottleneck (most congested) edge. This disconnect motivates consideration of nonlinear cost aggregation functions, such as the l p norms. In this paper, we initiate the study of the price of anarchy with variable demand and with broad classes of nonlinear aggregation functions. We focus on selfish routing in single- and multicommodity networks, and on the l p norms for 1 ≤ p ≤∞; our main results are as follows. For a natural "prize-collecting" objective function, the price of anarchy in multicommodity networks with variable demand is no larger than that in fixed-demand networks. Thus the inefficiency arising from the tragedy of the commons is no more severe than that from routing inefficiencies. Using the l p norm with 1 < p < ∞ as a cost aggregation function can dramatically increase the price of anarchy in multicommodity networks (relative to additive aggregation), but causes no such additional inefficiency in single-commodity networks. Using the l norm as a cost aggregation function can dramatically increase the price of anarchy, even in single-commodity networks. If attention is restricted to equilibria with additional structure, however - structure that is ensured by distributed shortest-path routing protocols - then using the l norm does not increase the price of anarchy relative to additive aggregation.

Original languageEnglish (US)
Title of host publicationProceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
Pages668-677
Number of pages10
DOIs
StatePublished - 2006
EventSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States
Duration: Jan 22 2006Jan 24 2006

Other

OtherSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityMiami, FL
Period1/22/061/24/06

ASJC Scopus subject areas

  • Software
  • Discrete Mathematics and Combinatorics
  • Safety, Risk, Reliability and Quality
  • Chemical Health and Safety

Fingerprint Dive into the research topics of 'Bottleneck links, variable demand, and the tragedy of the commons'. Together they form a unique fingerprint.

  • Cite this

    Cole, R., Dodis, Y., & Roughgarden, T. (2006). Bottleneck links, variable demand, and the tragedy of the commons. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 668-677) https://doi.org/10.1145/1109557.1109630