Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. The Price of Anarchy with Polynomial Edge Latency

The Price of Anarchy with Polynomial Edge Latency

File(s)
2001-1847.ps (225.68 KB)
Permanent Link(s)
https://hdl.handle.net/1813/5834
Collections
Computer Science Technical Reports
Author
Roughgarden, Tim
Abstract

We consider the problem of routing traffic to optimize the performance of a congested network. We are given a network, a rate of traffic between each pair of nodes, and a latency function for each edge specifying the time needed to traverse the edge given its congestion; the objective is to route traffic such that the sum of all travel times---the total latency---is minimized. In many settings, it is not possible to implement an optimal assignment of routes. In the absence of regulation by some central authority, we assume that each network user routes its traffic on the minimum-latency path available to it, given the network congestion caused by the other users. In general such a ``selfishly motivated'' assignment of traffic to paths will not minimize the total latency; hence, this lack of regulation carries the cost of decreased network performance. In this paper, we prove that if the latency of each edge is a polynomial function of degree at most $p$ of the edge congestion, then the total latency of the routes chosen by selfish network users is at most $[1 - p \cdot (p+1)^{-(p+1)/p}]^{-1} = \Theta(\frac{p}{\ln p})$ times the minimum possible total latency. A simple example shows that this result is best possible for all values of $p$.

Date Issued
2001-07-29
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR2001-1847
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance