Tim Roughgarden

In his PhD dissertation and subsequent book on "Selfish Routing and the Price of Anarchy," Tim Roughgarden introduces novel techniques for quantifying lost efficiency when the participants in a network act in their own self interest. These kinds of techniques are increasingly important as the Internet is by design, a decentralized collection of computers and networking equipment run by autonomous actors with their own goals. Beyond its practical import, Tim's research made important connections between computer science and economics, and he is a recognized leader in algorithmic mechanism design---a new and vibrant part of computer science. His research also built a much-needed bridge between theoretical computer science and the networking research community, as evidenced by a growing interest in understanding how incentives affect the behavior and evolution of the Internet.

Tim's research on selfish routing considers a network where the delays on each edge grow with increasing congestion. Selfish users try to direct their traffic over paths with the lowest delay, without regard to the consequences for other users. As such, selfish routing could lead to much worse performance than a socially optimal solution that coordinates the actions of all of the users. Tim's research answers the question "how bad is selfish routing," offering a clear mathematical explanation for why simple, uncoordinated networks with strategic users perform reasonably well in practice. Going beyond quantifying the "price of anarchy", Tim's recent research also explores how to design new network protocols with strategic users in mind from the beginning. Rather than requiring participants to divulge their preferences, his solutions focus on simple, distributed mechanisms that provably offer good performance to selfish users. His research has the potential to put the design and analysis of future networks and systems on a strong theoretical foundation that accurately captures the important role of strategic behavior.