Tim Roughgarden's Papers by Topic
(See also DBLP for further bibliographic information.)
Algorithmic Game Theory (Books and Surveys)
 T. Roughgarden,
Barbados Lectures on Complexity Theory, Game Theory, and Economics, arXiv, 2018.
 Twenty Lectures on Algorithmic Game Theory, Cambridge University Press, 2016.
 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.
 T. Roughgarden,
An Algorithmic Game Theory
Primer, TCS '08 (invited survey).
 N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani (eds.),
Algorithmic Game Theory, Cambridge University Press.
Applications of Algorithms
 R. Kumar, J. Talton, S. Ahmad, T. Roughgarden, and S. Klemmer,
Flexible Tree Matching,
IJCAI '11.
 A. Motskin, T. Roughgarden, P. Skraba, and L. Guibas,
Lightweight Coloring and Desynchronization for
Networks, INFOCOM '09.
 M. Saha, G. SanchezAnte, T. Roughgarden, and J.C. Latombe,
Planning Tours of Robotic Arms Among Partitioned Goals, International Journal of Robotics Research.
 M. Enachescu, Y. Ganjali, A. Goel, N. McKeown, and
T. Roughgarden,
Routers with Very Small Buffers,
ACM Computer Communication Review.
INFOCOM '06 version.
Approximation Algorithms
 R. Niazadeh, T. Roughgarden, and J. R. Wang,
Optimal Algorithms for Continuous Nonmonotone Submodular
and DRSubmodular Maximization, arXiv.
 T. Roughgarden, I. TalgamCohen, and J. Vondrak,
When Are Welfare Guarantees Robust?, APPROX '17.
 R. Krauthgamer and T. Roughgarden,
Metric Clustering via Consistent Labeling, SODA '09/Theory of Computing '11.
 S. Chawla and T. Roughgarden,
SingleSource Stochastic Routing, APPROX '06.
 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.)
 A. Kumar, A. Gupta, and T. Roughgarden,
A ConstantFactor Approximation
Algorithm for
the Multicommodity RentorBuy 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.
 F. Chudak, T. Roughgarden, and D. Williamson,
Approximate kMSTs and kSteiner
trees via the primaldual method and Lagrangean relaxation,
IPCO '01/Mathematical Programming '04.
Auction and Mechanism Design
Surveys
Algorithmic Mechanism Design
 V. Gkatzelis, E. Markakis, and T. Roughgarden, DeferredAcceptance Auctions for Multiple Levels of Service, EC '17.
 P. Duetting, V. Gkatzelis, and T. Roughgarden,
The Performance of DeferredAcceptance Auctions,
full version of EC '14 paper.
 P. Duetting, T. Roughgarden, and I. TalgamCohen,
Modularity and Greed in Double Auctions,
full version of EC '14 paper.
 I. Abraham, M. Babaioff, S. Dughmi, and T. Roughgarden,
Combinatorial Auctions with Restricted Complements, EC '12.
 S. Dughmi, T. Roughgarden, and Q. Yan,
Optimal Mechanisms for Combinatorial Auctions and Combinatorial Public Projects via Convex Rounding, STOC '11/JACM '16. (Lecture notes)
 S. Dughmi and T. Roughgarden,
BlackBox Randomized Reductions in Algorithmic Mechanism Design, FOCS '10/SICOMP '14.
 P. Dhangwatnotai, S. Dobzinski, S. Dughmi, and T. Roughgarden,
Truthful Approximation Schemes for
SingleParameter Agents, FOCS '08/SICOMP '11.
Contracts
CostSharing Mechanisms
 S. Dobzinski, A. Mehta, T. Roughgarden, and M. Sundararajan,
Is Shapley Cost Sharing Optimal?,
SAGT '08/GEB '17.
 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.
 S. Chawla, T. Roughgarden, and M. Sundararajan,
Optimal CostSharing Mechanisms for Steiner Forest Problems, WINE '06.
 T. Roughgarden and M. Sundararajan,
Quantifying Inefficiency in CostSharing Mechanisms, STOC '06/JACM '09.
Learning Auctions from Data
 T. Roughgarden and J. R. Wang,
Minimizing Regret with Multiple Reserves, full version of EC '16 paper.
 T. Roughgarden and O. Schrijvers,
Ironing in the Dark
, EC '16.
 J. Morgenstern and T. Roughgarden,
Learning Simple
Auctions, COLT '16. (Jamie's talk)
 J. Morgenstern and T. Roughgarden,
The PseudoDimension of
NearOptimal Auctions, NIPS '15. (Related talk)
 Z. Huang, Y. Mansour, and T. Roughgarden,
Making the Most of Your
Samples, EC '15/SICOMP '18.
 R. Cole and T. Roughgarden,
The Sample Complexity of Revenue Maximization,
STOC '14.
 P. Dhangwatnotai, T. Roughgarden, and Q. Yan,
Revenue
Maximization with a Single Sample, EC '10/GEB '14.
Lower Bounds and Complexity
 T. Roughgarden and I. TalgamCohen,
Why Prices
Need Algorithms, EC '15.
 P. Gopalan, N. Nisan, and T. Roughgarden,
Public Projects, Boolean
Functions, and the Borders of Border's Theorem,
full version of EC '15 paper.
(Talk by Noam)
 T. Roughgarden,
Barriers to NearOptimal Equilibria,
FOCS
'14. FOCS
talk
(Lecture
notes)
RevenueMaximizing Auctions

T. Roughgarden and I. TalgamCohen,
Optimal and NearOptimal
Mechanism Design with Interdependent Values, EC '13/TEAC '16.
(Talk by Inbal)

S. Bhattacharya, E. Koutsoupias, J. Kulkarni, S. Leonardi, T. Roughgarden,
and X. Xu,
PriorFree MultiUnit Auctions with Ordered Bidders, EC '13 (full version, combined with STOC '12 paper, as of May '14).
 S. Leonardi and T. Roughgarden,
PriorFree Auctions with Ordered Bidders,
STOC '12.
Journal version, combined with EC '13 paper above (as of May '14).
 T. Roughgarden, I. TalgamCohen, and Q. Yan,
Robust Auctions for Revenue
via Enhanced Competition, full version of EC '12 paper (as of Aug '15). The conference version, with the title SupplyLimiting Mechanisms, has some additional results.
 P. Dhangwatnotai, T. Roughgarden, and Q. Yan,
Revenue
Maximization with a Single Sample, EC '10/GEB '14.
 J. D. Hartline and T. Roughgarden,
Simple versus Optimal Mechanisms, EC '09.
(Related talk)
 S. Dughmi, T. Roughgarden, and M. Sundararajan,
Revenue Submodularity, EC '09/Theory of Computing '12.
 J. D. Hartline and T. Roughgarden,
Optimal Mechanism Design
and Money Burning, STOC '08.
Simple Auctions
 T. Ezra, M. Feldman, T. Roughgarden, and W. Suksompong,
Pricing Identical Items, arXiv.
 R. ColiniBaldeschi, P. Goldberg, B. de Keijzer, S. Leonardi, T. Roughgarden, and S. Turchetta,
Approximately Efficient TwoSided Combinatorial Auctions, EC '17.
 K. Bhawalkar and T. Roughgarden,
Simultaneous SingleItem Auctions, WINE '12.
 A. Badanidiyuru, S. Dobzinski, H. Fu, R. D. Kleinberg, N. Nisan
and T. Roughgarden, Sketching Valuation Functions, SODA '12.
 K. Bhawalkar and T. Roughgarden,
Welfare Guarantees for Combinatorial Auctions with Item
Bidding, SODA '11.
(Related talk)
 J. D. Hartline and T. Roughgarden,
Simple versus Optimal Mechanisms, EC '09.
(Related talk)
Sponsored Search Auctions
Beyond WorstCase Analysis
 T. Roughgarden, Beyond WorstCase Analysis, to appear in Communications of the ACM.
 J. Fox, T. Roughgarden, C. Seshadhri, F. Wei, and N. Wein,
Finding Cliques in Social Networks: A New DistributionFree Model, ICALP '18.
 V. Chatziafratis, T. Roughgarden, and J. Vondrak,
Stability and Recovery for Independence Systems, ESA '17.
 R. Gupta and T. Roughgarden,
A PAC Approach to ApplicationSpecific Algorithm Selection, ITCS '16/SICOMP '17.
(Talk)
 R. Gupta, T. Roughgarden, and C. Seshadhri,
Decompositions of TriangleDense Graphs,
ITCS '14/SICOMP '16.
(Lecture notes)
(Related talk)
Communication Complexity
Complexity (Misc)
Computing Equilibria
 T. Roughgarden,
Barbados Lectures on Complexity Theory, Game Theory, and Economics, arXiv, 2018.
 T. Roughgarden, Computing Equilibria:
A Computational Complexity Perspective, invited survey
for Economic Theory, 2010.
 C. Papadimitriou and T. Roughgarden, Computing Correlated Equilibria in MultiPlayer
Games, SODA '05/JACM '08.
Addendum
Cryptocurrencies
Differential Privacy
 J. Hsu, A. Roth, T. Roughgarden, and J. Ullman,
Privately Solving Linear Programs,
ICALP '14.
 J. Hsu, Z. Huang, A. Roth, T. Roughgarden, and Z. S. Wu,
Private Matchings and Allocations,
full version of STOC '14 paper.
 A. Roth and T. Roughgarden,
Interactive Privacy via the Median Mechanism, STOC '10.
 A. Ghosh, T. Roughgarden, and M. Sundararajan,
Universally
UtilityMaximizing Privacy Mechanisms, STOC '09/SICOMP '12.
Fair Division
Inference
MapReduce
Network Games (other than Routing)
 T. Roughgarden and O. Schrijvers,
Network CostSharing without Anonymity,
SAGT '14/TEAC '16.
 U. Nadav, R. Johari, and T. Roughgarden,
Uncoupled Potentials for Proportional Allocation Markets, CDC '11.
 K. Kollias and T. Roughgarden,
Restoring Pure Equilibria
to Weighted Congestion Games, ICALP '11/TEAC '15.
 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.
 H. Chen and T. Roughgarden,
Network Design with Weighted Players, SPAA '06/Theory of Computing Systems '09.
 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.
Online Learning
 V. Chatziafratis, T. Roughgarden, and J. R. Wang,
On the Computational Power of Online Gradient Descent, arXiv.
 T. Roughgarden and J. R. Wang,
An Optimal Algorithm for Online Unconstrained Submodular Maximization, COLT '18.
 T. Roughgarden and O. Schrijvers, Online Prediction with Selfish Experts, NIPS '17.
 T. Roughgarden and J. R. Wang,
Minimizing Regret with Multiple Reserves, full version of EC '16 paper.
Price of Anarchy
Surveys
Lower Bounds
POA Bounds for Specific Games (other than Routing and Auctions)
Smooth Games and Robust POA Bounds
 M. Feldman, N. Immorlica, B. Lucier, T. Roughgarden,
and V. Syrgkanis,
The Price of Anarchy in
Large Games, STOC '16.
(Related talk by Brendan)
 T. Roughgarden, The Price of Anarchy in Games of Incomplete Information, EC '12/TEAC '14.
(Related talk)
 T. Roughgarden, Intrinsic
Robustness of the Price of Anarchy,
Communications of the ACM, July 2012. ("Reader's digest" version of
STOC '09 paper below.) Also: preprint and video.
 T. Roughgarden and F. Schoppmann,
Local Smoothness and the Price of Anarchy in Splittable
Congestion Games, SODA '11/JET '14.
 U. Nadav and T. Roughgarden,
The Limits of Smoothness:
A PrimalDual Framework for Price of Anarchy Bounds, WINE '10.
 T. Roughgarden, Intrinsic Robustness of the
Price of Anarchy, STOC '09/JACM '15. See also CACM version above.
(Related talk)
Routing Games
Surveys
Braess's Paradox
 G. Valiant and T. Roughgarden,
Braess's Paradox in Large Random Graphs, EC '06/Random
Structures and Algorithms '10.
 H. Lin, T. Roughgarden, E. Tardos, and A. Walkover, Braess's Paradox, Fibonacci Numbers, and
Exponential Inapproximability, ICALP '05/SIDMA '11.
 H. Lin, T. Roughgarden, and E. Tardos,
A Stronger Bound on Braess's
Paradox, SODA '04.
 T. Roughgarden,
Designing Networks for
Selfish Users is Hard, FOCS '01/JCSS '06.
Fairness
Price of Anarchy in Routing Games
 V. Gkatzelis, K. Kollias, and T. Roughgarden,
Optimal CostSharing in General Resource Selection
Games,
WINE '14/OR '16.
 K. Kollias and T. Roughgarden,
Restoring Pure Equilibria
to Weighted Congestion Games, ICALP '11 (full version as of Jan '14).
 T. Roughgarden and F. Schoppmann,
Local Smoothness and the Price of Anarchy in Atomic Splittable
Congestion Games, SODA '11/JET '14.
 K. Bhawalkar, M. Gairing, and T. Roughgarden,
Weighted Congestion Games:
Price of Anarchy, Universal WorstCase Examples, and Tightness, ESA '10/ACM TEAC '14.
 M. Haviv and T. Roughgarden,
The Price of Anarchy in an Exponential MultiServer,
Operations Research Letters.
 R. Cole, Y. Dodis, and T. Roughgarden,
Bottleneck Links, Variable Demand, and the Tragedy of the
Commons, SODA '06/Networks '12.
 T. Roughgarden, Selfish Routing with Atomic
Players, SODA '05.
Erratum
 T. Roughgarden and E. Tardos, Bounding the Inefficiency of Equilibria in
Nonatomic Congestion Games, Games and Economic Behavior.
 T. Roughgarden,
The Price of Anarchy is Independent
of the Network Topology, STOC '02/JCSS '03.
 T. Roughgarden and E. Tardos,
How Bad is Selfish Routing?,
FOCS '00/JACM '02.
Stackelberg Routing and Tolls
 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.
 T. Roughgarden,
Stackelberg Scheduling
Strategies, STOC '01/SICOMP '04.
Social Computing
Social Networks
 G. Barmpalias, N. Huang, A. LewisPye, A. Li, X. Li, Y. Pan, and T. Roughgarden, The Idemetric Property: When Most Distances Are (Almost) the Same, arXiv.
 J. Fox, T. Roughgarden, C. Seshadhri, F. Wei, and N. Wein,
Finding Cliques in Social Networks: A New DistributionFree Model, ICALP '18.
 R. Gupta, T. Roughgarden, and C. Seshadhri,
Decompositions of TriangleDense Graphs,
ITCS '14/SICOMP '16.
(Lecture notes)
 K. Bhawalkar, J. Kleinberg, K. Lewi, T. Roughgarden, and A. Sharma,
Preventing Unraveling in Social Networks: The Anchored kCore Problem, ICALP '12/SIDMA '15.
Other
Home