Tim Roughgarden's Papers (Chronological List)

See also DBLP for further bibliographic information.

2018

P. Duetting, T. Roughgarden, and I. Talgam-Cohen, Simple versus Optimal Contracts, arXiv.
R. Niazadeh, T. Roughgarden, and J. R. Wang, Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization, arXiv.
V. Chatziafratis, T. Roughgarden, and J. R. Wang, On the Computational Power of Online Gradient Descent, arXiv.
G. Barmpalias, N. Huang, A. Lewis-Pye, A. Li, X. Li, Y. Pan, and T. Roughgarden, The Idemetric Property: When Most Distances Are (Almost) the Same, arXiv.
B. Plaut and T. Roughgarden, Communication Complexity of Discrete Fair Division, arXiv.
T. Ezra, M. Feldman, T. Roughgarden, and W. Suksompong, Pricing Identical Items, arXiv.
T. Roughgarden, Beyond Worst-Case 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 Distribution-Free Model, ICALP '18.
T. Roughgarden and J. R. Wang, An Optimal Algorithm for Online Unconstrained Submodular Maximization, COLT '18.
B. Plaut and T. Roughgarden, Almost Envy-Freeness with General Valuations, SODA '18.
T. Roughgarden, Barbados Lectures on Complexity Theory, Game Theory, and Economics, arXiv.

2017

T. Roughgarden and O. Schrijvers, Online Prediction with Selfish Experts, NIPS '17.
V. Chatziafratis, T. Roughgarden, and J. Vondrak, Stability and Recovery for Independence Systems, ESA '17.
T. Roughgarden, I. Talgam-Cohen, and J. Vondrak, When Are Welfare Guarantees Robust?, APPROX '17.
V. Gkatzelis, E. Markakis, and T. Roughgarden, Deferred-Acceptance Auctions for Multiple Levels of Service, EC '17.
R. Colini-Baldeschi, P. Goldberg, B. de Keijzer, S. Leonardi, T. Roughgarden, and S. Turchetta, Approximately Efficient Two-Sided Combinatorial Auctions, EC '17.
T. Roughgarden, V. Syrgkanis, and E. Tardos, The Price of Anarchy in Auctions (survey), Journal of Artificial Intelligence Research.

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 k-Means 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, full version of EC '16 paper.
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 Application-Specific Algorithm Selection, ITCS '16/SICOMP '17. (Talk)

2015

J. Morgenstern and T. Roughgarden, The Pseudo-Dimension of Near-Optimal 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. Talgam-Cohen, 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)
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 Cost-Sharing 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 Near-Optimal Equilibria, FOCS '14. FOCS talk (Lecture notes)
T. Roughgarden and O. Schrijvers, Network Cost-Sharing 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 Deferred-Acceptance Auctions, full version of EC '14 paper.
P. Duetting, T. Roughgarden, and I. Talgam-Cohen, Modularity and Greed in Double Auctions, full version of EC '14 paper.
J. Hsu, Z. Huang, A. Roth, T. Roughgarden, and Z. S. Wu, Private Matchings and Allocations, full version of STOC '14 paper.
R. Cole and T. Roughgarden, The Sample Complexity of Revenue Maximization, STOC '14.
R. Gupta, T. Roughgarden, and C. Seshadhri, Decompositions of Triangle-Dense Graphs, ITCS '14/SICOMP '16. (Lecture notes) (Related talk)

2013

T. Roughgarden and M. Kearns, Marginals-to-Models Reducibility, NIPS '13.
T. Roughgarden and I. Talgam-Cohen, Optimal and Near-Optimal 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, Prior-Free Multi-Unit Auctions with Ordered Bidders, EC '13 (full version, combined with STOC '12 paper, as of May '14).

2012

K. Bhawalkar and T. Roughgarden, Simultaneous Single-Item Auctions, WINE '12.
K. Bhawalkar, J. Kleinberg, K. Lewi, T. Roughgarden, and A. Sharma, Preventing Unraveling in Social Networks: The Anchored k-Core Problem, ICALP '12/SIDMA '15.
T. Roughgarden, Intrinsic Robustness of the Price of Anarchy, Communications of the ACM, July 2012. ("Reader's digest" 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. Talgam-Cohen, 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 Supply-Limiting 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, Prior-Free 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 Primal-Dual 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, Black-Box 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 Worst-Case 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.
- Section 6 subsumes the working paper Is Efficiency Expensive?, presented at the 3rd Workshop on Sponsored Search, 2007.
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/JACM '15. See also CACM version above. (Related talk)
A. Ghosh, T. Roughgarden, and M. Sundararajan, Universally Utility-Maximizing 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 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.
- For a more recent (2016) version with a different emphasis and some new results, see Optimal Platform Design.
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. 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/Networks '12.
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.
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 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, appeared in SIDMA '11.

2003

A. Gupta, A. Kumar, M. Pal, and T. Roughgarden, Approximation Via Cost Sharing, FOCS '03.
- Journal version, combined with STOC '03 paper below. Appears in JACM '07.
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

T. Roughgarden, Designing Networks for Selfish Users is Hard, FOCS '01/JCSS '06.
T. Roughgarden, Stackelberg Scheduling Strategies, STOC '01/SICOMP '04.
F. Chudak, T. Roughgarden, and D. Williamson, Approximate k-MSTs and k-Steiner trees via the primal-dual method and Lagrangean relaxation, IPCO '01/Mathematical Programming '04.

2000

T. Roughgarden and E. Tardos, How Bad is Selfish Routing?, FOCS '00/JACM '02.

Home