Selfish Routing and the Price of Anarchy Tim Roughgarden 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 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 independent and conflicting 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''. In general networks, the price of anarchy can be arbitrarily large. This negative fact motivates the following two positive results that bound the consequences of noncooperative behavior: (1) The inefficiency of selfish routing can always be offset by a moderate investment in network hardware. (2) If network performance does not degrade arbitrarily quickly as network congestion increases, then the price of anarchy is bounded. Moreover, very simple networks furnish worst-case examples for selfish routing. I will also briefly touch on methods for improving the noncooperative solution, such as network design and edge pricing; en route to understanding the power of these methods, I will describe the first generalization of Braess's Paradox to an infinite family of networks. Portions of this work are joint with Eva Tardos.