Bio


Roughgarden's research interests lie on the interface of computer science and game theory, and he is currently investigating a wide range of game-theoretic issues in networks and auctions.

Academic Appointments


  • Associate Professor, Computer Science
  • Associate Professor (By courtesy), Management Science and Engineering

Honors & Awards


  • Doctoral Dissertation Award, Honorable Mention, ACM (2002)
  • Tucker Prize, Mathematical Programming Society (2003)
  • Optimization Prize for Young Researchers, INFORMS (2003)
  • Alfred P. Sloan Fellow, Alfred P. Sloan (2006)
  • Young Investigator, ONR (2007)
  • Presidential Early Career Award for Scientists and Engineers (PECASE), PECASE (2007)
  • Shapley Lecturer, Shapley Lecturer (2008)
  • Grace Murray Hopper Award, ACM (2009)
  • Godel Prize, EATCS-SIGACT (2012)

Professional Education


  • PhD, Cornell (2002)

2013-14 Courses


Journal Articles


  • Bottleneck links, variable demand, and the tragedy of the commons NETWORKS Cole, R., Dodis, Y., Roughgarden, T. 2012; 60 (3): 194-203

    View details for DOI 10.1002/net.21458

    View details for Web of Science ID 000308311800005

  • Intrinsic Robustness of the Price of Anarchy COMMUNICATIONS OF THE ACM Roughgarden, T. 2012; 55 (7): 116-123
  • UNIVERSALLY UTILITY-MAXIMIZING PRIVACY MECHANISMS SIAM JOURNAL ON COMPUTING Ghosh, A., Roughgarden, T., Sundararajan, M. 2012; 41 (6): 1673-1693

    View details for DOI 10.1137/09076828X

    View details for Web of Science ID 000312600700014

  • Do Externalities Degrade GSP’s Efficiency? Ad Auctions '12. Roughgarden, T., Tardos, E. 2012
  • TRUTHFUL APPROXIMATION SCHEMES FOR SINGLE- PARAMETER AGENTS SIAM JOURNAL ON COMPUTING Dhangwatnotai, P., Dobzinski, S., Dughmi, S., Roughgarden, T. 2011; 40 (3): 915-933

    View details for DOI 10.1137/080744992

    View details for Web of Science ID 000292108900015

  • From Convex Optimization to Randomized Mechanisms: Toward Optimal Combinatorial Auctions STOC 11: PROCEEDINGS OF THE 43RD ACM SYMPOSIUM ON THEORY OF COMPUTING Dughmi, S., Roughgarden, T., Yan, Q. 2011: 149-158
  • Uncoupled Potentials for Proportional Allocation Markets 2011 50TH IEEE CONFERENCE ON DECISION AND CONTROL AND EUROPEAN CONTROL CONFERENCE (CDC-ECC) Nadav, U., Johari, R., Roughgarden, T. 2011: 4479-4484
  • Local Smoothness and the Price of Anarchy in Atomic Splittable Congestion Games PROCEEDINGS OF THE TWENTY-SECOND ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS Roughgarden, T., Schoppmann, F. 2011: 255-267
  • Welfare Guarantees for Combinatorial Auctions with Item Bidding PROCEEDINGS OF THE TWENTY-SECOND ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS Bhawalkar, K., Roughgarden, T. 2011: 700-709
  • STRONGER BOUNDS ON BRAESS'S PARADOX AND THE MAXIMUM LATENCY OF SELFISH ROUTING SIAM JOURNAL ON DISCRETE MATHEMATICS Lin, H., Roughgarden, T., Tardos, E., Walkover, A. 2011; 25 (4): 1667-1686

    View details for DOI 10.1137/090769600

    View details for Web of Science ID 000298348400011

  • Braess's Paradox in Large Random Graphs RANDOM STRUCTURES & ALGORITHMS Valiant, G., Roughgarden, T. 2010; 37 (4): 495-515

    View details for DOI 10.1002/rsa.20325

    View details for Web of Science ID 000284038400006

  • Algorithmic Game Theory COMMUNICATIONS OF THE ACM Roughgarden, T. 2010; 53 (7): 78-86
  • Computing equilibria: a computational complexity perspective ECONOMIC THEORY Roughgarden, T. 2010; 42 (1): 193-236
  • FULLY DISTRIBUTED ALGORITHMS FOR CONVEX OPTIMIZATION PROBLEMS SIAM JOURNAL ON OPTIMIZATION Mosk-Aoyama, D., Roughgarden, T., Shah, D. 2010; 20 (6): 3260-3279

    View details for DOI 10.1137/080743706

    View details for Web of Science ID 000285547100024

  • The Limits of Smoothness: A Primal-Dual Framework for Price of Anarchy Bounds INTERNET AND NETWORK ECONOMICS Nadav, U., Roughgarden, T. 2010; 6484: 319-326
  • Generalized Efficiency Bounds In Distributed Resource Allocation 49TH IEEE CONFERENCE ON DECISION AND CONTROL (CDC) Marden, J. R., Roughgarden, T. 2010: 2233-2238
  • Weighted Congestion Games: Price of Anarchy, Universal Worst-Case Examples, and Tightness ALGORITHMS-ESA 2010, PT II Bhawalkar, K., Gairing, M., Roughgarden, T. 2010; 6347: 17-28
  • DESIGNING NETWORK PROTOCOLS FOR GOOD EQUILIBRIA SIAM JOURNAL ON COMPUTING Chen, H., Roughgarden, T., Valiant, G. 2010; 39 (5): 1799-1832

    View details for DOI 10.1137/08072721X

    View details for Web of Science ID 000277584700005

  • Black-Box Randomized Reductions in Algorithmic Mechanism Design 2010 IEEE 51ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE Dughmi, S., Roughgarden, T. 2010: 775-784
  • Interactive Privacy via the Median Mechanism STOC 2010: PROCEEDINGS OF THE 2010 ACM SYMPOSIUM ON THEORY OF COMPUTING Roth, A., Roughgarden, T. 2010: 765-774
  • Equilibrium Efficiency and Price Complexity in Sponsored Search Auctions Workshop on Ad Auctions. Babaioff, M., Roughgarden, T. 2010
  • Quantifying Inefficiency in Cost-Sharing Mechanisms JOURNAL OF THE ACM Roughgarden, T., Sundararajan, M. 2009; 56 (4)
  • Intrinsic Robustness of the Price of Anarchy STOC'09: PROCEEDINGS OF THE 2009 ACM SYMPOSIUM ON THEORY OF COMPUTING Roughgarden, T. 2009: 513-522
  • Lightweight Coloring and Desynchronization for Networks IEEE INFOCOM 2009 - IEEE CONFERENCE ON COMPUTER COMMUNICATIONS, VOLS 1-5 Motskin, A., Roughgarden, T., Skraba, P., Guibas, L. 2009: 2383-2391
  • Simple versus Optimal Mechanisms 10TH ACM CONFERENCE ON ELECTRONIC COMMERCE - EC 2009 Hartline, J. D., Roughgarden, T. 2009: 225-234
  • Universally Utility-Maximizing Privacy Mechanisms STOC'09: PROCEEDINGS OF THE 2009 ACM SYMPOSIUM ON THEORY OF COMPUTING Ghosh, A., Roughgarden, T., Sundararajan, M. 2009: 351-359
  • Revenue Submodularity AUCTIONS, MARKET MECHANISMS AND THEIR APPLICATIONS Dughmi, S., Roughgarden, T., Sundararajan, M. 2009; 14: 89-91
  • Revenue Submodularity 10TH ACM CONFERENCE ON ELECTRONIC COMMERCE - EC 2009 Dughmi, S., Roughgarden, T., Sundararajan, M. 2009: 243-252
  • Worst-Case Efficiency Analysis of Queueing Disciplines AUTOMATA, LANGUAGES AND PROGRAMMING, PT II, PROCEEDINGS Mosk-Aoyama, D., Roughgarden, T. 2009; 5556: 546-557
  • Computing correlated equilibria in multi-player games JOURNAL OF THE ACM Papadimitriou, C. H., Roughgarden, T. 2008; 55 (3)
  • Optimal Mechanism Design and Money Burning STOC'08: PROCEEDINGS OF THE 2008 ACM INTERNATIONAL SYMPOSIUM ON THEORY OF COMPUTING Hartline, J. D., Roughgarden, T. 2008: 75-84
  • Metric Clustering via Consistent Labeling PROCEEDINGS OF THE NINETEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS Krauthgamer, R., Roughgarden, T. 2008: 809-818
  • Algorithmic game theory: Some greatest hits and future directions FIFTH IFIP INTERNATIONAL CONFERENCE ON THEORETICAL COMPUTER SCIENCE - TCS 2008 Roughgarden, T. 2008; 273: 21-42
  • Designing Networks with Good Equilibria PROCEEDINGS OF THE NINETEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS Chen, H., Roughgarden, T., Valiant, G. 2008: 854-863
  • Truthful Approximation Schemes for Single-Parameter Agents PROCEEDINGS OF THE 49TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE Dhangwatnotai, P., Dobzinski, S., Dughmi, S., Roughgarden, T. 2008: 15-24
  • Bertrand competition in networks ALGORITHMIC GAME THEORY, PROCEEDINGS Chawla, S., Roughgarden, T. 2008; 4997: 70-82
  • THE PRICE OF STABILITY FOR NETWORK DESIGN WITH FAIR COST ALLOCATION SIAM JOURNAL ON COMPUTING Anshelevich, E., Dasgupta, A., Kleinberg, J., Tardos, E., Wexler, T., Roughgarden, T. 2008; 38 (4): 1602-1623

    View details for DOI 10.1137/070680096

    View details for Web of Science ID 000261891600017

  • Is Shapley cost sharing optimal? ALGORITHMIC GAME THEORY, PROCEEDINGS Dobzinski, S., Mehta, A., Roughgarden, T., Sundaxarajan, M. 2008; 4997: 327-336
  • Non-cooperative behavior in networking IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS Buttyan, L., Hubaux, J., Li, L. (., Li, X., Roughgarden, T., Leon-Garcia, A. 2007; 25 (6): 1065-1068
  • The price of anarchy in an exponential multi-server OPERATIONS RESEARCH LETTERS Haviv, M., Roughgarden, T. 2007; 35 (4): 421-426
  • Beyond Moulin Mechanisms EC'07: PROCEEDINGS OF THE EIGHTH ANNUAL CONFERENCE ON ELECTRONIC COMMERCE Mehta, A., Roughgarden, T., Sundararajan, M. 2007: 1-10
  • Optimal efficiency guarantees for network design mechanisms INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, PROCEEDINGS Roughgarden, T., Sundararajan, M. 2007; 4513: 469-483
  • Approximation via cost sharing: Simpler and better approximation algorithms for network design JOURNAL OF THE ACM Gupta, A., Kumar, A., Pal, M., Roughgarden, T. 2007; 54 (3)
  • Fully distributed algorithms for convex optimization problems DISTRIBUTED COMPUTING, PROCEEDINGS Mosk-Aoyama, D., Roughgarden, T., Shah, D. 2007; 4731: 492-493
  • How much can taxes help selfish routing? JOURNAL OF COMPUTER AND SYSTEM SCIENCES Cole, R., Dodis, Y., Roughgarden, T. 2006; 72 (3): 444-467
  • Planning tours of robotic arms among partitioned goals INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH Saha, M., Roughgarden, T., Latombe, J. C., Sanchez-Ante, G. 2006; 25 (3): 207-223
  • Optimal cost-sharing mechanisms for Steiner forest problems INTERNET AND NETWORK ECONOMICS, PROCEEDINGS Chawla, S., Roughgarden, T., Sundararajan, M. 2006; 4286: 112-123
  • Routers with very small buffers 25TH IEEE INTERNATIONAL CONFERENCE ON COMPUTER COMMUNICATIONS, VOLS 1-7, PROCEEDINGS IEEE INFOCOM 2006 Enachescu, M., Ganjali, Y., Goel, A., McKeown, N., Roughgarden, T. 2006: 1833-1843
  • Single-source stochastic routing APPROXIMATION, RANDOMIZATION AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES Chawla, S., Roughgarden, T. 2006; 4110: 82-94
  • Bottleneck Links, Variable Demand, and the Tragedy of the Commons PROCEEDINGS OF THE SEVENTHEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS Cole, R., Dodis, Y., Roughgarden, T. 2006: 668-677
  • Part III: Routers with very small buffers COMPUTER COMMUNICATION REVIEW Enachescu, M., Ganjali, Y., Goel, A., McKeown, N., Roughgarden, T. 2005; 35 (3): 83-89
  • Selfish Routing with Atomic Players PROCEEDINGS OF THE SIXTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS Roughgarden, T. 2005: 1184-1185
  • Computing Equilibria in Multi-Player Games PROCEEDINGS OF THE SIXTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS Papadimitriou, C. H., Roughgarden, T. 2005: 82-91
  • Braess's Paradox, Fibonacci numbers, and exponential inapproximability AUTOMATA, LANGUAGES AND PROGRAMMING, PROCEEDINGS Lin, H., Roughgarden, T., Tardos, E., Walkover, A. 2005; 3580: 497-512
  • Routers with Very Small Buffers ACM Computer Communication Review. Enachescu, M., Ganjali, Y., Goel, A., McKeown, N., Roughgarden, T. 2005
  • Bounding the inefficiency of equilibria in nonatomic congestion games GAMES AND ECONOMIC BEHAVIOR Roughgarden, T., Tardos, E. 2004; 47 (2): 389-403
  • The price of stability for network design with fair cost allocation 45TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS Anshelevich, E., Dasgupta, A., Kleinberg, J., Tardos, E., Wexler, T., Roughgarden, T. 2004: 295-304
  • How bad is selfish routing? 41ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS Roughgarden, T., Tardos, E. 2000: 93-102
  • Climate change policy: quantifying uncertainties for damages and optimal carbon taxes ENERGY POLICY Roughgarden, T., Schneider, S. H. 1999; 27 (7): 415-429

Books and Book Chapters


  • Introduction to the Inefficiency of Equilibria Chapter 17 in Algorithmic Game Theory. Roughgarden, T., Tardos, E. 2008
  • Routing Games Chapter 18 in Algorithmic Game Theory. Roughgarden, T. 2008
  • Algorithmic Game Theory edited by N., T., E. Cambridge University Press.. 2007
  • Selfish Routing and the Price of Anarchy T. MIT Press.. 2005

Conference Proceedings


  • Decompositions of Triangle-Dense Graphs Gupta, R., Roughgarden, T., Seshadhri, C. 2014
  • Near-Optimal Multi-Unit Auctions with Ordered Bidders Bhattacharya, S., Koutsoupias, E., Kulkarni, J., Leonardi, S., Roughgarden, T., Xu, X. 2013
  • Marginals-to-Models Reducibility Roughgarden, T., Kearns, M. 2013
  • Optimal and Near-Optimal Mechanism Design with Interdependent Values Roughgarden, T., Talgam-Cohen, I. 2013
  • Combinatorial Auctions with Restricted Complements Abraham, I., Babaioff, M., Dughmi, S., Roughgarden, T. 2012
  • The Price of Anarchy in Games of Incomplete Information Roughgarden, T. 2012
  • Sketching Valuation Functions Badanidiyuru, A., Dobzinski, S., Fu, H., Kleinberg, R., D., Nisan, N., Roughgarden, T. 2012
  • Simultaneous Single-Item Auctions Bhawalkar, K., Roughgarden, T. 2012
  • Do Externalities Degrade GSP’s Efficiency? Roughgarden, T., Tardos, E. 2012
  • Supply-Limiting Mechanisms Roughgarden, T., Talgam-Cohen, I., Yan, Q. 2012
  • Prior-Free Auctions with Ordered Bidders Leonardi, S., Roughgarden, T. 2012
  • Preventing Unraveling in Social Networks: The Anchored k-Core Problem Bhawalkar, K., Kleinberg, J., Lewi, K., Roughgarden, T., Sharma, A. 2012
  • Restoring Pure Equilibria to Weighted Congestion Games Kollias, K., Roughgarden, T. 2011
  • Flexible Tree Matching Kumar, R., Talton, J., Ahmad, S., Roughgarden, T., Klemmer, S. 2011
  • Revenue Maximization with a Single Sample Dhangwotnotai, P., Roughgarden, T., Yan, Q. 2010
  • Beyond Moulin mechanisms Mehta, A., Roughgarden, T., Sundararajan, M. ACADEMIC PRESS INC ELSEVIER SCIENCE. 2009: 125-155
  • Network Design with Weighted Players Chen, H., Roughgarden, T. SPRINGER. 2009: 302-324
  • An Algorithmic Game Theory Primer Roughgarden, T. 2008
  • Selfish Routing and the Price of Anarchy (Survey) Roughgarden, T. 2007
  • Fully Distributed Algorithms for Convex Optimization Mosk-Aoyama, D., Roughgarden, T., Shah, D. 2007
  • On the severity of Braess's Paradox: Designing networks for selfish users is hard Roughgarden, T. ACADEMIC PRESS INC ELSEVIER SCIENCE. 2006: 922-953
  • Quantifying Inefficiency in Cost-Sharing Mechanisms Roughgarden, T., Sundararajan, M. 2006
  • Potential Functions and the Inefficiency of Equilibria (Survey) Roughgarden, T. 2006
  • Network Design with Weighted Players Chen, H., Roughgarden, T. 2006
  • Braess's Paradox in Large Random Graphs Valiant, G., Roughgarden, T. 2006
  • Bottleneck Links, Variable Demand, and the Tragedy of the Commons Cole, R., Dodis, Y., Roughgarden, T. 2006
  • An Interview with Vladimir Trifonov (2005 Danny Lewin Best Student Paper Award Winner) Roughgarden, T. 2005
  • Computing Correlated Equilibria in Multi-Player Games Papadimitriou, C., Roughgarden, T. 2005
  • The Maximum Latency of Selfish Routing Roughgarden, T. 2004
  • A Stronger Bound on Braess's Paradox Lin, H., Roughgarden, T., Tardos, E. 2004
  • Simpler and Better Approximation Algorithms for Network Design Gupta, A., Kumar, A., Roughgarden, T. 2003
  • Approximation Via Cost Sharing Gupta, A., Kumar, A., Pal, M., Roughgarden, T. 2003
  • Pricing Network Edges for Heterogeneous Selfish Users Cole, R., Dodis, Y., Roughgarden, T. 2003
  • How Much Can Taxes Help Selfish Routing? Cole, R., Dodis, Y., Roughgarden, T. 2003
  • A Constant-Factor Approximation Algorithm for the Multicommodity Rent-or-Buy Problem Kumar, A., Gupta, A., Roughgarden, T. 2002
  • The Price of Anarchy is Independent of the Network Topology Roughgarden, T. 2002
  • On a Game in Directed Graphs Hoffman, A., Jenkins, K., Roughgarden, T. 2002
  • How Unfair is Optimal Routing? Roughgarden, T. 2002
  • Approximate k-MSTs and k-Steiner trees via the primal-dual method and Lagrangean relaxation Chudak, F., Roughgarden, T., Williamson, D. 2001
  • Stackelberg Scheduling Strategies Roughgarden, T. 2001
  • Designing Networks for Selfish Users is Hard Roughgarden, T. 2001