See also DBLP for further bibliographic information.
2012
2011
- U. Nadav, R. Johari, and T. Roughgarden,
Uncoupled Potentials for Proportional Allocation Markets, CDC '11.
- S. Dughmi, T. Roughgarden, and Q. Yan,
From Convex Optimization to
Randomized Mechanisms: Toward Optimal Combinatorial Auctions, STOC '11.
- K. Kollias and T. Roughgarden,
Restoring Pure Equilibria
to Weighted Congestion Games, ICALP '11.
- R. Kumar, J. Talton, S. Ahmad, T. Roughgarden, and S. Klemmer,
Flexible Tree Matching,
IJCAI '11.
- K. Bhawalkar and T. Roughgarden,
Welfare Guarantees for Combinatorial Auctions with Item
Bidding, SODA '11.
- T. Roughgarden and F. Schoppmann,
Local Smoothness and the Price of Anarchy in Atomic Splittable
Congestion Games, SODA '11.
2010
- U. Nadav and T. Roughgarden,
The Limits of Smoothness:
A Primal-Dual Framework for Price of Anarchy Bounds, WINE '10.
- J. Marden and T. Roughgarden,
Generalized Efficiency Bounds in Distributed Resource
Allocation, CDC '10.
- S. Dughmi and T. Roughgarden,
Black-Box Randomized Reductions in Algorithmic Mechanism Design, FOCS '10.
- T. Roughgarden, Algorithmic Game Theory,
Communications of the ACM, July 2010.
Preprint
-
This is a revised and abridged version of the TCS '08 survey below.
- K. Bhawalkar, M. Gairing, and T. Roughgarden,
Weighted Congestion Games:
Price of Anarchy, Universal Worst-Case Examples, and Tightness, ESA '10.
- P. Dhangwotnotai, T. Roughgarden, and Q. Yan,
Revenue
Maximization with a Single Sample, EC '10.
- M. Babaioff and T. Roughgarden,
Equilibrium Efficiency and Price Complexity
in Sponsored Search Auctions, Workshop on Ad Auctions.
- A. Roth and T. Roughgarden,
Interactive Privacy via the Median Mechanism, STOC '10.
- T. Roughgarden, Computing Equilibria:
A Computational Complexity Perspective, invited survey
for Economic Theory.
2009
- J. D. Hartline and T. Roughgarden,
Simple versus Optimal Mechanisms, EC '09.
- S. Dughmi, T. Roughgarden, and M. Sundararajan,
Revenue Submodularity, EC '09 (full version as of Aug '10).
- D. Mosk-Aoyama and T. Roughgarden, Worst-Case Efficiency Analysis of Queueing Disciplines, ICALP '09.
- T. Roughgarden, Intrinsic Robustness of the
Price of Anarchy, STOC '09.
- A. Ghosh, T. Roughgarden, and M. Sundararajan,
Universally
Utility-Maximizing Privacy Mechanisms, STOC '09
(full version as of May '11).
- A. Motskin, T. Roughgarden, P. Skraba, and L. Guibas,
Lightweight Coloring and Desynchronization for
Networks, INFOCOM '09.
2008
- P. Dhangwatnotai, S. Dobzinski, S. Dughmi, and T. Roughgarden,
Truthful Approximation Schemes for
Single-Parameter Agents, FOCS '08/SICOMP '11.
- T. Roughgarden,
An Algorithmic Game Theory
Primer, TCS '08 (invited survey).
- J. D. Hartline and T. Roughgarden,
Optimal Mechanism Design
and Money Burning, STOC '08.
- S. Dobzinski, A. Mehta, T. Roughgarden, and M. Sundararajan,
Is Shapley Cost Sharing Optimal?, SAGT '08.
- S. Chawla and T. Roughgarden,
Bertrand Competition in Networks, SAGT '08.
- H. Chen, T. Roughgarden, and G. Valiant,
Designing Networks with Good Equilibria, SODA '08/SICOMP '10.
- R. Krauthgamer and T. Roughgarden,
Metric Clustering via Consistent Labeling, SODA '09/Theory of Computing '11.
2007
- N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani (eds.),
Algorithmic Game Theory, Cambridge University Press.
- T. Roughgarden,
Routing Games, Chapter 18
in Algorithmic Game Theory.
- T. Roughgarden and E. Tardos,
Introduction to the Inefficiency of Equilibria, Chapter 17
in Algorithmic Game Theory.
- D. Mosk-Aoyama, T. Roughgarden, and D. Shah,
Fully Distributed Algorithms for Convex Optimization,
DISC '07/SIAM J on Optimization '10.
- M. Haviv and T. Roughgarden,
The Price of Anarchy in an Exponential Multi-Server,
Operations Research Letters.
- T. Roughgarden,
Selfish Routing and the Price of Anarchy (Survey),
OPTIMA #74.
- T. Roughgarden and M. Sundararajan,
Optimal Efficiency Guarantees for Network Design Mechanisms, IPCO '07.
- A. Mehta, T. Roughgarden, and M. Sundararajan,
Beyond Moulin Mechanisms, EC '07/GEB '09.
2006
- S. Chawla, T. Roughgarden, and M. Sundararajan,
Optimal Cost-Sharing Mechanisms for Steiner Forest Problems, WINE '06.
- S. Chawla and T. Roughgarden,
Single-Source Stochastic Routing, APPROX '06.
- T. Roughgarden,
Potential Functions and the Inefficiency of Equilibria (Survey), ICM '06.
- H. Chen and T. Roughgarden,
Network Design with Weighted Players, SPAA '06/Theory of Computing Systems '09.
- T. Roughgarden and M. Sundararajan,
Quantifying Inefficiency in Cost-Sharing Mechanisms, STOC '06/JACM '09.
- G. Valiant and T. Roughgarden,
Braess's Paradox in Large Random Graphs, EC '06/Random
Structures and Algorithms '10.
- R. Cole, Y. Dodis, and T. Roughgarden,
Bottleneck Links, Variable Demand, and the Tragedy of the
Commons, SODA '06
(full version as of March '11).
- M. Saha, G. Sanchez-Ante, T. Roughgarden, and J.C. Latombe,
Planning Tours of Robotic Arms Among Partitioned Goals, International Journal of Robotics Research.
2005
- T. Roughgarden.
Selfish Routing and the Price of Anarchy, MIT Press.
- T. Roughgarden,
An Interview with Vladimir Trifonov (2005 Danny Lewin Best Student Paper Award Winner), SIGACT News '05.
- M. Enachescu, Y. Ganjali, A. Goel, N. McKeown, and
T. Roughgarden,
Routers with Very Small Buffers,
ACM Computer Communication Review.
INFOCOM '06 version.
- H. Lin, T. Roughgarden, E. Tardos, and A. Walkover, Braess's Paradox, Fibonacci Numbers, and
Exponential Inapproximability, ICALP '05.
-
This is the full version with the new title Stronger Bounds on Braess's Paradox
and the Maximum Latency of Selfish Routing
and includes both SODA 04 papers below; version from April '11.
- T. Roughgarden, Selfish Routing with Atomic
Players, SODA '05.
Erratum
- C. Papadimitriou and T. Roughgarden, Computing Correlated Equilibria in Multi-Player
Games, SODA '05/JACM '08.
Addendum
2004
- E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos,
T. Wexler, and T. Roughgarden, The Price
of Stability for Network Design
with Fair Cost Allocation, FOCS '04/SICOMP '08.
- T. Roughgarden and E. Tardos, Bounding the Inefficiency of Equilibria in
Nonatomic Congestion Games, Games and Economic Behavior.
- T. Roughgarden, The Maximum Latency of Selfish
Routing, SODA '04.
- H. Lin, T. Roughgarden, and E. Tardos,
A Stronger Bound on Braess's
Paradox, SODA '04.
- Journal version of these two SODA
papers, combined with the ICALP '05 paper above (most recent version from April '11).
2003
- A. Gupta, A. Kumar, M. Pal, and T. Roughgarden, Approximation Via Cost Sharing, FOCS '03.
- A. Gupta, A. Kumar, and T. Roughgarden,
Simpler and Better
Approximation Algorithms for
Network Design, STOC '03.
(Full version combined with FOCS '03 paper, above.)
- R. Cole, Y. Dodis, and T. Roughgarden, Pricing Network Edges for Heterogeneous Selfish Users, STOC '03.
- R. Cole, Y. Dodis, and T. Roughgarden, How Much Can Taxes Help Selfish
Routing?, EC '03/JCSS '06.
-
Survey of EC '03 and STOC '03 pricing papers, presented at P2PECON '03.
2002
- T. Roughgarden,
Selfish Routing, PhD Thesis,
Cornell University.
- A. Kumar, A. Gupta, and T. Roughgarden,
A Constant-Factor Approximation
Algorithm for
the Multicommodity Rent-or-Buy Problem, FOCS '02.
- No journal version of this paper is planned, although the algorithm
and analysis were simplified and extended in a STOC
'09 paper of Gupta and Kumar.
- T. Roughgarden,
The Price of Anarchy is Independent
of the Network Topology, STOC '02/JCSS '03.
- A. Hoffman, K. Jenkins, and T. Roughgarden,
On a Game in Directed Graphs, IPL '02.
- T. Roughgarden,
How Unfair is Optimal
Routing?, SODA '02.
2001
2000