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


  • Professor (By courtesy), Management Science and Engineering

Honors & Awards


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

Professional Education


  • PhD, Cornell (2002)

2018-19 Courses


Stanford Advisees


All Publications


  • The Price of Anarchy in Auctions JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH Roughgarden, T., Syrgkanis, V., Tardos, E. 2017; 59: 59–101

    View details for DOI 10.1613/jair.5272

    View details for Web of Science ID 000411179900002

  • Mathematical Foundations for Social Computing COMMUNICATIONS OF THE ACM Chen, Y., Ghosh, A., Kearns, M., Roughgarden, T., Vaughan, J. W. 2016; 59 (12): 102-108

    View details for DOI 10.1145/2960403

    View details for Web of Science ID 000391635300023

  • Optimal Cost-Sharing in General Resource Selection Games OPERATIONS RESEARCH Gkatzelis, V., Kollias, K., Roughgarden, T. 2016; 64 (6): 1230-1238
  • Optimal Mechanisms for Combinatorial Auctions and Combinatorial Public Projects via Convex Rounding JOURNAL OF THE ACM Dughmi, S., Roughgarden, T., Yan, Q. 2016; 63 (4)

    View details for DOI 10.1145/2908735

    View details for Web of Science ID 000394496300002

  • DECOMPOSITIONS OF TRIANGLE-DENSE GRAPHS SIAM JOURNAL ON COMPUTING Gupta, R., Roughgarden, T., Seshadhri, C. 2016; 45 (2): 197-215

    View details for DOI 10.1137/140955331

    View details for Web of Science ID 000375554000001

  • PRIVATE MATCHINGS AND ALLOCATIONS SIAM JOURNAL ON COMPUTING Hsu, J., Huang, Z., Roth, A., Roughgarden, T., Wu, Z. S. 2016; 45 (6): 1953-1984

    View details for DOI 10.1137/15100271X

    View details for Web of Science ID 000391838800001

  • Intrinsic Robustness of the Price of Anarchy JOURNAL OF THE ACM Roughgarden, T. 2015; 62 (5)

    View details for DOI 10.1145/2806883

    View details for Web of Science ID 000364039500001

  • Revenue maximization with a single sample GAMES AND ECONOMIC BEHAVIOR Dhangwatnotai, P., Roughgarden, T., Yan, Q. 2015; 91: 318-333
  • Local smoothness and the price of anarchy in splittable congestion games JOURNAL OF ECONOMIC THEORY Roughgarden, T., Schoppmann, F. 2015; 156: 317-342
  • PREVENTING UNRAVELING IN SOCIAL NETWORKS: THE ANCHORED K-CORE PROBLEM SIAM JOURNAL ON DISCRETE MATHEMATICS Bhawalkar, K., Kleinberg, J., Lewi, K., Roughgarden, T., Sharma, A. 2015; 29 (3): 1452-1475

    View details for DOI 10.1137/14097032X

    View details for Web of Science ID 000362419600018

  • Generalized Efficiency Bounds in Distributed Resource Allocation IEEE TRANSACTIONS ON AUTOMATIC CONTROL Marden, J. R., Roughgarden, T. 2014; 59 (3): 571-584
  • Decompositions of Triangle-Dense Graphs Gupta, R., Roughgarden, T., Seshadhri, C. 2014
  • Network Cost-Sharing without Anonymity 7th International Symposium on Algorithmic Game Theory (SAGT) Roughgarden, T., Schrijvers, O. SPRINGER-VERLAG BERLIN. 2014: 134–145
  • BLACK-BOX RANDOMIZED REDUCTIONS IN ALGORITHMIC MECHANISM DESIGN SIAM JOURNAL ON COMPUTING Dughmi, S., Roughgarden, T. 2014; 43 (1): 312-336

    View details for DOI 10.1137/110843654

    View details for Web of Science ID 000333538300017

  • 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
  • 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

  • Preventing Unraveling in Social Networks: The Anchored k-Core Problem 39th International Colloquium on Automata, Languages, and Programming (ICALP) Bhawalkar, K., Kleinberg, J., Lewi, K., Roughgarden, T., Sharma, A. SPRINGER-VERLAG BERLIN. 2012: 440–451
  • 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
  • Do Externalities Degrade GSP’s Efficiency? Ad Auctions '12. 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
  • Combinatorial Auctions with Restricted Complements Abraham, I., Babaioff, M., Dughmi, S., Roughgarden, T. 2012
  • Restoring Pure Equilibria to Weighted Congestion Games Kollias, K., Roughgarden, T. 2011
  • Restoring Pure Equilibria to Weighted Congestion Games 38th International Colloquium on Automata, Languages and Programming (ICALP) / Annual Meeting of the European-Association-for-Theoretical-Computer-Science (EATCS) Kollias, K., Roughgarden, T. SPRINGER-VERLAG BERLIN. 2011: 539–551
  • Flexible Tree Matching Kumar, R., Talton, J., Ahmad, S., Roughgarden, T., Klemmer, S. 2011
  • 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 43rd ACM Symposium on Theory of Computing Dughmi, S., Roughgarden, T., Yan, Q. ASSOC COMPUTING MACHINERY. 2011: 149–158
  • Uncoupled Potentials for Proportional Allocation Markets 50th IEEE Conference of Decision and Control (CDC)/European Control Conference (ECC) Nadav, U., Johari, R., Roughgarden, T. IEEE. 2011: 4479–4484
  • Local Smoothness and the Price of Anarchy in Atomic Splittable Congestion Games 22nd Annual ACM/SIAM Symposium on Discrete Algorithms Roughgarden, T., Schoppmann, F. SIAM. 2011: 255–267
  • Welfare Guarantees for Combinatorial Auctions with Item Bidding 22nd Annual ACM/SIAM Symposium on Discrete Algorithms Bhawalkar, K., Roughgarden, T. SIAM. 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
  • Generalized Efficiency Bounds In Distributed Resource Allocation 49th IEEE Conference on Decision and Control (CDC) Marden, J. R., Roughgarden, T. IEEE. 2010: 2233–2238
  • Revenue Maximization with a Single Sample Dhangwotnotai, P., Roughgarden, T., Yan, Q. 2010
  • Equilibrium Efficiency and Price Complexity in Sponsored Search Auctions Workshop on Ad Auctions. Babaioff, M., Roughgarden, T. 2010
  • 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 6th International Workshop on Internet and Network Economics Nadav, U., Roughgarden, T. SPRINGER-VERLAG BERLIN. 2010: 319–326
  • Weighted Congestion Games: Price of Anarchy, Universal Worst-Case Examples, and Tightness 18th European Symposium on Algorithms (ESA) Bhawalkar, K., Gairing, M., Roughgarden, T. SPRINGER-VERLAG BERLIN. 2010: 17–28
  • Computing equilibria: a computational complexity perspective ECONOMIC THEORY Roughgarden, T. 2010; 42 (1): 193-236
  • 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. IEEE COMPUTER SOC. 2010: 775–784
  • Interactive Privacy via the Median Mechanism 42nd ACM Symposium on Theory of Computing Roth, A., Roughgarden, T. ASSOC COMPUTING MACHINERY. 2010: 765–774
  • Beyond Moulin mechanisms 8th Annual Conference on Electronic Commerce (EC 2007) Mehta, A., Roughgarden, T., Sundararajan, M. ACADEMIC PRESS INC ELSEVIER SCIENCE. 2009: 125–55
  • Network Design with Weighted Players 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures Chen, H., Roughgarden, T. SPRINGER. 2009: 302–24
  • Quantifying Inefficiency in Cost-Sharing Mechanisms JOURNAL OF THE ACM Roughgarden, T., Sundararajan, M. 2009; 56 (4)
  • Intrinsic Robustness of the Price of Anarchy 41st Annual ACM Symposium on Theory of Computing Roughgarden, T. ASSOC COMPUTING MACHINERY. 2009: 513–522
  • Simple versus Optimal Mechanisms 10th ACM Conference on Electronic Commerce (EC-2009) Hartline, J. D., Roughgarden, T. ASSOC COMPUTING MACHINERY. 2009: 225–234
  • Universally Utility-Maximizing Privacy Mechanisms 41st Annual ACM Symposium on Theory of Computing Ghosh, A., Roughgarden, T., Sundararajan, M. ASSOC COMPUTING MACHINERY. 2009: 351–359
  • Lightweight Coloring and Desynchronization for Networks IEEE INFOCOM Conference 2009 Motskin, A., Roughgarden, T., Skraba, P., Guibas, L. IEEE. 2009: 2383–2391
  • Revenue Submodularity 1st Conference on Auctions, Market Mechanisms and Their Applications (AMMA) Dughmi, S., Roughgarden, T., Sundararajan, M. SPRINGER. 2009: 89–91
  • Revenue Submodularity 10th ACM Conference on Electronic Commerce (EC-2009) Dughmi, S., Roughgarden, T., Sundararajan, M. ASSOC COMPUTING MACHINERY. 2009: 243–252
  • Worst-Case Efficiency Analysis of Queueing Disciplines 36th International Colloquium on Automata, Languages and Programming Mosk-Aoyama, D., Roughgarden, T. SPRINGER-VERLAG BERLIN. 2009: 546–557
  • Computing correlated equilibria in multi-player games JOURNAL OF THE ACM Papadimitriou, C. H., Roughgarden, T. 2008; 55 (3)
  • Is Shapley cost sharing optimal? 1st International Symposium on Algorithmic Game Theory Dobzinski, S., Mehta, A., Roughgarden, T., Sundaxarajan, M. SPRINGER-VERLAG BERLIN. 2008: 327–336
  • An Algorithmic Game Theory Primer Roughgarden, T. 2008
  • Routing Games Chapter 18 in Algorithmic Game Theory. Roughgarden, T. 2008
  • Introduction to the Inefficiency of Equilibria Chapter 17 in Algorithmic Game Theory. Roughgarden, T., Tardos, E. 2008
  • Metric Clustering via Consistent Labeling 19th ACM-SIAM Symposium on Discrete Algorithms Krauthgamer, R., Roughgarden, T. SIAM. 2008: 809–818
  • Designing Networks with Good Equilibria 19th ACM-SIAM Symposium on Discrete Algorithms Chen, H., Roughgarden, T., Valiant, G. SIAM. 2008: 854–863
  • Optimal Mechanism Design and Money Burning 14th Annual ACM International Symposium on Theory of Computing Hartline, J. D., Roughgarden, T. ASSOC COMPUTING MACHINERY. 2008: 75–84
  • 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

  • Truthful Approximation Schemes for Single-Parameter Agents 49th Annual Symposium on Foundations-of-Computer-Science Dhangwatnotai, P., Dobzinski, S., Dughmi, S., Roughgarden, T. IEEE COMPUTER SOC. 2008: 15–24
  • Algorithmic game theory: Some greatest hits and future directions 5th IFIP International Conference on Theoretical Computer Science held at the 20th World Computer Congress Roughgarden, T. SPRINGER. 2008: 21–42
  • Bertrand competition in networks 1st International Symposium on Algorithmic Game Theory Chawla, S., Roughgarden, T. SPRINGER-VERLAG BERLIN. 2008: 70–82
  • 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 8th Annual Conference on Electronic Commerce (EC 2007) Mehta, A., Roughgarden, T., Sundararajan, M. ASSOC COMPUTING MACHINERY. 2007: 1–10
  • 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
  • Optimal efficiency guarantees for network design mechanisms 12th International Integer Programming and Combinatorial Optimization Conference Roughgarden, T., Sundararajan, M. SPRINGER-VERLAG BERLIN. 2007: 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)
  • Algorithmic Game Theory edited by N., T., E. Cambridge University Press.. 2007
  • Fully distributed algorithms for convex optimization problems 21st International Symposium on Distributed Computing Mosk-Aoyama, D., Roughgarden, T., Shah, D. SPRINGER-VERLAG BERLIN. 2007: 492–493
  • On the severity of Braess's Paradox: Designing networks for selfish users is hard 42nd Annual IEEE Symposium on Foundations of Computer Science Roughgarden, T. ACADEMIC PRESS INC ELSEVIER SCIENCE. 2006: 922–53
  • 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
  • Bottleneck Links, Variable Demand, and the Tragedy of the Commons 17th ACM-SIAM Symposium on Discrete Algorithms Cole, R., Dodis, Y., Roughgarden, T. SIAM. 2006: 668–677
  • 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
  • Optimal cost-sharing mechanisms for Steiner forest problems 2nd International Workshop on Internet and Network Economic Chawla, S., Roughgarden, T., Sundararajan, M. SPRINGER-VERLAG BERLIN. 2006: 112–123
  • Routers with very small buffers IEEE INFOCOM 2006 Conference/25th IEEE International Conference on Computer Communications Enachescu, M., Ganjali, Y., Goel, A., McKeown, N., Roughgarden, T. IEEE. 2006: 1833–1843
  • Single-source stochastic routing 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems/10th International Workshop on Randomization and Computation Chawla, S., Roughgarden, T. SPRINGER-VERLAG BERLIN. 2006: 82–94
  • 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 16th Annual ACM-SIAM Symposium on Discrete Algorithms Roughgarden, T. SIAM. 2005: 1184–1185
  • 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
  • Routers with Very Small Buffers ACM Computer Communication Review. Enachescu, M., Ganjali, Y., Goel, A., McKeown, N., Roughgarden, T. 2005
  • Braess's Paradox, Fibonacci numbers, and exponential inapproximability 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005) Lin, H., Roughgarden, T., Tardos, E., Walkover, A. SPRINGER-VERLAG BERLIN. 2005: 497–512
  • Computing Equilibria in Multi-Player Games 16th Annual ACM-SIAM Symposium on Discrete Algorithms Papadimitriou, C. H., Roughgarden, T. SIAM. 2005: 82–91
  • 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 Anshelevich, E., Dasgupta, A., Kleinberg, J., Tardos, E., Wexler, T., Roughgarden, T. IEEE COMPUTER SOC. 2004: 295–304
  • 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
  • Approximation via cost-sharing: A simple approximation algorithm for the multicommodity rent-or-buy problem 44th Annual IEEE Symposium on Foundations of Computer Science Gupta, A., Kumar, A., Pal, M., Roughgarden, T. IEEE COMPUTER SOC. 2003: 606–615
  • How bad is selfish routing? JOURNAL OF THE ACM Roughgarden, T., Tardos, E. 2002; 49 (2): 236-259
  • A Constant-Factor Approximation Algorithm for the Multicommodity Rent-or-Buy Problem Kumar, A., Gupta, A., Roughgarden, T. 2002
  • A constant-factor approximation algorithm for the multicommodity rent-or-buy problem 43rd Annual IEEE Symposium on Foundations of Computer Science Kumar, A., Gupta, A., Roughgarden, T. IEEE COMPUTER SOC. 2002: 333–342
  • The Price of Anarchy is Independent of the Network Topology Roughgarden, T. 2002
  • How Unfair is Optimal Routing? Roughgarden, T. 2002
  • On a Game in Directed Graphs Hoffman, A., Jenkins, K., 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
  • How bad is selfish routing? 41st Annual Symposium on Foundations of Computer Science (FOCS 00) Roughgarden, T., Tardos, E. IEEE COMPUTER SOC. 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