The Maximum Latency of Selfish Routing
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 2004
- Accession Number
- ADA637902
Entities
People
- Tim Roughgarden
Organizations
- Cornell University