CORNELL UNIV ITHACA NY DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
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.
- Operations Research
- Computer Programming and Software
- Computer Systems