Selfish Routing
Abstract
A central problem arising in the management of a large network is that of routing traffic. In many networks, it is difficult or even impossible to impose optimal routing strategies on network traffic, leaving network users free to act according to their own interests. The result of local optimization by many selfish network users with conflicting interests does not possess any type of global optimality; hence, this lack of regulation carries the cost of decreased network performance. We study the degradation in network performance due to selfish, uncoordinated behavior by network users. Our contributions are twofold: we quantify the worst-possible loss in network performance arising from noncooperative behavior; and we design and analyze algorithms for building and managing networks so that selfish behavior leads to a socially desirable outcome. To quantify the loss in network performance caused by selfish behavior, we investigate the following question: what is the worst-case ratio between the social cost of an uncoordinated outcome and the social cost of the best coordinated outcome? We provide an exact solution to this problem in a variety of traffic models, thereby identifying types of networks for which the cost of routing selfishly is mild. The inefficiency inherent in an uncoordinated outcome and the inability to centrally implement a globally optimal solution motivate our second question: how can we ensure that the loss in network performance due to selfish behavior will be tolerable? We explore two algorithmic approaches to coping with the selfishness of network users. First, we consider the problem of designing networks that exhibit good performance when used selfishly. Second, we study how to route a small fraction of the traffic centrally to induce "good" (albeit selfish) behavior from the rest of the network users. We give both efficient algorithms with provable performance guarantees and hardness of approximation results for these two problems.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 2002
- Accession Number
- ADA637978
Entities
People
- Tim Roughgarden
Organizations
- Cornell University