Selfish Routing and the Price of Anarchy
Tim Roughgarden, Cornell University

Abstract:

A recent trend in algorithm design is the study of game-theoretic environments, in which individual agents act according to their own independent and conflicting interests. The well-studied objective of routing traffic in a network to achieve the best possible network performance has emerged as a central problem in this area.

In large networks, it can be difficult or even impossible to impose optimal routing strategies on network traffic. On the other hand, permitting network users to act according to their own competing interests precludes any type of global optimality, and therefore carries the cost of decreased network performance. This inefficiency of noncooperative behavior is well known, and is most (in)famously illustrated in classical game theory by "The Prisoner's Dilemma" and in network routing by the counterintuitive "Braess's Paradox".

In this talk, I will discuss methods for quantifying the worst-possible loss in network performance arising from such noncooperative behavior --- the "price of anarchy". I will also briefly touch on methods for improving the noncooperative solution, including network design and edge pricing.

Portions of this work are joint with Eva Tardos.