CS364A: Algorithmic Game Theory (Fall 2013)

Time/location: 2:15-3:30 PM on Mondays and Wednesdays in Littlefield 103.

Course description: Broad survey of topics at the interface of theoretical computer science and economics. Introduction to auction and mechanism design, with an emphasis on computational efficiency and robustness. Introduction to the "price of anarchy", with applications to networks. Algorithms and complexity theory for learning and computing Nash and market equilibria. Case studies in Web search auctions, wireless spectrum auctions, matching markets, network routing, and security applications.

Prerequisites: basic algorithms and complexity (154N and 161, or equivalent). No prior knowledge of economics or game theory is required.

• A LaTeX template that you can use to type up solutions. Here and here are good introductions to LaTeX.

• Lecture 1 (Introduction):   Video    Notes
• Lecture 2 (Mechanism Design Basics):   Video    Notes
• Lecture 3 (Myerson's Lemma):   Video    Notes
• Lecture 4 (Algorithmic Mechanism Design):   Video    Notes
• Lecture 5 (Revenue-Maximizing Auctions):   Video    Notes
• Lecture 6 (Simple Near-Optimal Auctions):   Video    Notes
• Lecture 7 (VCG Mechanism):   Video    Notes
• Lecture 8 (Spectrum Auctions):   Video    Notes
• Lecture 9 (Beyond Quasi-Linearity):   Video    Notes
• Lecture 10 (Kidney Exchange, Stable Matching):   Video    Notes
• Lecture 11 (Selfish Routing and the POA):   Video    Notes
• Lecture 12 (Network Over-Provisioning):   Video    Notes
• Lecture 13 (Hierarchy of Equilibrium Concepts):   Video    Notes
• Lecture 14 (Smooth Games):   Video    Notes
• Lecture 15 (Best-Case and Strong Nash Equilibria):   Video    Notes
• Lecture 16 (Best-Response Dynamics):   Video    Notes
• Lecture 17 (No-Regret Dynamics):   Video    Notes
• Lecture 18 (Swap Regret; Minimax):   Video    Notes
• Lecture 19 (Pure NE and PLS-Completeness):   Video    Notes
• Lecture 20 (Mixed NE and PPAD-Completeness):   Video    Notes
• The CS364A Top 10 List

Exercise and problem sets:

• Exercise Set #1 (Out Wed 9/25, due by class Wed 10/2.)
• Exercise Set #2 (Out Wed 10/2, due by class Wed 10/9.)
• Exercise Set #3 (Out Wed 10/9, due by class Wed 10/16.)
• Exercise Set #4 (Out Wed 10/16, due by class Wed 10/23.)
• Exercise Set #5 (Out Wed 10/23, due by class Wed 10/30.)
• Exercise Set #6 (Out Wed 10/30, due by class Wed 11/6.)
• Exercise Set #7 (Out Wed 11/6, due by class Wed 11/13.)
• Exercise Set #8 (Out Wed 11/13, due by class Wed 11/20.)
• Exercise Set #9 (Out Fri 11/22, due by noon Fri 12/6.)

• Problem Set #1 (Out Wed 9/25, due by noon Fri 10/11.)
• Problem Set #2 (Out Wed 10/9, due by noon Fri 10/25.)
• Problem Set #3 (Out Wed 10/23, due by noon Fri 11/8.)
• Problem Set #4 (Out Wed 11/6, due by noon Fri 11/22.)
• Take-Home Final (Out Wed 11/20, due by noon Fri 12/13.)

• Nisan/Roughgarden/Tardos/Vazirani (eds), Algorithmic Game Theory, Cambridge University, 2007.
  • Also available free on the Web, see here.
  • T. Roughgarden, Algorithmic Game Theory (CACM July 2010);
  • T. Roughgarden, An Algorithmic Game Theory Primer (an earlier and longer version).
  • Lecture 1 (Mon 9/23): Introduction. The 2012 Olympic badminton scandal. Selfish routing and Braess's Paradox. Can strategic players learn a Nash equilibrium?
    Readings:
    • J. Hartline and R. Kleinberg, Badminton and the Science of Rule Making, Huffington Post, 2012.
    • Video of the first controversial badminton match.
    • Braess's Paradox: Chapter 1 of T. Roughgarden, Selfish Routing and the Price of Anarchy (MIT Press, 2005), available here via the "Sample Chapter" link.
    • Physical demonstrations of Braess's Paradox, by alumni of CS364A: #1#2#3
    • Basic games and equilibrium notions: AGT book, Sections 1.1.1--1.3.4.
    • The Vickrey auction: AGT book, Section 9.3.1, 9.3.2, and 9.3.5; and/or Section 1 or these old CS364B notes.
    • Pages 1-8 of Hartline's book.
    • Optional sponsored search readings: AGT book, Sections 28.1-28.3.1. See also this CS364B course for tons of subtopics and references on sponsored search auctions (circa late 2007).
    • AGT book, Sections 9.4.1--9.4.2 and 9.5.4--9.5.6. Optionally, see also Section 4 in this FOCS '01 paper by Archer and Tardos.
    • Sections 2.6 and 3.1 of Hartline's book.
    • See Lecture 2 for sponsored search readings.
    • AGT book, Sections 9.4.3 (Revelation Principle) and 12.1 (introduction to algorithmic mechanism design).
    • Sections 2.10 and 3.2 of Hartline's book.
    • Knapsack review videos: Dynamic programming solutions part 1part 2 part 3; greedy 0.5-approximation algorithm and analysis part 1part 2part 3; (1-epsilon)-approximation algorithm part 1part 2
    • Optional: How To Think About Algorithmic Mechanism Design, a 90-minute tutorial by your instructor at FOCS '10. Video
    • The latest results on black-box reductions for single-parameter problems are due to Chawla/Immorlica/Lucier, STOC '12.
    • AGT book, Sections 13.1-13.2.
    • Sections 3.3.1-3.3.3 of Hartline's book.
    • Sections 4.2, 5.1, 5.2.1 of Hartline's book.
    • Ostrovsky/Schwarz, Reserve Prices in Internet Advertising Auctions: A Field Experiment, 2009.
    • AGT book, Sections 9.3.3-9.3.4 and 11.1.
    • See also these old CS364B notes on combinatorial auctions and the VCG mechanism.
    • Cramton/Schwartz, Collusive Bidding in the FCC Spectrum Auctions, 1999.
    • Cramton/Shoham/Steinberg (eds.), Combinatorial Auctions, MIT Press, 2006.
      • Chapter 4 (Cramton) covers simultaneous ascending auctions.
      • Chapter 5 (Ausubel/Cramton/Milgrom) discusses how to add a final "proxy" round with package bidding.
      • Dobzinski/Lavi/Nisan, Multi-unit Auctions with Budget Limits, FOCS '08.
      • AGT book, Section 10.3.
      • Roth/Sönmez/Ünver, Kidney Exchange, QJE '04.
      • Roth/Sönmez/Ünver, Pairwise Kidney Exchange, JET '05.
      • Ashlagi/Fischer/Kash/Procaccia, Mix and Match: A Strategyproof Mechanism for Multi-Hospital Kidney Exchange, EC '10.
      • AGT book, Section 10.4.
      • 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, or the "reader's digest" version here.
      • AGT book, Sections 18.3.2, 18.4.2, and 18.5.2.
      • AGT book, Sections 1.3.4, 1.3.6, 19.3.1, 19.3.2.
      • T. Roughgarden, Intrinsic Robustness of the Price of Anarchy, STOC '09, Sections 1.1 and 3.1.
      • AGT book, Section 19.4.
      • T. Roughgarden, Intrinsic Robustness of the Price of Anarchy, STOC '09, Sections 2.1, 2.2, 2.3, 3.1, and 4.1.
      • AGT book, Sections 17.2.2 and 19.3.
      • A. Epstein, M. Feldman, and Y. Mansour, Strong Equilibrium in Cost Sharing Connection Games, EC '07.
      • AGT book, Section 19.3.
      • Chien/Sinclair, Convergence to approximate Nash equilibria in congestion games, SODA '07.
      • T. Roughgarden, Intrinsic Robustness of the Price of Anarchy, STOC '09, Section 4.3.
      • AGT book, Sections 4.1-4.3.
      • Lecture notes by Bobby Kleinberg.
      • AGT book, Sections 4.4-4.5.
      • Section 3 of Roughgarden, Computing Equilibria: A Computational Complexity Perspective.
      • 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 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.
      • 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.
      • 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.
      • AGT book, Chapter 10.