As part of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2020), convened at Duke University, it will be announced that Tim Roughgarden and Éva Tardos' paper “How Bad is Selfish Routing?” (FOCS 2000, 93-102) will receive a Test of Time Award. FOCS 2020 runs from November 16-19.
Tim Roughgarden is a professor in the computer science department at Columbia University. Prior to joining Columbia, he spent fifteen years on the computer science faculty at Stanford, following a Ph.D. at Cornell ('02) and a postdoc at UC Berkeley. He works on the boundary of computer science and economics, and on the design, analysis, applications, and limitations of algorithms. Roughgarden's doctoral dissertation is entitled Selfish Routing (May 2002) and his Ph.D. advisor was Éva Tardos.
Éva Tardos is the Jacob Gould Schurman Professor of Computer Science and Chair of the department. At Cornell, Tardos's research focus is "Algorithms and algorithmic game theory, the sub-area of theoretical computer science theory of designing systems and algorithms for selfish users [...], and games on networks and simple auctions." She notes she is "mostly interested in designing algorithms and games that provide provably close-to-optimal results."
"How Bad is Selfish Routing?” abstract:
We consider the problem of routing traffic to optimize the performance of a congested network. We are given a network, a rate of traffic between each pair of nodes, and a latency function for each edge specifying the time needed to traverse the edge given its congestion; the objective is to route traffic such that the sum of all travel times—the total latency—is minimized.
In many settings, it may be expensive or impossible to regulate network traffic so as to implement an optimal assignment of routes. In the absence of regulation by some central authority, we assume that each network user routes its traffic on the minimum-latency path available to it, given the network congestion caused by the other users. In general such a “selfishly motivated” assignment of traffic to paths will not minimize the total latency; hence, this lack of regulation carries the cost of decreased network performance.
In this paper we quantify the degradation in network performance due to unregulated traffic. We prove that if the latency of each edge is a linear function of its congestion, then the total latency of the routes chosen by selfish network users is at most 4 times the minimum possible total latency (subject to the condition that all traffic must be routed). We also consider the more general setting in which edge latency functions are assumed only to be continuous and nondecreasing in the edge congestion. Here, the total latency of the routes chosen by unregulated selfish network users may be arbitrarily larger than the minimum possible total latency; however, we prove that it is no more than the total latency incurred by optimally routing twice as much traffic.