CS364A: Algorithmic Game Theory

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.
  For more surveys on the VCG mechanism and combinatorial auctions that are geared toward computer scientists, see:
  • 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.
  There's also an excellent recent book devoted to combinatorial auctions:
  • 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.
  Optional original references:
  • 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.
  Optional original reference:
  • Anshelevich/Dasgupta/Kleinberg/Tardos/Wexler/Roughgarden, The Price of Stability for Network Design with Fair Cost Allocation, FOCS '04.
  For much more on potentials:
  • T. Roughgarden, Potential Functions and the Inefficiency of Equilibria, ICM '06.

• Tue 11/4: Vetta's location game. Readings:
  • AGT book, Section 19.4.
  Optional original reference:
  • 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.
  Original reference:
  • Fabrikant/Papadimitriou/Talwar, The Complexity of Pure Nash Equilibria, STOC '04.
  Further good surveys:
  • Voecking, Congestion Games: Optimization in Competition (Survey Paper), ACiD '06.
  • Yannakakis, Chapter 2 in Local Search in Combinatorial Optimization (Wiley, 1997; and Princeton, 2003).

• 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.
  Original references:
  • 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.

• 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.