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 single-commodity 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 521--530.
- 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 lump-sum 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 98--107.
- 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 worst-case 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 worst-case 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 selfishly-defined 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 203--204.
- Slides
- T. Roughgarden.
Designing Networks for Selfish Users is Hard.
(or PDF)
- Abstract
- Quick summary: Given a network with congestion-dependent edge latencies
and a prescribed source-destination 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 polynomial-time 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 load-dependent
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 selfishly-defined 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 Cost-Sharing: A Simple Approximation Algorithm
for the Multicommodity Rent-or-Buy 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
rent-or-buy 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 dirt-simple and easy-to-analyze
randomized algorithms that
improve the best-known approximation ratios for connected facility location,
virtual private network design,
and single-sink buy-at-bulk network design.
- Bibliographic info: Conference version appeared in
STOC 2003, pages 365--372.
- A. Kumar,
A. Gupta, T. Roughgarden.
A Constant-Factor Approximation Algorithm for
the Multicommodity Rent-or-Buy Problem.
(or PDF)
- Abstract
- Quick summary:
Presents the first constant-factor approximation algorithm for network
design with multiple commodities and economies of scale
(all recent breakthroughs for buy-at-bulk 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 333--342.
- T. Roughgarden.
Designing Networks for Selfish Users is Hard.
- See papers on selfish routing, above.
- F. A. Chudak,
T. Roughgarden,
D. P. Williamson. Approximate k-MSTs and k-Steiner
trees via the primal-dual method and Lagrangean relaxation.
(or PDF)
- Abstract
- Quick summary: Garg's 5-approximation algorithm for the min-cost k-MST
problem (FOCS '96) can be explained simply with the Lagrangean relaxation framework
introduced by Jain and Vazirani for the k-median problem (JACM '01).
- Bibliographic info:
- Slides
Other
Tim Roughgarden
Department of Computer Science
Upson Hall
Cornell University
Ithaca, NY 14853
(607)255-9201
