CS364A: Algorithmic Game Theory
Roughgarden (Gates 462)
Sergei Vassilvitskii. Office hours: Tuesdays 10:30-noon in Gates 464.
1:15-2:30 PM on Tuesdays and Thursdays in Gates B08. (Room will be
B12 starting on Thursday 10/7.)
Broad, graduate-level overview of topics on the interface of
computer science and game theory. Possible topics include: auctions;
congestion and potential games; cost sharing; existence and
equilibria; game theory in the Internet; mechanism design; network
price of anarchy; pricing; selfish routing. Minimal overlap with 224M
324. Prerequisites: 154N and 161, or equivalent.
Course requirements: Two problem sets and a 10-15 page report
summarizing 2-3 research papers.
Schedule and references:
- Tue 9/28: Introduction: Braess's Paradox, the Vickrey auction, and
- Thu 9/30: Selfish routing: examples and optimality conditions.
- Most of these preliminaries date back to M. Beckmann,
C. B. McGuire, and C. B. Winsten, Studies in the Economics of
Transportation, Yale University Press, 1956.
- Much of it can be found online in T. Roughgarden and E. Tardos, How Bad Is
Selfish Routing?, Journal
of the ACM, 49(2):236--259, 2002. (Conference version in FOCS 2000.)
- Tue 10/5: Selfish routing: Worst-case price of anarchy always
occurs in Pigou-like networks.
- This result was first proved in T. Roughgarden, The Price of
Anarchy Is Independent of the Network Topology, Journal of
Computer and System Sciences, 67(2):341--364, 2003. (Conference
version in STOC 2002.)
- The proof given in class is due to E. Tardos; see these lecture
notes from Cornell CS684.
- For another proof (that also works in a somewhat more general
context), see J. R. Correa, N. E. Stier Moses, and
A. S. Schulz, Selfish
Routing in Capacitated Networks, Mathematics of Operations
Research, 2004 (to appear). (Conference version in SODA 2003.)
- Thu 10/7: Selfish routing: Completion of last lecture and a
bicriteria bound for general networks.
- Tue 10/12: Braess's Paradox: Worst-case severity;
algorithmic complexity of detection.
- Survey of results of three papers: (1)
T. Roughgarden, On the
Severity of Braess's Paradox: Designing Networks for Selfish Users Is
Hard, Journal of Computer and System Sciences, to appear.
(Conference version in FOCS 2001.)
H. Lin, T. Roughgarden, and E. Tardos, A Stronger Bound
on Braess's Paradox, SODA 2004.
H. Lin, T. Roughgarden, E. Tardos, and A. Walkover,
Braess's Paradox, Fibonacci Numbers, and Exponential
Inapproximability. (Not online.)
- Thu 10/14: No class
- Tue 10/19: Price of anarchy in network design and congestion games.
- This lecture
is based on a very recent (FOCS 2004) paper:
A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, and T. Roughgarden,
The Price of
Stability for Network Design with Fair Cost Allocation.
- See also
A. Dasgupta, E. Tardos, and T. Wexler,
Network Design with Selfish Agents (STOC 2003) and
- A. Fabrikant, A. Luthra, E. Maneva, C. H. Papadimitriou, and
S. Shenker, On a
Network Creation Game (PODC 2003) for other recent papers along
- Thu 10/21: Price of anarchy in bandwidth allocation.
- Tue 10/26: Price of anarchy and convergence to Nash equilibrium in
facility location games.
- Thu 10/28: Vickrey auction, introduction to shortest-path
auctions, combinatorial auctions, and Vickrey-Clarke-Groves (VCG)
mechanisms. For surveys on algorithmic mechanism design geared toward
computer scientists, see:
- Tue 11/2: Shortest-path auctions and frugal mechanisms.
This lecture is based on:
- Thu 11/4: No class
- Tue 11/9: Combinatorial auctions. The proof done in class is from
- Thu 11/11: Auctions for digital goods.
- This lecture is based on A. V. Goldberg, J. D. Hartline, A. R. Karlin,
and A. Wright,
- Tue 11/16: Cross-monotonic cost sharing yields group strategyproof
mechanisms. The main result from this lecture is from
- H. Moulin,
Incremental Cost Sharing: Characterization by
Group Strategyproofness, Social Choice and Welfare, 16:279--320, 1999.
- H. Moulin and S. Shenker,
Strategyproof Sharing of Submodular
Costs: Budget Balance versus Efficiency, Economic Theory,
18:511--533, 2001. The multicast application is from:
- J. Feibenbaum, C. Papadimitriou, and S. Shenker,
Sharing the Cost of Multicast Transmissions,
Journal of Computer and System Sciences, 63:21--41, 2001.
(Conference version in STOC 2000.)
- Thu 11/18: Multicast cost sharing.
- Tue 11/23: 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/25: No class (Thanksgiving)
- Tue 11/30: Existence of Nash equilibria in non-zero-sum games:
Nash's Theorem, Sperner's Lemma, and Brouwer's Theorem.
- 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
- 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/2: Completion of proof of Nash's Theorem (see references
for previous lecture).