Tim Roughgarden
Note: I am no longer maintaining this web page. Please see
here instead.
Standard disclaimer: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained
by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints
invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright
holder.
Most Recent Papers
Selfish Routing
 R. Cole,
Y. Dodis, T. Roughgarden.
Pricing Networks with Selfish Routing
(or PDF).
 R. Cole,
Y. Dodis, T. Roughgarden.
Pricing Network Edges for Heterogeneous Selfish Users
(or PDF).
 Abstract
 Quick summary:
Marginal cost edge pricing
is known to eradicate the inefficiency of selfish routing,
under the strong homogeneity assumption that all network users trade
off time and money in an identical way. How should edges
be priced when the homogeneity assumption fails?
We prove that the edges of a singlecommodity network
can always be priced so that an optimal routing of traffic
arises as a Nash equilibrium, even for very general heterogeneous
populations of network users. We show how to compute such
taxes for most populations, and characterize the populations
for which moderate taxes always suffice.
 Bibliographic info: Conference version appeared in
STOC 2003, pages 521530.
 Slides
 R. Cole,
Y. Dodis, T. Roughgarden.
How Much Can Taxes Help Selfish Routing?
(or PDF).
 Abstract
 Quick summary:
How should network edges be priced to reduce
the cost of selfish routing, where cost is defined as
the sum of user utilities (the sum of the delays incurred and
the taxes paid)?
Marginal cost taxes (aka congestion or Pigouvian taxes),
which aim to minimize only the sum
of delays, are only appropriate for this goal only if taxes can
be feasibly refunded to users in a lumpsum fashion.
Since exorbitant taxes can effectively delete edges from a network,
this generalizes the FOCS '01 paper on network design, below.
 Bibliographic info: Conference version appeared in
EC 2003, pages 98107.
 Slides
 T. Roughgarden.
Selfish Routing (or PDF).
 Abstract
 Quick summary: Includes all material from the six papers below,
plus additional introductory material, surveys of prior work, and some
open questions.
 Bibliographic info: PhD thesis, Cornell University, May 2002.
 T. Roughgarden and É. Tardos.
Bounding the Inefficiency of Equilibria in
Nonatomic Congestion Games
(or PDF)
 Abstract
 Quick summary: Many of the positive results about selfish routing (in
particular, the main results from the FOCS 2000 and STOC 2002 papers, below)
do not require the combinatorial structure of a network, and hold more generally
for a wide class of games (called nonatomic congestion games) that has recently
received attention in the game theory literature.
 Bibliographic info:
 T. Roughgarden.
The Price of Anarchy is Independent of the
Network Topology. (or PDF)
 Abstract
 Quick summary: The worstcase inefficiency due to selfish routing always occurs
in the simplest of networks (e.g., a network of two parallel links).
This in turn permits the computation of the price of anarchy (the worstcase ratio between
the total latency of selfish routing and of optimal routing) for a wide array of edge
latency functions (polynomials, delay functions of M/M/1 queues, etc.).
 Bibliographic info:
 Note: Thanks to a suggestion of
Amir Ronen, the proof of the main technical theorem (Theorem 3.8 in the above version)
has been simplified considerably since the conference version.

Slides
 T. Roughgarden.
How Unfair is Optimal Routing?
(or PDF)
 Quick summary: A routing of traffic that is optimal from the viewpoint
of total latency may be "unfair" in the sense that some traffic may incur far more
latency in the optimal flow than in a selfishlydefined equilibrium. We prove limits
on this unfairness when all traffic shares the same source and destination.
 Bibliographic info:
Conference version appears in SODA 2002,
pages 203204.
 Slides
 T. Roughgarden.
Designing Networks for Selfish Users is Hard.
(or PDF)
 Abstract
 Quick summary: Given a network with congestiondependent edge latencies
and a prescribed sourcedestination pair and traffic rate, which subnetwork will
exhibit the best performance when used selfishly? Braess's Paradox shows that the
trivial algorithm of choosing the whole network is a suboptimal heuristic; we show
that it is the best possible polynomialtime heuristic, unless P=NP. We also give
an infinite family of examples generalizing Braess's Paradox, providing the
first demonstration that the severity of the paradox grows with the
network size.
 Bibliographic info:
 Slides:
short version or
long version
 T. Roughgarden.
Stackelberg Scheduling Strategies.
(or PDF)
 Abstract
 Quick summary: A manager controlling a small portion of the job traffic and
employing a carefully chosen scheduling strategy can greatly reduce the inefficiency
caused by selfish users in a system of shared machines possessing loaddependent
latencies.
 Bibliographic info:
 Slides:
short version or
long version
 T. Roughgarden and É. Tardos.
How Bad is Selfish Routing?
(or PDF)
 Abstract
 Quick summary: We give two bounds on the degradation in network
performance caused by network users routing their traffic selfishly.
First, the sum of all travel times (aka total latency)
of a selfishlydefined equilibrium in any multicommodity flow network
is at most that of an optimal routing of twice as much traffic.
Second, when link delay depends linearly on edge congestion, the total latency of
selfish routing is at most 4/3 times that of the best coordinated outcome.
 Bibliographic info:
 Slides: short version or
long version
 Additional slides from talks on selfish routing:
 Some press on selfish routing:
Approximation Algorithms

A. Gupta,
A. Kumar,
M. Pal,
T. Roughgarden.
Approximation Via CostSharing: A Simple Approximation Algorithm
for the Multicommodity RentorBuy Problem (or PDF).
 Abstract
 Quick summary: We show that a novel connection between cost sharing
and approximation algorithms leads to a general framework in which all results
of the STOC '03 paper below can be derived, and via which we also give a simpler and
better algorithm (than the FOCS '02 paper below) for the multicommodity
rentorbuy problem.
 Bibliographic info: Conference version to appear in
FOCS 2003.

A. Gupta,
A. Kumar,
T. Roughgarden.
Simpler and Better Approximation Algorithms for
Network Design (or PDF).
 Abstract
 Quick summary: We give dirtsimple and easytoanalyze
randomized algorithms that
improve the bestknown approximation ratios for connected facility location,
virtual private network design,
and singlesink buyatbulk network design.
 Bibliographic info: Conference version appeared in
STOC 2003, pages 365372.
 A. Kumar,
A. Gupta, T. Roughgarden.
A ConstantFactor Approximation Algorithm for
the Multicommodity RentorBuy Problem.
(or PDF)
 Abstract
 Quick summary:
Presents the first constantfactor approximation algorithm for network
design with multiple commodities and economies of scale
(all recent breakthroughs for buyatbulk network design have studied only the
special case where all commodities share a common sink vertex).
 Bibliographic info: Conference version appears in
FOCS 2002, pages 333342.
 T. Roughgarden.
Designing Networks for Selfish Users is Hard.
 See papers on selfish routing, above.
 F. A. Chudak,
T. Roughgarden,
D. P. Williamson. Approximate kMSTs and kSteiner
trees via the primaldual method and Lagrangean relaxation.
(or PDF)
 Abstract
 Quick summary: Garg's 5approximation algorithm for the mincost kMST
problem (FOCS '96) can be explained simply with the Lagrangean relaxation framework
introduced by Jain and Vazirani for the kmedian problem (JACM '01).
 Bibliographic info:
 Slides
Other
Tim Roughgarden
Department of Computer Science
Upson Hall
Cornell University
Ithaca, NY 14853
(607)2559201