Tim Roughgarden Associate professor in the Computer Science and (by courtesy) Management Science and Engineering Departments at Stanford University. N.B.: I'm on sabbatical in the New York area for the 2012-2013 school year. 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

• Algorithms: Design and Analysis (Part I). Not currently running, but all of the lecture videos are available freely here, and the slides here. Next offered later in 2013.
• Algorithms: Design and Analysis (Part II). Not currently running, but all of the lecture videos are available freely here, and the slides here. Next offered later in 2013.
• 20 Video Lectures on the Design and Analysis of Algorithms, for those of you who prefer blackboard lectures (from Stanford's CS161, Winter 2011).
  • Warning/apology: the audio is suboptimal on a few segements of the blackboard lectures.

Recent Goings-On

• STOC 2013 will be in Palo Alto, June 1-4.
• FOCS 2012 CFP, accepted papers, etc. The Program Committee's act of rebellion.
• Summer school in algorithmic game theory, co-organized with Ariel Procaccia, August 6-10, 2012, at CMU. Talk summaries: 1 2 3 4 5
• Workshop on Beyond Worst-Case Analysis (September 19-21, 2011, at Stanford).

Blog

• Turing's Invisible Hand, a blog on algorithmic game theory and economics that I sporadically contribute to.

Some Recent Papers

• K. Bhawalkar and T. Roughgarden, Simultaneous Single-Item Auctions, WINE '12.
• 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 and E. Tardos, Do Externalities Degrade GSP’s Efficiency?, Ad Auctions '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.

Some Sorta Recent Talks

• Quantifying the Inefficiency of Game-Theoretic Equilibria (video), College de France. Survey for general scientific audience. (En Francais)
• Intractability in Algorithmic Game Theory (video), Institute for Advanced Studies. Survey for theoretical computer scientists.
• Simple and Prior-Independent Auctions (video), Princeton theory seminar. About my EC '09, '11, and '12 papers on the topic.
• Simple Auctions with Near-Optimal Equilibria (video), Jerusalem Algorithmic Game Theory Workshop. About my EC '09 and SODA '11 papers on the topic.
• How To Think About Algorithmic Mechanism Design (slides), tutorial at FOCS '10. Video. Survey for theoretical computer scientists.
• Intrinsic Robustness of the Price of Anarchy (video), talk at MSR New England. (Seems to work only with IE, unfortunately.) About my STOC '09 paper.
• Potentials and Approximation (slides), Shapley Lecture, Third World Congress of the Game Theory Society. Survey for game theorists.

Some Older Papers

• S. Dughmi, T. Roughgarden, and Q. Yan, From Convex Optimization to Randomized Mechanisms: Toward Optimal Combinatorial Auctions, STOC '11.
• 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. See also this CACM article (preprint) and video.
• 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 (2012-2013)

• None (on sabbatical).

Teaching (Archives)

• Fall 2011: CS369, Beyond Worst-Case Analysis
• 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