## 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 ℓ _{p} path cost. In single-commodity networks, the worst-case price of anarchy under the ℓ _{1} 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. ©

Original language | English (US) |
---|---|

Pages (from-to) | 194-203 |

Number of pages | 10 |

Journal | Networks |

Volume | 60 |

Issue number | 3 |

DOIs | |

State | Published - Oct 2012 |

## Keywords

- price of anarchy
- routing
- shortest path protocols
- traffic equilibria

## ASJC Scopus subject areas

- Information Systems
- Computer Networks and Communications