See also DBLP for further bibliographic information.
2021
 E. Neyman and T. Roughgarden, From Proper Scoring Rules to MaxMin Optimal
Forecast Aggregation, arXiv. (Talk by Eric)
 N. Haghtalab, T. Roughgarden, and A. Shetty, Smoothed Analysis with Adaptive Adversaries, arXiv.
 A. LewisPye and T. Roughgarden, Byzantine Generals in the Permissionless Setting, arXiv.
 E. Husic and T. Roughgarden, FPT Algorithms for Finding Dense Subgraphs in cClosed Graphs, arXiv.
 T. Roughgarden and C. Shikhelman, Ignore the Extra Zeroes:
VarianceOptimal Mining Pools, FC '21. (Clara's talk)
2020
 T. Roughgarden, Transaction Fee Mechanism Design for the Ethereum Blockchain: An Economic Analysis of EIP1559, December 2020. (Talks from Ethereum and mechanism design perspectives)
 N. Haghtalab, T. Roughgarden, and A. Shetty, Smoothed Analysis of Online and Differentially Private Learning, NeurIPS '20.
 R. Gupta and T. Roughgarden, DataDriven Algorithm Design,
Communications of the ACM, June 2020. ("Research highlights" version of the ITCS '16 paper below.)
 P. Duetting, T. Roughgarden, and I. TalgamCohen,
The Complexity of Contracts, SODA '20.
 T. Roughgarden and C. Seshadhri,
DistributionFree Models of Social Networks, Chapter 28
in Beyond the WorstCase Analysis of Algorithms.
 T. Roughgarden,
Distributional Analysis, Chapter 8
in Beyond the WorstCase Analysis of Algorithms.
 T. Roughgarden,
Resource Augmentation, Chapter 4
in Beyond the WorstCase Analysis of Algorithms.
 T. Roughgarden,
Introduction (to Beyond WorstCase Analysis), Chapter 1
in Beyond the WorstCase Analysis of Algorithms.
 T. Roughgarden,
Complexity Theory, Game Theory, and Economics (The Barbados Lectures), Foundations and Trends in TCS. (Preprint)
2019
 X. Chen, C. Papadimitriou, and T. Roughgarden,
An Axiomatic Approach to Block Rewards, AFT '19. (Related talk)
 P. Duetting, T. Roughgarden, and I. TalgamCohen,
Simple versus Optimal Contracts, EC '19. (Talk by Inbal)
 V. Chatziafratis, T. Roughgarden, and J. R. Wang,
On the Computational Power of Online Gradient Descent, COLT '19. (Talk by Vaggos)
 T. Roughgarden, ComplexityTheoretic Barriers in Economics, The Future of Economic Design.
 T. Roughgarden and I. TalgamCohen, Approximately Optimal Mechanism Design, Annual Reviews of Economics.
 T. Roughgarden, Beyond WorstCase Analysis, Communications of the ACM.
 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, Proceedings of the Royal Society A.
 B. Plaut and T. Roughgarden,
Communication Complexity of Discrete Fair Division, SODA '19.
2018
 R. Niazadeh, T. Roughgarden, and J. R. Wang,
Optimal Algorithms for Continuous Nonmonotone Submodular
and DRSubmodular Maximization, NeurIPS '18.
 T. Ezra, M. Feldman, T. Roughgarden, and W. Suksompong,
Pricing Identical Items, WINE '18.
 J. Fox, T. Roughgarden, C. Seshadhri, F. Wei, and N. Wein,
Finding Cliques in Social Networks: A New DistributionFree Model, ICALP '18. (Related talk)
 T. Roughgarden and J. R. Wang,
An Optimal Algorithm for Online Unconstrained Submodular Maximization, COLT '18. (Related talk)
 B. Plaut and T. Roughgarden,
Almost EnvyFreeness with General Valuations, SODA '18.
2017
 T. Roughgarden and O. Schrijvers, Online Prediction with Selfish Experts, NIPS '17. (Talk by Okke)
 V. Chatziafratis, T. Roughgarden, and J. Vondrak,
Stability and Recovery for Independence Systems, ESA '17.
 T. Roughgarden, I. TalgamCohen, and J. Vondrak,
When Are Welfare Guarantees Robust?, APPROX '17.
 V. Gkatzelis, E. Markakis, and T. Roughgarden, DeferredAcceptance Auctions for Multiple Levels of Service, EC '17. (Talk by Vasilis)
 R. ColiniBaldeschi, P. Goldberg, B. de Keijzer, S. Leonardi, T. Roughgarden, and S. Turchetta,
Approximately Efficient TwoSided Combinatorial Auctions, EC '17. (Talk by Stefano T)
 T. Roughgarden, V. Syrgkanis, and E. Tardos,
The Price of
Anarchy in Auctions (survey), Journal of Artificial Intelligence Research. (Related talk)
2016
 Y. Chen, A. Ghosh, M. Kearns, T. Roughgarden, and J. Wortman Vaughan, Mathematical Foundations for Social Computing, Communications of the ACM, December 2016.
(Preprint)
 T. Roughgarden and O. Weinstein,
On the Communication
Complexity of Approximate Fixed Points, FOCS '16.
(Talk by Omri)
 T. Roughgarden and J. R. Wang,
The Complexity of the kMeans Method, ESA '16.
 T. Roughgarden and O. Schrijvers,
Ironing in the Dark
, EC '16.
 T. Roughgarden and J. R. Wang,
Minimizing Regret with Multiple Reserves, EC '16/TEAC '19.
 T. Roughgarden, S. Vassilvitskii, and J. R. Wang,
Shuffles and Circuits
(On Lower Bounds for Modern Parallel Computation),
SPAA '16/JACM '18.
 J. Morgenstern and T. Roughgarden,
Learning Simple
Auctions, COLT '16. (Jamie's talk)
 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,
Communication Complexity (for Algorithm Designers), Foundations and
Trends in TCS. (arXiv version)
 O. Schrijvers, J. Bonneau, D. Boneh, and T. Roughgarden,
Incentive Compatibility of
Bitcoin Mining Pool Reward Functions, FC '16.
 R. Gupta and T. Roughgarden,
A PAC Approach to ApplicationSpecific Algorithm Selection, ITCS '16/SICOMP '17.
(Talk)
2015
 J. Morgenstern and T. Roughgarden,
The PseudoDimension of
NearOptimal Auctions, NIPS '15.
(Related talk)
 A. Globerson, T. Roughgarden, D. Sontag, and C. Yildirim,
How Hard Is Inference for Structured Prediction?
, ICML '15.
(longer arXiv version)
(Talk)
 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,
EC '15/TEAC '18.
(Talk by Noam)
 Z. Huang, Y. Mansour, and T. Roughgarden,
Making the Most of Your
Samples, EC '15/SICOMP '18.
2014
 V. Gkatzelis, K. Kollias, and T. Roughgarden,
Optimal CostSharing in General Resource Selection
Games,
WINE '14/OR '16.
 T. Roughgarden,
Approximately Optimal Mechanism Design: Motivation, Examples, and Lessons Learned,
SIGEcom Exchanges, 2014.
 T. Roughgarden,
Barriers to NearOptimal Equilibria,
FOCS
'14. FOCS
talk
(Lecture
notes)
 T. Roughgarden and O. Schrijvers,
Network CostSharing without Anonymity,
SAGT '14/TEAC '16.
 J. Hsu, A. Roth, T. Roughgarden, and J. Ullman,
Privately Solving Linear Programs,
ICALP '14.
 P. Duetting, V. Gkatzelis, and T. Roughgarden,
The Performance of DeferredAcceptance Auctions,
EC '14/MOR '17.
 P. Duetting, T. Roughgarden, and I. TalgamCohen,
Modularity and Greed in Double Auctions,
EC '14/GEB '17.
 J. Hsu, Z. Huang, A. Roth, T. Roughgarden, and Z. S. Wu,
Private Matchings and Allocations,
STOC '14/SICOMP '16.
 R. Cole and T. Roughgarden,
The Sample Complexity of Revenue Maximization,
STOC '14.
 R. Gupta, T. Roughgarden, and C. Seshadhri,
Decompositions of TriangleDense Graphs,
ITCS '14/SICOMP '16.
(Lecture notes)
(Related talk)
2013

T. Roughgarden and M. Kearns,
MarginalstoModels Reducibility,
NIPS '13.

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).
2012
 K. Bhawalkar and T. Roughgarden,
Simultaneous SingleItem Auctions, WINE '12.
 K. Bhawalkar, J. Kleinberg, K. Lewi, T. Roughgarden, and A. Sharma,
Preventing Unraveling in Social Networks: The Anchored kCore Problem, ICALP '12/SIDMA '15.
 T. Roughgarden, Intrinsic
Robustness of the Price of Anarchy,
Communications of the ACM, July 2012. ("Research highlights" version of
STOC '09 paper.) Also: preprint and video.
 T. Roughgarden and E. Tardos,
Do Externalities Degrade GSP's Efficiency?, Ad Auctions '12.
 T. Roughgarden, The Price of Anarchy in Games of Incomplete Information, EC '12/TEAC '14.
(Related talk)
 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.
 I. Abraham, M. Babaioff, S. Dughmi, and T. Roughgarden,
Combinatorial Auctions with Restricted Complements, EC '12.
 S. Leonardi and T. Roughgarden,
PriorFree Auctions with Ordered Bidders,
STOC '12.
Journal version, combined with EC '13 paper above (as of May '14).
 A. Badanidiyuru, S. Dobzinski, H. Fu, R. D. Kleinberg, N. Nisan
and T. Roughgarden, Sketching Valuation Functions, SODA '12.
2011
 U. Nadav, R. Johari, and T. Roughgarden,
Uncoupled Potentials for Proportional Allocation Markets, CDC '11.
 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)
 K. Kollias and T. Roughgarden,
Restoring Pure Equilibria
to Weighted Congestion Games, ICALP '11/TEAC '15.
 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.
(Related talk)
 T. Roughgarden and F. Schoppmann,
Local Smoothness and the Price of Anarchy in Splittable
Congestion Games, SODA '11/JET '14.
2010
 U. Nadav and T. Roughgarden,
The Limits of Smoothness:
A PrimalDual Framework for Price of Anarchy Bounds, WINE '10.
 J. Marden and T. Roughgarden,
Generalized Efficiency Bounds in Distributed Resource
Allocation, CDC '10/IEEE TAC '14.
 S. Dughmi and T. Roughgarden,
BlackBox Randomized Reductions in Algorithmic Mechanism Design, FOCS '10/SICOMP '14.
 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 WorstCase Examples, and Tightness, ESA '10/TEAC '14.
 P. Dhangwatnotai, T. Roughgarden, and Q. Yan,
Revenue
Maximization with a Single Sample, EC '10/GEB '14.
 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.
(Related talk)
 S. Dughmi, T. Roughgarden, and M. Sundararajan,
Revenue Submodularity, EC '09/Theory of Computing '12.
 D. MoskAoyama and T. Roughgarden, WorstCase Efficiency Analysis of Queueing Disciplines, ICALP '09.
 T. Roughgarden, Intrinsic Robustness of the
Price of Anarchy, STOC '09/JACM '15. See also CACM version above.
(Related talk)
 A. Ghosh, T. Roughgarden, and M. Sundararajan,
Universally
UtilityMaximizing Privacy Mechanisms, STOC '09/SICOMP '12.
 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
SingleParameter 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/GEB '17.
 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. MoskAoyama, 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 MultiServer,
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 CostSharing Mechanisms for Steiner Forest Problems, WINE '06.
 S. Chawla and T. Roughgarden,
SingleSource 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 CostSharing 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/Networks '12.
 M. Saha, G. SanchezAnte, 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.
 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/SIDMA '11.

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.
 T. Roughgarden, Selfish Routing with Atomic
Players, SODA '05.
Erratum
 C. Papadimitriou and T. Roughgarden, Computing Correlated Equilibria in MultiPlayer
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, appeared in SIDMA '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 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.
 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
Home