The maximum latency of selfish routing
Tim Roughgarden · Symposium on Discrete Algorithms · 2004
Abstract : We study a model of selfish routing first studied in a theoretical computer science context by Roughgarden and Tardos. In this model, we are given a directed network in which each edge possesses a continuous, nondecreasing latency function that describes the common delay experienced by all traffic on the edge as a function of the edge congestion. We assume that each network user acts selfishly and routes itself from its source to its desired destination to minimize the latency experienced, given the network congestion due to the other users. As in most earlier works, we assume that the traffic comprises a large population of users, so that the actions of a single individual have negligible effect on network congestion. In this note, we prove that for single-commodity networks with n vertices arbitrary continuous, nondecreasing latency functions, the price of anarchy is precisely n - 1. We thus give both the first finite upper bound, and a new, optimal lower bound. The finite upper bound stands in contrast to the price of anarchy relative to the average latency, which is unbounded even for tow-node tow-link networks (3). We also give two conjectures (but no results) on the price of anarchy for multicommodity networks.