Location via proxy:   [ UP ]   [Report a bug]   [Manage cookies]    No cookies    No scripts    No ads    No referrer    Show this form

Tim Roughgarden's Papers by Topic
(See also DBLP for further bibliographic information.)

• Algorithmic Game Theory (Books and Surveys)
• Applications of Algorithms
• Approximation Algorithms
• Auctions and Mechanism Design
  • Surveys
  • Algorithmic Mechanism Design
  • Contracts
  • Cost-Sharing Mechanisms
  • Learning Auctions from Data
  • Lower Bounds and Complexity
  • Revenue-Maximizing Auctions
  • Simple Auctions
  • Sponsored Search Auctions
• Beyond Worst-Case Analysis
• Communication Complexity
• Complexity (Misc)
• Computing Equilibria
• Cryptocurrencies
• Differential Privacy
• Fair Division
• Inference
• MapReduce
• Network Games (other than Routing)
• Online Learning
• Price of Anarchy
  • Surveys
  • Lower Bounds
  • POA Bounds for Specific Games (other than Routing and Auctions)
  • Smooth Games and Robust POA Bounds
• Routing Games
  • Surveys
  • Braess's Paradox
  • Fairness
  • Price of Anarchy in Routing Games
  • Stackelberg Routing and Tolls
• Social Computing
• Social Networks
• Other

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. Sanchez-Ante, 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 Non-monotone Submodular and DR-Submodular Maximization, arXiv.
• T. Roughgarden, I. Talgam-Cohen, 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, Single-Source Stochastic Routing, APPROX '06.
• 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.)
• 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.
• 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.

Auction and Mechanism Design

Surveys

• T. Roughgarden, V. Syrgkanis, and E. Tardos, The Price of Anarchy in Auctions (survey), Journal of Artificial Intelligence Research.
• T. Roughgarden, Approximately Optimal Mechanism Design: Motivation, Examples, and Lessons Learned, SIGEcom Exchanges, 2014.

Algorithmic Mechanism Design

• V. Gkatzelis, E. Markakis, and T. Roughgarden, Deferred-Acceptance Auctions for Multiple Levels of Service, EC '17.
• 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.
• 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, Black-Box Randomized Reductions in Algorithmic Mechanism Design, FOCS '10/SICOMP '14.
• P. Dhangwatnotai, S. Dobzinski, S. Dughmi, and T. Roughgarden, Truthful Approximation Schemes for Single-Parameter Agents, FOCS '08/SICOMP '11.

Contracts

• P. Duetting, T. Roughgarden, and I. Talgam-Cohen, Simple versus Optimal Contracts, arXiv.

Cost-Sharing 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 Cost-Sharing Mechanisms for Steiner Forest Problems, WINE '06.
• T. Roughgarden and M. Sundararajan, Quantifying Inefficiency in Cost-Sharing 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 Pseudo-Dimension of Near-Optimal 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. 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)
• T. Roughgarden, Barriers to Near-Optimal Equilibria, FOCS '14. FOCS talk (Lecture notes)

Revenue-Maximizing Auctions

• 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).
• 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).
• 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.
• 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.
  • Section 6 subsumes the working paper Is Efficiency Expensive?, presented at the 3rd Workshop on Sponsored Search, 2007.
• 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.

Simple Auctions

• T. Ezra, M. Feldman, T. Roughgarden, and W. Suksompong, Pricing Identical Items, arXiv.
• R. Colini-Baldeschi, P. Goldberg, B. de Keijzer, S. Leonardi, T. Roughgarden, and S. Turchetta, Approximately Efficient Two-Sided Combinatorial Auctions, EC '17.
• K. Bhawalkar and T. Roughgarden, Simultaneous Single-Item 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

• T. Roughgarden and E. Tardos, Do Externalities Degrade GSP’s Efficiency?, Ad Auctions '12.
• M. Babaioff and T. Roughgarden, Equilibrium Efficiency and Price Complexity in Sponsored Search Auctions, Workshop on Ad Auctions '10.

Beyond Worst-Case Analysis

• 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.
• V. Chatziafratis, T. Roughgarden, and J. Vondrak, Stability and Recovery for Independence Systems, ESA '17.
• R. Gupta and T. Roughgarden, A PAC Approach to Application-Specific Algorithm Selection, ITCS '16/SICOMP '17. (Talk)
• R. Gupta, T. Roughgarden, and C. Seshadhri, Decompositions of Triangle-Dense Graphs, ITCS '14/SICOMP '16. (Lecture notes) (Related talk)

Communication Complexity

• B. Plaut and T. Roughgarden, Communication Complexity of Discrete Fair Division, arXiv.
• T. Roughgarden and O. Weinstein, On the Communication Complexity of Approximate Fixed Points, FOCS '16. (Talk by Omri)
• T. Roughgarden, Communication Complexity (for Algorithm Designers), Foundations and Trends in TCS, 2016. (arXiv version)

Complexity (Misc)

• V. Chatziafratis, T. Roughgarden, and J. R. Wang, On the Computational Power of Online Gradient Descent, arXiv.
• T. Roughgarden and J. R. Wang, The Complexity of the k-Means Method, ESA '16.

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 Multi-Player Games, SODA '05/JACM '08. Addendum

Cryptocurrencies

• O. Schrijvers, J. Bonneau, D. Boneh, and T. Roughgarden, Incentive Compatibility of Bitcoin Mining Pool Reward Functions, FC '16.

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 Utility-Maximizing Privacy Mechanisms, STOC '09/SICOMP '12.

Fair Division

• B. Plaut and T. Roughgarden, Communication Complexity of Discrete Fair Division, arXiv.
• B. Plaut and T. Roughgarden, Almost Envy-Freeness with General Valuations, SODA '18.

Inference

• A. Globerson, T. Roughgarden, D. Sontag, and C. Yildirim, How Hard Is Inference for Structured Prediction? , ICML '15. (arXiv) (Talk)
• T. Roughgarden and M. Kearns, Marginals-to-Models Reducibility, NIPS '13.

MapReduce

• T. Roughgarden, S. Vassilvitskii, and J. R. Wang, Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation), SPAA '16/JACM '18.

Network Games (other than Routing)

• T. Roughgarden and O. Schrijvers, Network Cost-Sharing 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

• T. Roughgarden, V. Syrgkanis, and E. Tardos, The Price of Anarchy in Auctions (survey), Journal of Artificial Intelligence Research, 2017.
• T. Roughgarden and E. Tardos, Introduction to the Inefficiency of Equilibria, Chapter 17 in Algorithmic Game Theory.
• T. Roughgarden, Potential Functions and the Inefficiency of Equilibria (Survey), ICM '06.

Lower Bounds

• T. Roughgarden, Barriers to Near-Optimal Equilibria, FOCS '14. FOCS talk (Lecture notes)

POA Bounds for Specific Games (other than Routing and Auctions)

• J. Marden and T. Roughgarden, Generalized Efficiency Bounds in Distributed Resource Allocation, CDC '10/IEEE TAC '14.
• D. Mosk-Aoyama and T. Roughgarden, Worst-Case Efficiency Analysis of Queueing Disciplines, ICALP '09.

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 Primal-Dual 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

• T. Roughgarden. Selfish Routing and the Price of Anarchy, MIT Press.
• T. Roughgarden, Selfish Routing and the Price of Anarchy (Survey), OPTIMA #74.
• T. Roughgarden, Routing Games, Chapter 18 in Algorithmic Game Theory.
• T. Roughgarden, Selfish Routing, PhD Thesis, Cornell University.

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

• T. Roughgarden, The Maximum Latency of Selfish Routing, SODA '04.
• T. Roughgarden, How Unfair is Optimal Routing?, SODA '02.

Price of Anarchy in Routing Games

• V. Gkatzelis, K. Kollias, and T. Roughgarden, Optimal Cost-Sharing 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 Worst-Case Examples, and Tightness, ESA '10/ACM TEAC '14.
• M. Haviv and T. Roughgarden, The Price of Anarchy in an Exponential Multi-Server, 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

• Y. Chen, A. Ghosh, M. Kearns, T. Roughgarden, and J. Wortman Vaughan, Mathematical Foundations for Social Computing, Communications of the ACM, December 2016. (Preprint)

Social Networks

• 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.
• J. Fox, T. Roughgarden, C. Seshadhri, F. Wei, and N. Wein, Finding Cliques in Social Networks: A New Distribution-Free Model, ICALP '18.
• R. Gupta, T. Roughgarden, and C. Seshadhri, Decompositions of Triangle-Dense 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 k-Core Problem, ICALP '12/SIDMA '15.

Other

• D. Mosk-Aoyama, T. Roughgarden, and D. Shah, Fully Distributed Algorithms for Convex Optimization, DISC '07/SIAM J on Optimization '10.
• A. Hoffman, K. Jenkins, and T. Roughgarden, On a Game in Directed Graphs, IPL '02.

Home