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

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.