## 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 language | English (US) |
---|---|

Title of host publication | Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms |

Pages | 668-677 |

Number of pages | 10 |

DOIs | |

State | Published - 2006 |

Event | Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States Duration: Jan 22 2006 → Jan 24 2006 |

### Other

Other | Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Country/Territory | United States |

City | Miami, FL |

Period | 1/22/06 → 1/24/06 |

## ASJC Scopus subject areas

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