CS364A: Algorithmic Game Theory

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.
  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.
  Our treatment of Bayes-Nash implementations and the first-price single-item auction are standard; see e.g.:
  • Sections 2.3-2.5 of notes by Hartline.
  Some supplementary material on combinatorial auctions:
  • 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.
  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.

• 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.
  Optional original references:
  • 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.
  For much more on potentials:
  • 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.
  Optional important precursor:
  • 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.
  Optional important precursor:
  • Blum/Hajiaghayi/Ligett/Roth, Regret Minimization and the Price of Total Anarchy, STOC '08.
  Optional original reference:
  • 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.
  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).

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

• 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.
  The reduction from finding planted cliques in random graphs to computing approximately max-payoff approximate Nash equilibria is
  • Hazan/Krauthgamer, How hard is it to approximate the best Nash equilibrium?, SODA '09.
  with an optimization in
  • 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.