Selfish Routing and the Price of Anarchy

Tim Roughgarden

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. The result of local optimization by many selfish network users with conflicting interests need not possess any type of global optimality; hence, this lack of regulation carries the cost of decreased network performance.  In this talk, we will discuss methods for quantifying the worst possible loss in network performance arising from such no cooperative behavior. 

Includes joint work with Eva Tardos.