[home] - [up]


Lectures and Colloquia during the semester



June 25, 2002

Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin
Math building - Room MA 042           - map -
Lecture - 16:15

Tim Roughgarden - Cornell University

Selfish Routing

Abstract: A central and well-studied problem arising in the management of a large network is that of routing traffic to achieve the best possible network performance. 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. In general, 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. We will discuss methods for quantifying the worst-possible loss in network performance arising from noncooperative behavior, and algorithms for building and managing networks so that selfish behavior leads to a socially desirable outcome.

-

Abstract:


[home] - [up] - [top]