CS364A: Introduction to Algorithmic Game Theory
Roughgarden (Gates 462)
Mukund Sundararajan (Office hours: Tue 4-5 PM and by appt in Gates 470).
Sergei Vassilvitskii (Office hours: Wed 11-noon and by appt in Gates 492).
2:45-4 PM on Tuesdays and Thursdays in Gates B12.
Broad survey of topics at the interface of theoretical computer science
and game theory such as: algorithmic mechanism design; combinatorial and
competitive auctions; congestion and potential games; cost sharing;
existence, computation, and learning of equilibria; game theory in the
Internet; network games; price of anarchy and stability; pricing; and
selfish routing. Minimal overlap with 224M and 324. Prerequisites: 154N
and 161, or equivalents.
Course requirements: Three problem sets and a 10-15 page report
summarizing 1-3 research papers. (Students taking the course
pass/fail need only do the problems sets or the report, not both.)
Schedule and references:
- Tue 9/26: Introduction to the course; introduction to auctions.
- Thu 9/28: Introduction to algorithmic mechanism design. The Vickrey
(second-price) auction. Introduction to competitive auctions
- Tue 10/3: Guest lecture by Jason Hartline (Microsoft) on
- Thu 10/5: Guest lecture by Zoe Abrams (Yahoo) on
sponsored search auctions. Reading:
A few other recent papers on the topic include:
- Tue 10/10: Introduction to combinatorial auctions.
The VCG mechanism.
For more surveys on algorithmic mechanism design, combinatorial auctions,
and the VCG mechanism that are geared toward
computer scientists, see:
There's also an excellent recent book on the topic:
- Thu 10/12: Truthful approximate combinatorial auctions and
the winner determination problem. For material on single-minded
For a good discussion of the winner determination problem with
complement-free bidders, and for the best approximation algorithm
known for the subadditive case, see
- Tue 10/17: Communication lower bounds in combinatorial auctions.
Introduction to cost-sharing mechanisms.
References for communication lower bounds:
The fixed-tree multicast problem was introduced in
- Thu 10/19: Design and analysis of optimal Moulin cost-sharing mechanisms.
- Tue 10/24: Finish cost-sharing mechanisms.
Introduction to nonatomic selfish routing games and the price of anarchy.
- Thu 10/26:
Bounding the price of anarchy for nonatomic selfish routing.
- Tue 10/31: The price of anarchy in nonatomic and atomic selfish
routing games. Reference:
The price of anarchy in atomic selfish routing games was first analyzed in:
- "Routing Games" (see last lecture).
- Thu 11/2: Existence of equilibrium flows. The potential function
method. Introduction to Shapley network design games and the price of
stability. Main reference:
Shapley network design games were defined in:
For more studies on the inefficiency of equilibria in network
formation games, see, for example:
- Tue 11/7: Finish Shapley network design games.
Convergence of better-response dynamics in congestion and potential
- Congestion games were first defined in Robert Rosenthal, "A Class of Games Possessing
Pure-Strategy Nash Equilibria", International Journal of Game Theory 1973.
- Potential games were first defined in Dov Monderer and Lloyd Shapley, "Potential Games", Games and
Economic Behavior 1996.
- Thu 11/9: The interplay between convergence and price of anarchy
bounds. Sink equilibria. References:
- A. Vetta, Nash equilibria in
competitive societies with applications to facility location, traffic
routing, and auctions, FOCS 2002;
- V. Mirrokni and A. Vetta,
Convergence issues in competitive games, APPROX 2004.
- M. X. Goemans, V. Mirrokni, and A. Vetta,
Sink equilibria and convergence, FOCS 2005.
- Tue 11/14:
Convergence of best-response dynamics to Nash equilibria
in congestion games: fast convergence to approximate equilbria.
- Thu 11/16:
Convergence of best-response dynamics to Nash equilibria
in congestion games: slow convergence to exact equilbria.
PLS-completeness. Main reference:
- Tue 11/21: No class (Thanksgiving break).
- Thu 11/23: No class (Thanksgiving break).
- Tue 11/28: Computing equilibria using linear programming:
2-player zero-sum games. Proof sketch of Nash's Theorem.
For references on Nash's Theorem, see the following.
- The material on zero-sum games 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).
- The von Neumann correspondence to Econometrica that I discussed is
- The Dantzig quote was from the Preface to Volume 1 of his
book on Linear Programming (with Thapa), 1997.
- 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.,
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,
and Walras Equilibrium Via Brouwer, Economic Theory
- Thu 11/30:
Approximate Nash equilibria via sampling and enumeration.
Introduction to correlated equilibria.
- The quasipolynomial-time algorithm for finding approximate Nash
equilibria is from
- For recent applications of
enumeration algorithms to random games, see:
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 12/5:
Computing correlated equilibria using linear programming.
Warm-up to PPAD: Sperner's Lemma and Brouwer's FIxed-Point Theorem.
- Our treatment of Sperner's Lemma and Brouwer's Theorem follows
that outlined in course notes from
and Cornell (part
1 and part
- Thu 12/7:
Reductions between computing Nash equilibria and computing
- N. Megiddo and C. Papadimitriou,
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.
- K. Daskalakis, P. Goldberg, C. Papadimitriou,
The Complexity of Computing a Nash Equilibrium, STOC 2006.
the Complexity of 2-Player Nash-Equilibrium, FOCS 2006.