Tim Roughgarden's Homepage

Tim Roughgarden

Associate professor in the Computer Science and (by courtesy) Management Science and Engineering Departments at Stanford University.

Research interests: Design, analysis, and applications of algorithms.
Game theory and microeconomics, especially as applied to networks and auctions.

Contact info: tim@cs.stanford.edu. 650-724-9147.
462 Gates Building, 353 Serra Mall, Stanford, CA 94305.

Admin: Lynda Harris. lrharris@stanford.edu. 650-723-4377. Fax: 650-725-4671.
480 Gates Building, 353 Serra Mall, Stanford, CA 94305.

List of papers (all online)

PhD students, postdocs, etc.

20 Video Lectures on the Design and Analysis of Algorithms
The course's old home page, no longer maintained.

Goings-On

Workshop on Beyond Worst-Case Analysis (September 19-21, 2011, at Stanford).
- Part of Stanford's special year (2011-12) on theoretical computer science.
EC 2011 (June 5-9, 2011): Conference Program

Some Recent Papers

A. Badanidiyuru, S. Dobzinski, H. Fu, R. D. Kleinberg, N. Nisan and T. Roughgarden, Sketching Valuation Functions, SODA '12.
U. Nadav, R. Johari, and T. Roughgarden, Uncoupled Potentials for Proportional Allocation Markets, CDC '11.
S. Dughmi, T. Roughgarden, and Q. Yan, From Convex Optimization to Randomized Mechanisms: Toward Optimal Combinatorial Auctions, STOC '11.
K. Kollias and T. Roughgarden, Restoring Pure Equilibria to Weighted Congestion Games, ICALP '11.
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.
T. Roughgarden and F. Schoppmann, Local Smoothness and the Price of Anarchy in Atomic Splittable Congestion Games, SODA '11.
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.
S. Dughmi and T. Roughgarden, Black-Box Randomized Reductions in Algorithmic Mechanism Design, FOCS '10.
T. Roughgarden, Algorithmic Game Theory, Communications of the ACM, July 2010. Preprint
K. Bhawalkar, M. Gairing, and T. Roughgarden, Weighted Congestion Games: Price of Anarchy, Universal Worst-Case Examples, and Tightness, ESA '10.
P. Dhangwotnotai, T. Roughgarden, and Q. Yan, Revenue Maximization with a Single Sample, EC '10.
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.

Some Sorta Recent Talks

Approximation in Algorithmic Game Theory (slides), Princeton Workshop on Approximation Algorithms. Scribe notes courtesy of Qiqi Yan.
Simple Auctions with Near-Optimal Equilibria (video), Jerusalem Algorithmic Game Theory Workshop.
How To Think About Algorithmic Mechanism Design (slides), tutorial at FOCS '10. Video
Intrinsic Robustness of the Price of Anarchy (slides), plenary lecture, Bellairs Workshop on Algorithmic Game Theory.
- A video from a similar talk at MSR New England. (Seems to work only with IE, unfortunately.)
Potentials and Approximation (slides), Shapley Lecture, Third World Congress of the Game Theory Society.

Some Older Papers

T. Roughgarden, Intrinsic Robustness of the Price of Anarchy, STOC '09.
A. Ghosh, T. Roughgarden, and M. Sundararajan, Universally Utility-Maximizing Privacy Mechanisms, full version of STOC '09 paper.
A. Mehta, T. Roughgarden, and M. Sundararajan, Beyond Moulin Mechanisms, Games and Economic Behavior, 2009.
T. Roughgarden and M. Sundararajan, Quantifying Inefficiency in Cost-Sharing Mechanisms, JACM '09.
C. H. Papadimitriou and T. Roughgarden, Computing Correlated Equilibria in Multi-Player Games, JACM '08. Addendum
A. Gupta, A. Kumar, M. Pal, and T. Roughgarden, Approximation Via Cost Sharing, JACM '07.
T. Roughgarden, The Price of Anarchy is Independent of the Network Topology, JCSS '03.
T. Roughgarden, Designing Networks for Selfish Users is Hard, JCSS '06.
T. Roughgarden and E. Tardos, How Bad is Selfish Routing?, JACM '02.

Books and Surveys

T. Roughgarden, Algorithmic Game Theory, Communications of the ACM, July 2010. Preprint
- This is a revised and abridged version of An Algorithmic Game Theory Primer, invited survey for TCS '08.
T. Roughgarden, Computing Equilibria: A Computational Complexity Perspective, invited survey for Economic Theory, 2010.
The AGT Book: Algorithmic Game Theory, co-edited with Noam Nisan, Eva Tardos, and Vijay Vazirani.
- Read the entire book online by clicking here (username=agt1user, password=camb2agt).
- Here's errata from the first two printings.
T. Roughgarden, Routing Games, Chapter 18 in Algorithmic Game Theory, 2007
T. Roughgarden and E. Tardos, Introduction to the Inefficiency of Equilibria, Chapter 17 in Algorithmic Game Theory, 2007.
T. Roughgarden, Selfish Routing and the Price of Anarchy (Survey), OPTIMA #74, 2007
T. Roughgarden, Potential Functions and the Inefficiency of Equilibria (Survey), International Congress of Mathematicians, 2006.
T. Roughgarden. Selfish Routing and the Price of Anarchy, MIT Press, 2005.

Teaching (2011-2012)

Fall '11: CS161, Design and Analysis of Algorithms
Fall '11: CS369, Beyond Worst-Case Analysis

Teaching (Archives)

Video (open access) of all my lectures for the Design and Analysis of Algorithms (CS161, Winter 2011).
Winter 2011: CS364A, Introduction to Algorithmic Game Theory
Fall 2009: CS369N, Beyond Worst-Case Analysis (includes lecture notes)
Fall 2008: CS364A, Introduction to Algorithmic Game Theory
Winter 2008: CS369, Advanced Graph Algorithms
Fall 2007: CS364B, Foundations of Sponsored Search
Winter 2007: CS359, Hardness of Approximation
Fall 2006: CS364A, Introduction to Algorithmic Game Theory
Winter 2006: CS369, Metric Embeddings and Algorithmic Applications
Fall 2005: CS364B, Topics in Algorithmic Game Theory (lecture notes finalized on 10/18/08)
Fall 2004: CS364A, Algorithmic Game Theory

Hobbies: Underground music/records, sports, film, etc. Ask me in person some time.