**Instructor:** Tim
Roughgarden (Office hours: Thursdays 1-2 PM in Gates 462)

**Teaching Assistant:**
Peerapong Dhangwatnotai
(Office hours: Tuesdays 3:30-4:30 PM and Wednesdays 2-3 PM
in Gates 460 or Gates 463;
Email: pdh "at" stanford.edu)

**Time/location:**
2:15-3:30 PM on Tuesdays and Thursdays in Gates B12.

**Course description:**
Broad survey of topics at the interface of theoretical computer science
and game theory such as: algorithmic mechanism design;
auctions (efficient, revenue-maximizing, sponsored search, etc.);
congestion and potential games; cost sharing;
existence, computation, and learning of equilibria; game theory in the
Internet; network games; price of anarchy; selfish routing.

**Prerequisites**: basic algorithms and complexity (154N and 161, or equivalent).

**Course requirements:** 4 problem sets and a take-home final.
Students taking the course for a letter grade should
complete all 5 problems on each.
Students taking the course for pass/fail should
complete the first 3 problems on each.
There will also be occasional extra credit problems and opportunities.
**No late assignments accepted.**

- Problem Set #1 (Out Thu 1/6, due in class Thu 1/20.)
- Problem Set #2 (Out Thu 1/20, due in class Thu 2/3.)
- Problem Set #3 (Out Thu 2/3, due in class Thu 2/17.)
- Problem Set #4 (Out Thu 2/17, due in class Thu 3/3.)
- Take-Home Final (Out Thu 3/3, due Thu 3/17, 3:30 PM.)

**Primary references:**

- Nisan/Roughgarden/Tardos/Vazirani (eds),
*Algorithmic Game Theory*, Cambridge University, 2007.- Also available free on the Web here (username=agt1user, password=camb2agt).

- To get a sense for the course in a nutshell:
- T. Roughgarden, Algorithmic Game Theory (CACM July 2010);
- T. Roughgarden, An Algorithmic Game Theory Primer (an earlier and longer version).

- Another excellent textbook that covers several of the
course's topics is Shoham and Leyton-Browm,
*Multiagent Systems*, Cambridge, 2008.

- Schedule from the Fall 2008
version of the course; there will be a few changes this year but lots
of similarities.
**Tue 1/4:**Introduction: the Vickrey auction, Braess's Paradox, and Nash equilibria. Readings:- The Vickrey auction: AGT book, Section 9.3.1; and/or Section 1 or these old CS364B notes.
- Braess's Paradox: Chapter 1 of T. Roughgarden,
*Selfish Routing and the Price of Anarchy*(MIT Press, 2005), available here. - Basic games and equilibrium notions: AGT book, Sections 1.1.1--1.3.4.

**Thu 1/6:**Auction and mechanism design basics. Sponsored search auctions. Statement of Myerson's Lemma. Readings:- AGT book, Sections 9.3.1, 9.3.2, 9.3.5, 9.5.4.
- Optional sponsored search readings: AGT book, Sections 28.1-28.3.1, and Cornell lecture notes by D. Easley and J. Kleinberg. See also CS364B course for tons of subtopics and references on sponsored search auctions (circa late 2007).
- Optional: How To Think About Algorithmic Mechanism Design, a 90-minute tutorial by your instructor at FOCS '10. Video

**Tue 1/11:**Characterization of single-parameter truthful mechanisms (Myerson's Lemma). Introduction to revenue-maxmizing auctions. Revelation Principle. Readings:- AGT book, Sections 9.4 and 9.5.4--9.5.6. Optionally, see also Section 4 in this FOCS '01 paper by Archer and Tardos.
- AGT book, Section 13.1.

**Thu 1/13:**Myerson's theorem on Bayesian-optimal auctions. Introduction to prior-free revenue-maximizing auctions. Readings:- AGT book, Sections 13.1-13.2.
- For a more recent and expansive treatment of this material, see Jason Hartline's lecture notes.
- Optional: Myerson's original paper: Optimal Auction Design, Mathematics of Operations Research, 1981.
- Optional: Worst-case analysis for revenue maximization originates in this SODA '01 paper by Goldberg/Hartline/Wright.

**Tue 1/18:**Prior-free revenue-maximizing auctions and the 4-competitive RSPE auction. Readings:- AGT book, Section 13.4; or Section 3 of these notes from my CS369N class.
- Optional: The RSPE auction and its analysis are originally from this STOC '02 paper by Fiat, Goldberg, Hartline, and Karlin.
- Optional: Hartline's lecture notes from an old CS364B course that we co-taught constitute an expanded version of Chapter 13 of the AGT book.

**Tue 1/20:**Bayesian foundations for prior-free benchmarks. Simple and near-optimal multi-parameter pricings.- For the Bayesian foundations of prior-free benchmarks, see these notes from my CS369N class.
- Optional: the above ideas originate in a STOC '08 paper by Hartline and Roughgarden.
- For the multi-parameter pricing problem, see the EC '07 paper by S. Chawla, J. Hartline, and R. Kleinberg; the proof given in class is most closely related to pages 80-82 of these notes by Hartline.

**Tue 1/25:**Multi-parameter mechanism design and the VCG mechanism. Introduction to Bayes-Nash implementations. Readings:- AGT book, Section 9.3 and/or Section 2 of these old CS364B notes.

- Sections 1-4 of D. Lehmann, L. O'Callaghan, and Y. Shoham, Truth Revelation in Approximately Efficient Combinatorial Auctions, JACM 2002;
- David Parkes's resources on the topic (especially Sections 2.1-2.4 of his thesis); and
- N. Nisan and A. Ronen, Algorithmic Mechanism Design, which first appeared in STOC 1999.

- Sections 2.3-2.5 of notes by Hartline.

- AGT book, Chapter 11.
- Cramton/Shoham/Steinberg (eds.), Combinatorial Auctions, MIT Press, 2006.
- These old CS364B notes.

**Thu 1/27:**Bayes-Nash implementations. A black-box reduction from computationally efficient mechanism design to computationally efficient algorithm design. Related papers:- Hartline/Lucier, Bayesian Algorithmic Mechanism Design, STOC '10.
- Hartline/Kleinberg/Malekian, Bayesian Incentive Compatibility via Matchings, SODA '11.
- Bei/Huang, Bayesian Incentive Compatibility via Fractional Assignments, SODA '11.

**Tue 2/1:**Selfish routing and the price of anarchy: examples, preliminaries, and tight bounds for all classes of cost functions. Readings:- AGT book, Sections 17.1-17.2.1 and 18.1-18.3.1, 18.4.1.
- For much more on this topic, see the book on Selfish Routing and the Price of Anarchy, MIT Press, 2005.
- Optional: the original source is T. Roughgarden, The Price of Anarchy Is Independent of the Network Topology, JCSS '03.

**Thu 2/3:**Finish selfish routing: a bicriteria bound and bounds for atomic selfish routing networks. Readings:- AGT book, Sections 18.3.2, 18.4.2, and 18.5.2.

- Roughgarden/Tardos, How Bad Is Selfish Routing?, JACM 2002.
- Awerbuch/Azar/Epstein, The price of routing unsplittable flow, STOC 2005.
- Christodoulou/Koutsoupias, The price of anarchy of finite congestion games, STOC 2005.

**Tue 2/8:**Potential Functions. Network cost-sharing games and the price of stability. Best-response dynamnics. Readings:- AGT book, Sections 17.2.2, 19.1, and 19.3.

- Anshelevich/Dasgupta/Kleinberg/Tardos/Wexler/Roughgarden, The Price of Stability for Network Design with Fair Cost Allocation, FOCS '04.
- Rosenthal, "A Class of Games Possessing Pure-Strategy Nash Equilibria", International Journal of Game Theory 1973.
- Monderer/Shapley, "Potential Games", Games and Economic Behavior 1996.

- T. Roughgarden, Potential Functions and the Inefficiency of Equilibria, ICM '06.

**Thu 2/10:**Smooth Games. Guarantees for short best-response sequences. Reading:- T. Roughgarden, Intrinsic Robustness of the Price of Anarchy, STOC '09.

- Goemans/Mirrokni/Vetta, Sink equilibria and convergence, FOCS '05.

**Tue 2/15:**Introduction to Regret Minimization. No-regret sequences in smooth games. Vetta's location game. Reading:- AGT book, Sections 4.1, 4.2, and 19.4.
- T. Roughgarden, Intrinsic Robustness of the Price of Anarchy, STOC '09.

- Blum/Hajiaghayi/Ligett/Roth, Regret Minimization and the Price of Total Anarchy, STOC '08.

- Vetta, Nash equilibria in competitive societies with applications to facility location, traffic routing and auctions, FOCS '02.

**Thu 2/17:**Existence of no-regret algorithms: the multiplicative weights algorithm. Fast convergence of epsilon-best-response dynamics to Nash equilibria in symmetric congestion games. Reading:- AGT book, Section 4.3.
- Week 1 lecture notes from a course taught by Bobby Kleinberg.
- Chien/Sinclair, Convergence to approximate Nash equilibria in congestion games, SODA '07.

**Tue 2/22:**Convergence of no-regret dynamics in atomic splittable selfish routing and zero-sum games. References:- AGT book, Section 4.4.
- Fiat/Mansour/Nadav, On the Convergence of Regret Minimization Dynamics in Concave Games, STOC '09.

**Thu 2/24:**PLS-completeness and negative convergence results. Primary reference:- Section 3 of Roughgarden,
*Computing Equilibria: A Computational Complexity Perspective*.

- Fabrikant/Papadimitriou/Talwar, The Complexity of Pure Nash Equilibria, STOC '04.

- Voecking, Congestion Games: Optimization in Competition (Survey Paper), ACiD '06.
- Yannakakis, Chapter 2 in
*Local Search in Combinatorial Optimization*(Wiley, 1997; and Princeton, 2003).

- Section 3 of Roughgarden,
**Tue 3/1:**PPAD-completeness of computing mixed-strategy Nash equilibria of bimatrix games. Primary references:- Section 4 of Roughgarden,
*Computing Equilibria: A Computational Complexity Perspective*. - AGT book, Sections 2.1-2.6.
- Johnson, Finding Needles in Haystacks, ACM Transacations on Algorithms, 2007.
- Yannakakis, Equilibria, Fixed Points, and Complexity Classes, survey in STACS '08.

- N. Megiddo and C. Papadimitriou, A note on total functions, existence theorems and complexity, Theoretical Computer Science, 81:317--324, 1991.
- C. Papadimitriou, The complexity of the parity argument and other inefficient proofs of existence, JCSS 1994.
- Daskalakis/Goldberg/Papadimitriou, The Complexity of Computing a Nash Equilibrium, STOC 2006.
- Chen/Deng/Teng, Settling the Complexity of 2-Player Nash-Equilibrium, FOCS 2006.

- Section 4 of Roughgarden,
**Thu 3/3:**Proof of Nash's Theorem. Approximate Nash equilibria. For references on Nash's Theorem, see the following.- Nash's Theorem is originally from J. F. Nash, Jr., Equilibrium Points in N-Person Games, Proceedings of the National Academy of Sciences (USA), 36(1):48--49, 1950.
- A year later Nash showed how to reduce his theorem to Brouwer's fixed-point theorem: J. F. Nash, Jr., Non-cooperative games, Annals of Mathematics, 54(2):286--296, 1951.
- The reduction of Nash's theorem to Brouwer's theorem that we covered in class is from J. Geanakoplos, Nash and Walras Equilibrium Via Brouwer, Economic Theory 21(2-3):585--603, 2003.
- The von Neumann correspondence to Econometrica that I discussed is here.

- Hazan/Krauthgamer, How hard is it to approximate the best Nash equilibrium?, SODA '09.

- Minder/Vilenchik, Small clique detection and approximate Nash equilibria, RANDOM '09.

**Tue 3/8:**Arrow's Impossibility Theorem: A Fourier-analytic proof.- AGT book, Section 9.2.
- Arrow, A Difficulty in the Concept of Social Welfare, Journal of Political Economy, 1950.
- Section 4 of O'Donnell, Some Topics in Analysis of Boolean Functions, STOC 08 tutorial.

**Thu 3/10:**The Gibbard-Satterthwaite theorem. Single-peaked preferences. The top trading cycle algorithm. The Gale-Shapley proposal algorithm and the structure of stable matchings.- AGT book, Chapter 10.