Pricing Networks with Selfish Routing
Abstract
We study the negative consequences of selfish behavior in networks and economic means of influencing such behavior. We focus on a simple model of selfish routing, defined by Wardrop and first studied from a theoretical computer science perspective by Roughgarden and Tardos. In this model, we are given a directed network in which each edge possesses a latency function, describing the common latency (delay) experienced by all traffic on the edge as a function of the edge congestion. There is a fixed amount of traffic wishing to travel from a source vertex s to a sink vertex t, and we assume that the traffic comprises a very large population of users, so that the actions of a single individual have negligible effect on network congestion. A common way to measure the quality of an assignment of traffic to s-t paths is by the sum of all travel times the total latency. We assume that each network user acts selfishly and routes itself on a minimum-latency path, given the network congestion due to the other users. In general such a "selfishly motivated" assignment of traffic to paths (a Nash equilibrium) does not minimize the total latency; put differently, the outcome of selfish behavior can be improved upon with coordination.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 28, 2003
- Accession Number
- ADA637950
Entities
People
- Richard Cole
- Tim Roughgarden
- Yevgeniy Dodis
Organizations
- Cornell University