CS364B: Topics in Algorithmic Game Theory

Instructors: Tim Roughgarden (Gates 462) and Jason Hartline (Microsoft)

Teaching Assistant: Zoe Abrams.
Office hours: Tuesdays 11:30-1:00 in Gates 466.
Email: zoe"the letter a"@stanford.edu.

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

Course description: In-depth study of three currently active topics on the interface of theoretical computer science and game theory: approximately efficient combinatorial auctions, optimal mechanism design, and the computational complexity of noncooperative equilibria. Can be taken prior to 364A. Can be repeated for credit. Prerequisites: 154N and 161, or equivalent.

Course requirements: For students enrolled pass/fail, the grade will be purely attendance- and participation-based. Students enrolled for a letter grade are expected to complete a major research project.

Research project:

• Suggested project topics + deadlines.

Lecture notes: To be handed out sporadically as the course goes on (and afterwards...).

• Lecture Notes on Combinatorial Auctions, by Tim Roughgarden.
  • Latest (and probably final) version as of 10/18/08.
  • Covers the first 6 lectures.
• Lectures on Optimal Mechanism Design, by Jason Hartline.
  • Latest version as of 4/28/06.

Schedule and references:

• Tue 9/27: [TR+JH] Introduction to and motivation for the three topics of the course.

• Thu 9/29: [TR] Introduction to algorithmic mechanism design via the Vickrey auction; the VCG mechanism. For surveys on algorithmic mechanism design 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.
  • For much more on the Vickrey auction, see Chapter 1 of the forthcoming book on combinatorial auctions (chapter by Ausubel and Milgrom).

• Tue 10/4: [TR] Finish VCG. A truthful, approximately efficient mechanism for combinatorial auctions with (unknown) single-minded bidders. Incompatibility of VCG with approximation algorithms.
  • This lecture is based on D. Lehmann, L. O'Callaghan, and Y. Shoham, Truth Revelation in Approximately Efficient Combinatorial Auctions, JACM 2002.
  • See also Sections 1-3 and 7 of Chapter 15 (by Amir Ronen) of the forthcoming book on combinatorial auctions. (Not online -- copies handed out in class.)
  • For much more on the tricky issue of combining the VCG mechanism with approximate winner determination algorithms, see N. Nisan and A. Ronen, Computationally Feasable VCG Mechanisms, EC 2000.

• Thu 10/6: [TR] Finish single-minded bidders (see references for previous lecture).

• Tue 10/11: [TR] Subpolynomial approximation for general CAs requires exponential communication (ignoring both incentive and computation constraints). References:
  • This lecture is primarly based on N. Nisan, The Communication Complexity of Approximate Set Packing and Covering , ICALP 2002.
  • This line of research was pioneered by Nisan and Segal. See N. Nisan and I. Segal, The Communication Requirements of Efficient Allocations and Supporting Lindahl Prices (A Self-Contained CS-Friendly Executive Summary). The full paper (to appear in Journal of Economic Theory) is here.
  • See also Chapter 11 (by Ilya Segal) of the forthcoming book on combinatorial auctions. (Not online -- copies handed out in class.)

• Thu 10/13: [TR] Finish communication complexity (see references above).

• Tue 10/18: [TR] Approximate winner-determination with complement-free bidders. Submodular and subadditive valuations. Value and demand queries. References:
  • Lehmann/Lehmann/Nisan, Combinatorial Auctions with Decreasing Marginal Utilities, EC 2001.
  • S. Dobzinski, N. Nisan, and M. Schapira, Approximation Algorithms for Combinatorial Auctions with Complement-free Bidders, STOC 2005.
  • Feige, On Maximizing Welfare when Utility Functions are Subadditive, 2005 (contact instructor for a copy).

• Thu 10/20: [TR] Demand queries and LP rounding for subadditive valuations. A general technique for transforming LP-based approximation algorithms for winner determination into truthful in expectation, approximately efficient CAs. References as above plus the following.
  • Reference: R. Lavi and C. Swamy, Truthful and Near-optimal Mechanism Design via Linear Programming, to appear in FOCS 2005.

• Tue 10/25: Guest lecture by Zoe Abrams on sponsored search auctions. Reference:
  • Privacy Protection and Advertising in a Networked World. Gagan Aggarwal, PhD Thesis, Stanford University, September, 2005. Chapter 6.

• Thu 10/27: [JH] Single-parameter agent setting, characterization of truthful mechanisms.
  • Myerson, "Optimal Auction Design", 1981. (handout)
    This paper contains proof of the characterization of truthful mechanisms, the reduction from profit maximization to surplus maximization via virtual valuations, and the revenue equivalence theorem.
  • Archer, Tardos, "Truthful mechanisms for One-parameter Agents", FOCS 2001.
    This paper contains an accessible proof of the characterization of truthful mechanisms.
  • Krishna, "Auction Theory", Elsevier 2003. This text book is a good, accessible introduction to auction theory from a traditional Economics point of view.

• Tue 11/1: [JH] Bayesian optimal mechanism design.
  We give Myerson's proof (see papers from 10/27) reducing the problem of optimizing profit to the problem of optimizing surplus via the concept of virtual valuations. We present this in the full generality of the single-parameter agent setting (which is not considered explicitly in the literature).

• Thu 11/3: [JH] Worst-case optimal mechanism design: competitive analysis framework, and deterministic lower bounds.
  • Goldberg, Hartline, Wright, "Competitive Auctions and Digital Goods", SODA 2001.
    This paper defines the digital good auction problem, gives the deterministic symmetric lower bound, and an auction that is competitive.
  • Fiat, Goldberg, Hartline, Karlin, "Competitive Generalized Auctions" STOC 2002.
    This paper defines the competitive framework that we use. It gives a competitive auction that we will discuss on 11/8.

• Tue 11/8: [JH] Worst-case optimal mechanism design: constant-competitive auctions, lower bounds on the optimal competitive ratio.
  • Goldberg, Hartline, Karlin, Saks, A Lower Bound on the Competitive Ratio of Truthful Auctions, STACS 2004.
  • Hartline, McGrew, "From Optimal Limited to Unlimited Supply Auctions", EC 2005.
    This paper explores gives the auction with the optimal competitive ration for three bidders. It gives the auction with the best known competitive ratio in general. It discusses auctions that are competitive with benchmarks other than "the optimal single price sale with at least two winners".

• Thu 11/10: [JH] Online Auctions.
  • Blum, Hartline, "Near-Optimal Online Auctions", SODA 2005.
    This paper uses an expert learning algorithm due to Kalai to derive a near optimal online auction. Expert learning algorithms and multi-armed bandit algorithms are fundamental to the design of optimal online auctions.
  • Auer, Cesa-Bianchi, Freund, Schapire, Gambling in a rigged casino: the adversarial multi-armed bandit problem, FOCS 1995.
    This is a good reference for the multi-armed bandit problem.

• Tue 11/15: [TR] Finite noncooperative games, and the special case of two-player, zero-sum games.
  • This material is classical and can be found in many different sources; a favorite of mine is Chapter 15 of Vasek Chvatal's book, "Linear Programming" (Freeman, 1983).

• Thu 11/17: [TR] Enumeration algorithms and applications.
  • The quasipolynomial-time algorithm for finding approximate Nash equilibria is from
    • R. Lipton, E. Markakis, and A. Mehta, Playing Large Games using Simple Strategies, EC '03.
  • We didn't have time to cover the more recent application of enumeration algorithms to random games in
    • I. Barany, S. Vempala, and A. Vetta, Nash equilibria in random games, FOCS '05.
    This paper shows that for various distributions on bimatrix games, with high probability there is a Nash equilibrium with small (constant-size) support. Thus the enumeration algorithm runs in polynomial time with high probability. (It is still open whether or not the expected running time of the enumeration algorithm is polynomial for these distributions.)

• Tue 11/22: No class (Thanksgiving break).

• Thu 11/24: No class (Thanksgiving break).

• Tue 11/29: [TR] Introduction to reductions between classes of games.
  • The polynomial reduction from bimatrix games to 2-player symmetric games was first given by Gale, Kuhn, and Tucker, "On Symmetric Games", in Contributions to the Theory of Games (Volume I), 1950.
  • The proof that computing Nash equilibria in r-player games (where r is an arbitrarily large fixed constant) reduces (in poly-time) to the 4-player case is from
    • P. W. Goldberg and C. H. Papadimitriou, Reducibility Among Equilibrium Problems, 2005.
    Hot off the press are two papers that reduce the r-player problem to the 3-player version of the problem:
    • Daskalakis/Papadimitriou, Three-Player Games Are Hard.
    • Chen/Deng, 3-Nash Is PPAD-Complete.

• Thu 12/1: [TR] Further discussion of reducing computing Nash equilibria in r-player games to 4- and 3-player games (see references above).

• Tue 12/6: [TR] PPAD-completeness. 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.

• Thu 12/8: [TR] PPAD-completeness of computing Nash equilibria with three or more players. Reference:
  • K. Daskalakis, P. Goldberg, C. Papadimitriou, The Complexity of Computing a Nash Equilibrium, 2005.
  And just in time for the end of the course (!!!):
  • Chen/Deng, Settling the Complexity of 2-Player Nash-Equilibrium (Dec 4, 2005).