Selfish Routing And The Price Of Anarchy

Tim Roughgarden

Stanford University

March 15, 4:15pm


A recent trend in discrete optimization 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

Return to Applied Math Colloquium home page