Tim Roughgarden

According to our database1, Tim Roughgarden
  • authored at least 191 papers between 2000 and 2018.
  • has a "Dijkstra number"2 of four.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2018
Complexity Theory, Game Theory, and Economics.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Almost Envy-Freeness with General Valuations.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017
A PAC Approach to Application-Specific Algorithm Selection.
SIAM J. Comput., 2017

The Price of Anarchy in Auctions.
J. Artif. Intell. Res., 2017

Modularity and greed in double auctions.
Games and Economic Behavior, 2017

Communication Complexity of Discrete Fair Division.
CoRR, 2017

Online Prediction with Selfish Experts.
CoRR, 2017

Almost Envy-Freeness with General Valuations.
CoRR, 2017

Pricing Identical Items.
CoRR, 2017

Stability and Recovery for Independence Systems.
CoRR, 2017

Why prices need algorithms (invited talk).
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Deferred-Acceptance Auctions for Multiple Levels of Service.
Proceedings of the 2017 ACM Conference on Economics and Computation, 2017

Approximately Efficient Two-Sided Combinatorial Auctions.
Proceedings of the 2017 ACM Conference on Economics and Computation, 2017

Online Prediction with Selfish Experts.
Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Stability and Recovery for Independence Systems.
Proceedings of the 25th Annual European Symposium on Algorithms, 2017

When Are Welfare Guarantees Robust?.
Proceedings of the Approximation, 2017

2016
Optimal and Robust Mechanism Design with Interdependent Values.
ACM Trans. Economics and Comput., 2016

Network Cost-Sharing without Anonymity.
ACM Trans. Economics and Comput., 2016

Private Matchings and Allocations.
SIAM J. Comput., 2016

Decompositions of Triangle-Dense Graphs.
SIAM J. Comput., 2016

Optimal Mechanisms for Combinatorial Auctions and Combinatorial Public Projects via Convex Rounding.
J. ACM, 2016

Optimal Cost-Sharing in General Resource Selection Games.
Operations Research, 2016

Communication Complexity (for Algorithm Designers).
Foundations and Trends in Theoretical Computer Science, 2016

On the Communication Complexity of Approximate Fixed Points.
Electronic Colloquium on Computational Complexity (ECCC), 2016

When Are Welfare Guarantees Robust?
CoRR, 2016

The Price of Anarchy in Auctions.
CoRR, 2016

Learning Simple Auctions.
CoRR, 2016

Approximately Efficient Two-Sided Combinatorial Auctions.
CoRR, 2016

Mathematical foundations for social computing.
Commun. ACM, 2016

The price of anarchy in large games.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Shuffles and Circuits: (On Lower Bounds for Modern Parallel Computation).
Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, 2016

Minimizing Regret with Multiple Reserves.
Proceedings of the 2016 ACM Conference on Economics and Computation, 2016

Ironing in the Dark.
Proceedings of the 2016 ACM Conference on Economics and Computation, 2016

Intrinsic Robustness of the Price of Anarchy: Abstract of the Kalai Prize Talk.
Proceedings of the 2016 ACM Conference on Economics and Computation, 2016

A PAC Approach to Application-Specific Algorithm Selection.
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

Why Prices Need Algorithms.
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, 2016

On the Communication Complexity of Approximate Fixed Points.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Incentive Compatibility of Bitcoin Mining Pool Reward Functions.
Proceedings of the Financial Cryptography and Data Security, 2016

The Complexity of the k-means Method.
Proceedings of the 24th Annual European Symposium on Algorithms, 2016

Learning Simple Auctions.
Proceedings of the 29th Conference on Learning Theory, 2016

2015
The Price of Anarchy in Games of Incomplete Information.
ACM Trans. Economics and Comput., 2015

Restoring Pure Equilibria to Weighted Congestion Games.
ACM Trans. Economics and Comput., 2015

Why prices need algorithms.
SIGecom Exchanges, 2015

Preventing Unraveling in Social Networks: The Anchored k-Core Problem.
SIAM J. Discrete Math., 2015

Special Section on the Fifty-Third IEEE Annual Symposium on Foundations of Computer Science (FOCS 2012).
SIAM J. Comput., 2015

Local smoothness and the price of anarchy in splittable congestion games.
J. Economic Theory, 2015

Intrinsic Robustness of the Price of Anarchy.
J. ACM, 2015

Revenue maximization with a single sample.
Games and Economic Behavior, 2015

Special Section of Games and Economic Behavior dedicated to the 11th and 12th ACM Conference on Electronic Commerce.
Games and Economic Behavior, 2015

Introduction to the Special Issue - Algorithmic Game Theory - STOC/FOCS/SODA 2011.
Games and Economic Behavior, 2015

Communication Complexity (for Algorithm Designers).
Electronic Colloquium on Computational Complexity (ECCC), 2015

Computing Equilibria: A Computational Complexity Perspective.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Ironing in the Dark.
CoRR, 2015

Communication Complexity (for Algorithm Designers).
CoRR, 2015

The Pseudo-Dimension of Near-Optimal Auctions.
CoRR, 2015

A PAC Approach to Application-Specific Algorithm Selection.
CoRR, 2015

Public projects, Boolean functions and the borders of Border's theorem.
CoRR, 2015

The Price of Anarchy in Large Games.
CoRR, 2015

The Sample Complexity of Revenue Maximization.
CoRR, 2015

Why Prices Need Algorithms.
Proceedings of the Sixteenth ACM Conference on Economics and Computation, 2015

Public Projects, Boolean Functions, and the Borders of Border's Theorem.
Proceedings of the Sixteenth ACM Conference on Economics and Computation, 2015

Making the Most of Your Samples.
Proceedings of the Sixteenth ACM Conference on Economics and Computation, 2015

On the Pseudo-Dimension of Nearly Optimal Auctions.
Proceedings of the Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, 2015

How Hard is Inference for Structured Prediction?
Proceedings of the 32nd International Conference on Machine Learning, 2015

2014
Weighted Congestion Games: The Price of Anarchy, Universal Worst-Case Examples, and Tightness.
ACM Trans. Economics and Comput., 2014

Generalized Efficiency Bounds in Distributed Resource Allocation.
IEEE Trans. Automat. Contr., 2014

Approximately optimal mechanism design: motivation, examples, and lessons learned.
SIGecom Exchanges, 2014

Black-Box Randomized Reductions in Algorithmic Mechanism Design.
SIAM J. Comput., 2014

Analysis of Algorithms Beyond the Worst Case (Dagstuhl Seminar 14372).
Dagstuhl Reports, 2014

Approximately Optimal Mechanism Design: Motivation, Examples, and Lessons Learned.
CoRR, 2014

Making the Most of Your Samples.
CoRR, 2014

Privately Solving Linear Programs.
CoRR, 2014

Optimal Platform Design.
CoRR, 2014

Tight Error Bounds for Structured Prediction.
CoRR, 2014

Optimal Cost-Sharing in Weighted Congestion Games.
Proceedings of the Web and Internet Economics - 10th International Conference, 2014

Private matchings and allocations.
Proceedings of the Symposium on Theory of Computing, 2014

The sample complexity of revenue maximization.
Proceedings of the Symposium on Theory of Computing, 2014

Modularity and greed in double auctions.
Proceedings of the ACM Conference on Economics and Computation, 2014

The performance of deferred-acceptance auctions.
Proceedings of the ACM Conference on Economics and Computation, 2014

Network Cost-Sharing without Anonymity.
Proceedings of the Algorithmic Game Theory - 7th International Symposium, 2014

Decompositions of triangle-dense graphs.
Proceedings of the Innovations in Theoretical Computer Science, 2014

Privately Solving Linear Programs.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Barriers to Near-Optimal Equilibria.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013
Private Matchings and Allocations.
CoRR, 2013

Decompositions of Triangle-Dense Graphs.
CoRR, 2013

Optimal and near-optimal mechanism design with interdependent values.
Proceedings of the ACM Conference on Electronic Commerce, 2013

Near-optimal multi-unit auctions with ordered bidders.
Proceedings of the ACM Conference on Electronic Commerce, 2013

Marginals-to-Models Reducibility.
Proceedings of the Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013

2012
Revenue Submodularity.
Theory of Computing, 2012

The price of anarchy in games of incomplete information.
SIGecom Exchanges, 2012

Universally Utility-maximizing Privacy Mechanisms.
SIAM J. Comput., 2012

Bottleneck links, variable demand, and the tragedy of the commons.
Networks, 2012

Near-Optimal Multi-Unit Auctions with Ordered Bidders
CoRR, 2012

Combinatorial Auctions with Restricted Complements
CoRR, 2012

Intrinsic robustness of the price of anarchy.
Commun. ACM, 2012

Simultaneous Single-Item Auctions.
Proceedings of the Internet and Network Economics - 8th International Workshop, 2012

Prior-free auctions with ordered bidders.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Sketching valuation functions.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Supply-limiting mechanisms.
Proceedings of the ACM Conference on Electronic Commerce, 2012

The price of anarchy in games of incomplete information.
Proceedings of the ACM Conference on Electronic Commerce, 2012

Combinatorial auctions with restricted complements.
Proceedings of the ACM Conference on Electronic Commerce, 2012

Preventing Unraveling in Social Networks: The Anchored k-Core Problem.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011
Metric Clustering via Consistent Labeling.
Theory of Computing, 2011

Stronger Bounds on Braess's Paradox and the Maximum Latency of Selfish Routing.
SIAM J. Discrete Math., 2011

Truthful Approximation Schemes for Single-Parameter Agents.
SIAM J. Comput., 2011

An approximately truthful-in-expectation mechanism for combinatorial auctions using value queries
CoRR, 2011

From Convex Optimization to Randomized Mechanisms: Toward Optimal Combinatorial Auctions for Submodular Bidders
CoRR, 2011

From convex optimization to randomized mechanisms: toward optimal combinatorial auctions.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Local Smoothness and the Price of Anarchy in Atomic Splittable Congestion Games.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Welfare Guarantees for Combinatorial Auctions with Item Bidding.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Flexible Tree Matching.
Proceedings of the IJCAI 2011, 2011

Restoring Pure Equilibria to Weighted Congestion Games.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

Uncoupled potentials for proportional allocation markets.
Proceedings of the 50th IEEE Conference on Decision and Control and European Control Conference, 2011

2010
Fully Distributed Algorithms for Convex Optimization Problems.
SIAM Journal on Optimization, 2010

Designing Network Protocols for Good Equilibria.
SIAM J. Comput., 2010

Braess's Paradox in large random graphs.
Random Struct. Algorithms, 2010

Algorithmic game theory.
Commun. ACM, 2010

The Limits of Smoothness: A Primal-Dual Framework for Price of Anarchy Bounds.
Proceedings of the Internet and Network Economics - 6th International Workshop, 2010

Interactive privacy via the median mechanism.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Revenue maximization with a single sample.
Proceedings of the Proceedings 11th ACM Conference on Electronic Commerce (EC-2010), 2010

Black-Box Randomized Reductions in Algorithmic Mechanism Design.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Weighted Congestion Games: Price of Anarchy, Universal Worst-Case Examples, and Tightness.
Proceedings of the Algorithms, 2010

Generalized efficiency bounds in distributed resource allocation.
Proceedings of the 49th IEEE Conference on Decision and Control, 2010

Truthfulness via smoothed complexity.
Proceedings of the Behavioral and Quantitative Game Theory, 2010

2009
Simple versus optimal mechanisms.
SIGecom Exchanges, 2009

Bertrand competition in networks.
SIGecom Exchanges, 2009

Network Design with Weighted Players.
Theory Comput. Syst., 2009

Quantifying inefficiency in cost-sharing mechanisms.
J. ACM, 2009

Beyond Moulin mechanisms.
Games and Economic Behavior, 2009

The Median Mechanism: Interactive and Efficient Privacy with Multiple Queries
CoRR, 2009

Intrinsic robustness of the price of anarchy.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Universally utility-maximizing privacy mechanisms.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Simple versus optimal mechanisms.
Proceedings of the Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), 2009

Revenue submodularity.
Proceedings of the Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), 2009

Lightweight Coloring and Desynchronization for Networks.
Proceedings of the INFOCOM 2009. 28th IEEE International Conference on Computer Communications, 2009

Worst-Case Efficiency Analysis of Queueing Disciplines.
Proceedings of the Automata, Languages and Programming, 36th Internatilonal Colloquium, 2009

Revenue Submodularity.
Proceedings of the Auctions, 2009

2008
The Price of Stability for Network Design with Fair Cost Allocation.
SIAM J. Comput., 2008

Computing correlated equilibria in multi-player games.
J. ACM, 2008

Universally Utility-Maximizing Privacy Mechanisms
CoRR, 2008

Optimal Mechansim Design and Money Burning
CoRR, 2008

Optimal mechanism design and money burning.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Metric clustering via consistent labeling.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Designing networks with good equilibria.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Is Shapley Cost Sharing Optimal?
Proceedings of the Algorithmic Game Theory, First International Symposium, 2008

Bertrand Competition in Networks.
Proceedings of the Algorithmic Game Theory, First International Symposium, 2008

Algorithmic Game Theory: Some Greatest Hits and Future Directions.
Proceedings of the Fifth IFIP International Conference On Theoretical Computer Science, 2008

Truthful Approximation Schemes for Single-Parameter Agents.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007
The price of anarchy in an exponential multi-server.
Oper. Res. Lett., 2007

Guest Editorial Non-Cooperative Behavior in Networking.
IEEE Journal on Selected Areas in Communications, 2007

Approximation via cost sharing: Simpler and better approximation algorithms for network design.
J. ACM, 2007

Fully Distributed Algorithms for Convex Optimization Problems.
Proceedings of the Distributed Computing, 21st International Symposium, 2007

Beyond moulin mechanisms.
Proceedings of the Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), 2007

Optimal Efficiency Guarantees for Network Design Mechanisms.
Proceedings of the Integer Programming and Combinatorial Optimization, 2007

2006
On the severity of Braess's Paradox: Designing networks for selfish users is hard.
J. Comput. Syst. Sci., 2006

How much can taxes help selfish routing?
J. Comput. Syst. Sci., 2006

Planning Tours of Robotic Arms among Partitioned Goals.
I. J. Robotics Res., 2006

Approximately Efficient Cost-Sharing Mechanisms
CoRR, 2006

Optimal Cost-Sharing Mechanisms for Steiner Forest Problems.
Proceedings of the Internet and Network Economics, Second International Workshop, 2006

New trade-offs in cost-sharing mechanisms.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Network design with weighted players.
Proceedings of the SPAA 2006: Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Cambridge, Massachusetts, USA, July 30, 2006

Bottleneck links, variable demand, and the tragedy of the commons.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Braess's paradox in large random graphs.
Proceedings of the Proceedings 7th ACM Conference on Electronic Commerce (EC-2006), 2006

Routers with Very Small Buffers.
Proceedings of the INFOCOM 2006. 25th IEEE International Conference on Computer Communications, 2006

Single-Source Stochastic Routing.
Proceedings of the Approximation, 2006

2005
An interview with Vladimir Trifonov 2005 Danny Lewin best student paper award winner.
SIGACT News, 2005

Part III: routers with very small buffers.
Computer Communication Review, 2005

Selfish routing with atomic players.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Computing equilibria in multi-player games.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Braess's Paradox, Fibonacci Numbers, and Exponential Inapproximability.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

Selfish routing and the price of anarchy.
MIT Press, ISBN: 978-0-262-18243-0, 2005

2004
Stackelberg Scheduling Strategies.
SIAM J. Comput., 2004

Approximate k-MSTs and k-Steiner trees via the primal-dual method and Lagrangean relaxation.
Math. Program., 2004

Bounding the inefficiency of equilibria in nonatomic congestion games.
Games and Economic Behavior, 2004

The maximum latency of selfish routing.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

A stronger bound on Braess's Paradox.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

The Price of Stability for Network Design with Fair Cost Allocation.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003
The price of anarchy is independent of the network topology.
J. Comput. Syst. Sci., 2003

Simpler and better approximation algorithms for network design.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Pricing network edges for heterogeneous selfish users.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

How much can taxes help selfish routing?
Proceedings of the Proceedings 4th ACM Conference on Electronic Commerce (EC-2003), 2003

Approximation Via Cost-Sharing: A Simple Approximation Algorithm for the Multicommodity Rent-or-Buy Problem.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2002
How bad is selfish routing?
J. ACM, 2002

On a game in directed graphs.
Inf. Process. Lett., 2002

The price of anarchy is independent of the network topology.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

How unfair is optimal routing?
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

A Constant-Factor Approximation Algorithm for the Multicommodity.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

2001
Stackelberg scheduling strategies.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Approximate k-MSTs and k-Steiner Trees via the Primal-Dual Method and Lagrangean Relaxation.
Proceedings of the Integer Programming and Combinatorial Optimization, 2001

Designing Networks for Selfish Users is Hard.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000
How Bad is Selfish Routing?
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000


  Loading...