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.

PhD students, postdocs, etc.

Online Courses

• Design and Analysis of Algorithms I. Starts March 12th, 2012. Free to everyone. Corresponds to the first half (5 weeks) of my Stanford course (CS161).
• If you prefer blackboard lectures, here are my 20 Video Lectures on the Design and Analysis of Algorithms from CS161 (Winter 2011).
  • Warning/apology: the audio is suboptimal on a few segements of the blackboard lectures.

Goings-On

• FOCS 2012 Call for Papers. We are no longer accepting submissions.
• FOCS 2012 Call for Workshop Proposals. Submission deadline is June 20, 2012.
  • Details about posters TBA in the late spring/summer.
• Summer school in algorithmic game theory, co-organized with Ariel Procaccia, August 6-10, 2012, at CMU.
• Workshop on Beyond Worst-Case Analysis (September 19-21, 2011, at Stanford).

Some Recent Papers

• K. Bhawalkar, J. Kleinberg, K. Lewi, T. Roughgarden, and A. Sharma, Preventing Unraveling in Social Networks: The Anchored k-Core Problem, ICALP '12.
• T. Roughgarden, The Price of Anarchy in Games of Incomplete Information, EC '12.
• T. Roughgarden, I. Talgam-Cohen, and Q. Yan, Supply-Limiting Mechanisms, EC '12.
• I. Abraham, M. Babaioff, S. Dughmi, and T. Roughgarden, Combinatorial Auctions with Restricted Complements, EC '12.
• S. Leonardi and T. Roughgarden, Prior-Free Auctions with Ordered Bidders, STOC '12.
• 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 (full version).
• T. Roughgarden and F. Schoppmann, Local Smoothness and the Price of Anarchy in Atomic Splittable Congestion Games, SODA '11 (full version).

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

• S. Dughmi and T. Roughgarden, Black-Box Randomized Reductions in Algorithmic Mechanism Design, FOCS '10 (full version).
• P. Dhangwotnotai, T. Roughgarden, and Q. Yan, Revenue Maximization with a Single Sample, EC '10 (full version).
• 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.