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

**Teaching Assistant:**
Peerapong Dhangwatnotai
(Office hours: Mon 11 AM-Noon and Wed 2-3 PM in Gates 460;
Email: pdh "at" stanford.edu)

**Time/location:**
11 AM-12:15 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 9/25, due in class Thu 10/9.)
- Problem Set #2 (Out Thu 10/9, due in class Thu 10/23.)
- Problem Set #3 (Out Thu 10/23, due in class Thu 11/6.)
- Problem Set #4 (Out Thu 11/6, due in class Thu 11/20.)
- Take-Home Final (Out Thu 11/20, due Thu 12/11, 6: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).

- An even newer, excellent textbook that covers several of the
course's topics is Shoham and Leyton-Browm,
*Multiagent Systems*, Cambridge, 2008. - To get a sense for the course in a nutshell: T. Roughgarden, An Algorithmic Game Theory Primer.

**Tue 9/23:**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 9/25:**Auction and mechanism design basics. Sponsored search. 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 last year's 364B course for tons of subtopics and references on sponsored search auctions.

**Tue 9/30:**Characterization of single-parameter truthful mechanisms (Myerson's Lemma). Application to sponsored search. Introduction to revenue-maxmizing auctions. Readings:- AGT book, Sections 9.5.4--9.5.6. Optionally, see also Section 4 in this FOCS 2001 paper by Archer and Tardos.
- AGT book, Section 13.1.

**Thu 10/2:**Myerson's theorem on Bayesian-optimal auctions. Intro to prior-free revenue-maximizing auctions. Readings:- AGT book, Section 13.2.
- 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 10/7:**Prior-free revenue-maximizing auctions and the 4-competitive RSPE auction. Readings:- AGT book, Section 13.4.
- Slides (through slide 13) on the Hartline/Roughgarden framework for prior-free benchmarks. (Optional: full paper.)
- 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.
- Optional: The RSPE auction and its analysis are originally from this STOC '02 paper by Fiat, Goldberg, Hartline, and Karlin.

**Thu 10/9:**Multi-parameter mechanism design and the VCG mechanism. 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.

**Tue 10/14:**Combinatorial auctions with single-minded bidders. Readings:- AGT book, Sections 11.1 and 11.2.
- Section 3 of these old CS364B notes.

- Cramton/Shoham/Steinberg (eds.), Combinatorial Auctions, MIT Press, 2006.

**Thu 10/16:**Communication complexity in combinatorial auctions. Recent trends and open questions in algorithmic mechanism design. Readings:- AGT book, Section 11.6.
- Sections 2 and 5 of Roughgarden, An Algorithmic Game Theory Primer.
- Section 4 of these old CS364B notes (revised as of 10/18/08). Optional original refence: N. Nisan, The Communication Complexity of Approximate Set Packing and Covering , ICALP 2002.

**Tue 10/21:**Selfish routing and the price of anarchy: examples and preliminaries. Readings:- AGT book, Sections 17.1-17.2.1 and 18.1-18.3.1.
- For much more on this topic, see the book on Selfish Routing and the Price of Anarchy, MIT Press, 2005.

**Thu 10/23:**Selfish routing and the price of anarchy: tight bounds for all classes of cost functions. Readings:- AGT book, Section 18.4.1.
- Optional: the original source is T. Roughgarden, The Price of Anarchy Is Independent of the Network Topology, JCSS '03; the proof given in class is due to E. Tardos; see these lecture notes from Cornell CS684.

**Tue 10/28:**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.

**Thu 10/30:**Congestion and Shapley network cost-sharing games. 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.

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

**Tue 11/4:**Vetta's location game. Readings:- AGT book, Section 19.4.

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

**Thu 11/6:**Out-of-equilibrium inefficiency bounds. Introduction to regret-minimization. Readings:- AGT book, Section 19.4.5; Sections 4.1 and 4.2.
- Goemans/Mirrokni/Vetta, Sink equilibria and convergence, FOCS '05.
- Blum/Hajiaghayi/Ligett/Roth, Regret Minimization and the Price of Total Anarchy, STOC '08.

**Tue 11/11:**Existence of no-regret algorithms, with application to the minimax theorem in two-player zero-sum games. Reading:- AGT book, Sections 4.3-4.4.2.
- Week 1 and Week 2 lecture notes from a course taught by Bobby Kleinberg.
- The von Neumann correspondence to Econometrica that I discussed is here.

**Thu 11/13:**Convergence of best-response dynamics to Nash equilibria in congestion games: fast convergence to approximate equilbria. Reference:- Chien/Sinclair, Convergence to approximate Nash equilibria in congestion games, SODA 2007.

**Tue 11/18:**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,
**Thu 11/20:**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,
**Tue 11/25:**No class (Thanksgiving break).**Thu 11/27:**No class (Thanksgiving break).**Tue 12/2:**Proof of Nash's Theorem. Introduction to 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.

**Thu 12/4:**Hardness of approximately optimizing over approximate Nash equilibria of a bimatrix game. Reference:- Hazan/Krauthgamer, How hard is it to approximate the best Nash equilibrium?, SODA '09.