Tim Roughgarden's Homepage

Tim Roughgarden's Homepage

Some Recent Papers

• J. Morgenstern and T. Roughgarden, The Pseudo-Dimension of Near-Optimal Auctions, arXiv.
• M. Feldman, N. Immorlica, B. Lucier, T. Roughgarden, and V. Syrgkanis, The Price of Anarchy in Large Games, arXiv.
• A. Globerson, T. Roughgarden, D. Sontag, and C. Yildirim, How Hard Is Inference for Structured Prediction? , ICML '15. (arXiv)
• T. Roughgarden and I. Talgam-Cohen, Why Prices Need Algorithms, EC '15.
• P. Gopalan, N. Nisan, and T. Roughgarden, Public Projects, Boolean Functions, and the Borders of Border's Theorem, EC '15.
• Z. Huang, Y. Mansour, and T. Roughgarden, Making the Most of Your Samples, EC '15.
• V. Gkatzelis, K. Kollias, and T. Roughgarden, Optimal Cost-Sharing in General Resource Selection Games, WINE '14 (full version).
• T. Roughgarden, Barriers to Near-Optimal Equilibria, FOCS '14. FOCS talk (Lecture notes)
• T. Roughgarden and O. Schrijvers, Network Cost-Sharing without Anonymity, full version of SAGT '14 paper.
• J. Hsu, A. Roth, T. Roughgarden, and J. Ullman, Privately Solving Linear Programs, ICALP '14.
• P. Duetting, V. Gkatzelis, and T. Roughgarden, The Performance of Deferred-Acceptance Auctions, full version of EC '14 paper.
• P. Duetting, T. Roughgarden, and I. Talgam-Cohen, Modularity and Greed in Double Auctions, full version of EC '14 paper.
• J. Hsu, Z. Huang, A. Roth, T. Roughgarden, and Z. S. Wu, Private Matchings and Allocations, STOC '14.
• R. Cole and T. Roughgarden, The Sample Complexity of Revenue Maximization, STOC '14.
• R. Gupta, T. Roughgarden, and C. Seshadhri, Decompositions of Triangle-Dense Graphs, full version of ITCS '14 paper. (Lecture notes)

Books and Surveys

• T. Roughgarden, Lecture Notes on Algorithmic Game Theory, from the CS364A course (Fall 2013).
• T. Roughgarden, Approximately Optimal Mechanism Design: Motivation, Examples, and Lessons Learned, SIGEcom Exchanges, 2014.
• T. Roughgarden, Algorithmic Game Theory, Communications of the ACM, July 2010. Preprint
• 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.
• The Selfish Routing Book: T. Roughgarden. Selfish Routing and the Price of Anarchy, MIT Press, 2005.

Stanford Teaching (2014-2015)

• Fall 2014: CS264, Beyond Worst-Case Analysis Lecture videos
• Winter 2015: CS369E, Communication Complexity (for Algorithm Designers)
• Spring 2015: CS168, The Modern Algorithmic Toolbox
• Spring 2015: CS 261, Optimization and Algorithmic Paradigms

Open Online Courses

• Algorithms: Design and Analysis (Part I). All of the lecture videos are available freely here, and the slides here. Next session starts June 29, 2015.
  • Topics include: "Big-oh" notation, sorting and searching, divide and conquer, randomized algorithms, data structures (heaps, hash tables, etc.), graph primitives (search, shortest paths, etc.).
• Algorithms: Design and Analysis (Part II). All of the lecture videos are available freely here, and the slides here. Next session starts TBA.
  • Topics include: greedy algorithms, dynamic programming, NP-completeness, analysis of heuristics, local search.
• 20 Video Lectures on the Design and Analysis of Algorithms, covering most of the above two courses, 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.
• 20 Video Lectures on Algorithmic Game Theory (from Stanford's CS364A, Fall 2013). Lecture notes are here
  • Topics include: auction and mechanism design (Vickrey and Myerson auctions, VCG mechanism, etc.); the "price of anarchy" (selfish routing, smoothness, etc.); learning in games (no-regret algorithms, etc.); complexity of Nash equilibria (PLS- and PPAD-completeness). Case studies include: keyword search auctions, combinatorial auctions for spectrum, and communication network management.
• 20 Video Lectures on Advanced Mechanism Design (from Stanford's CS364B, Winter 2014). Lecture notes are here
  • Topics include: combinatorial auctions; Walrasian equilibria; ascending implementations; truthful approximation mechanisms; black-box reductions; simple auctions and equilibrium guarantees for them; Border's theorem and revenue-maximizing auctions beyond Myerson.
• 20 Video Lectures on Beyond Worst-Case Analysis (from Stanford's CS264, Fall 2014). Lecture notes are here
  • Topics include: instance optimality; smoothed analysis; parameterized analysis and condition numbers; models of data (pseudorandomness, locality, diffuse adversaries, etc.); planted and semi-random graph models. Motivating problems drawn from online algorithms, machine learning, computational geometry, graph partitioning, linear programming, hashing, etc.

Read full article from Tim Roughgarden's Homepage