Tim Roughgarden and Éva Tardos:
How bad is selfish routing?
This paper is one of the founding papers in the area of algorithmic game theory. The basic question the paper addresses is stated succinctly in the title of the paper: what is the worst-case ratio between the average latency experienced by the combined traffic of multiple selfish users in equilibrium (when each user chooses the path that minimizes their own latency, given the paths selected by other users) and the average latency in the globally optimal, latency-minimizing routing? In other words, it studies the so-called “price of anarchy” of selfish routing, a notion which had been introduced just a year earlier by Elias Koutsoupias and Christos Papadimitriou.
Roughgarden and Tardos were able to show that in a general multi-commodity flow setting, where the latency on each edge is an affine function of the amount of flow on that edge, the price of anarchy is at most 4/3 and that this bound is tight. Furthermore, they showed that for any set of latency functions, the average latency in Nash equilibrium is never worse than the optimal latency in a network sending twice as much traffic. This provides theoretical support for the common practice of overprovisioning a network with extra capacity.
The proofs of the results in this paper are elegant and general, yet simple and accessible. Moreover, they are surprising: both results imply that the loss in social welfare due to selfish behavior is not that great in these settings. For these reasons, this paper served to popularize and showcase the significance and centrality of studying the inefficiency of equilibria. In so doing, the paper played a major role in inspiring both the trajectory and the explosive growth in research in algorithmic game theory, leading to the development of a rich and valuable literature.