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:
Lecture notes: To be handed out sporadically as
the course goes on (and afterwards...).
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:
- 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.
- 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:
- 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:
- 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.
- Tue 10/25: Guest lecture by Zoe Abrams on sponsored search auctions.
Reference:
- 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.
- Thu 11/10: [JH] Online Auctions.
- 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
- We didn't have time to cover the more recent application of
enumeration algorithms to random games in
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
Hot off the press are two papers that reduce the r-player problem
to the 3-player version of the problem:
- 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:
- Thu 12/8: [TR] PPAD-completeness
of computing Nash equilibria with three or more players.
Reference:
And just in time for the end of the course (!!!):