CS364A: Algorithmic Game Theory
Roughgarden (Office hours: Thursdays 1-2 PM in Gates 462)
(Office hours: Mon 11 AM-Noon and Wed 2-3 PM in Gates 460;
Email: pdh "at" stanford.edu)
11 AM-12:15 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;
auctions (efficient, revenue-maximizing, sponsored search, etc.);
congestion and potential games; cost sharing;
existence, computation, and learning of equilibria; game theory in the
Internet; network games; price of anarchy; selfish routing.
Prerequisites: basic algorithms and complexity (154N and 161, or equivalent).
Course requirements: 4 problem sets and a take-home final.
Students taking the course for a letter grade should
complete all 5 problems on each.
Students taking the course for pass/fail should
complete the first 3 problems on each.
There will also be occasional extra credit problems and opportunities.
No late assignments accepted.
Detailed schedule and references:
- Nisan/Roughgarden/Tardos/Vazirani (eds),
Algorithmic Game Theory,
Cambridge University, 2007.
- Also available free on the Web
- An even newer, excellent textbook that covers several of the
course's topics is Shoham and Leyton-Browm, Multiagent
Systems, Cambridge, 2008.
- To get a sense for the course in a nutshell:
An Algorithmic Game Theory
- Tue 9/23: Introduction: the Vickrey auction, Braess's
Paradox, and Nash equilibria. Readings:
- The Vickrey auction: AGT book, Section 9.3.1;
and/or Section 1 or these old CS364B notes.
- Braess's Paradox: Chapter 1 of T. Roughgarden,
Selfish Routing and the Price of Anarchy (MIT Press, 2005), available here.
- Basic games and equilibrium notions: AGT book, Sections 1.1.1--1.3.4.
- Thu 9/25: Auction and mechanism design basics. Sponsored search.
- AGT book, Sections 9.3.1, 9.3.2, 9.3.5, 9.5.4.
- Optional sponsored search readings: AGT book, Sections 28.1-28.3.1,
and Cornell lecture notes by
D. Easley and J. Kleinberg.
See also last year's 364B course for tons of subtopics and references on sponsored search auctions.
- Tue 9/30: Characterization of single-parameter truthful
mechanisms (Myerson's Lemma). Application to sponsored search.
Introduction to revenue-maxmizing auctions. Readings:
- AGT book, Sections 9.5.4--9.5.6. Optionally, see also Section 4
in this FOCS 2001 paper by Archer and Tardos.
- AGT book, Section 13.1.
- Thu 10/2: Myerson's theorem on Bayesian-optimal auctions.
Intro to prior-free revenue-maximizing auctions. Readings:
- AGT book, Section 13.2.
- Optional: Myerson's original paper: Optimal Auction Design,
Mathematics of Operations Research, 1981.
- Optional: Worst-case analysis for revenue maximization
originates in this SODA '01 paper by
- Tue 10/7: Prior-free revenue-maximizing auctions and the
4-competitive RSPE auction. Readings:
- AGT book, Section 13.4.
- Slides (through slide 13) on
the Hartline/Roughgarden framework for prior-free benchmarks.
(Optional: full paper.)
- Optional: Hartline's lecture
notes from an old CS364B course that we co-taught constitute an
expanded version of Chapter 13 of the AGT book.
- Optional: The RSPE auction and its analysis are originally from
this STOC '02 paper by
Fiat, Goldberg, Hartline, and Karlin.
- Thu 10/9:
Multi-parameter mechanism design and the VCG mechanism.
For more surveys on the VCG mechanism and combinatorial auctions that
are geared toward computer scientists, see:
- Tue 10/14: Combinatorial auctions with single-minded bidders.
There's also an excellent recent book devoted to combinatorial auctions:
- Thu 10/16: Communication complexity in combinatorial auctions.
Recent trends and open questions in algorithmic mechanism design.
- Tue 10/21:
Selfish routing and the price of anarchy: examples and preliminaries.
- Thu 10/23:
Selfish routing and the price of anarchy: tight bounds for
all classes of cost functions.
- Tue 10/28:
Finish selfish routing: a bicriteria bound and bounds for
atomic selfish routing networks.
Optional original references:
- AGT book, Sections 18.3.2, 18.4.2, and 18.5.2.
- Thu 10/30: Congestion and Shapley network cost-sharing games.
Optional original reference:
For much more on potentials:
- AGT book, Sections 17.2.2, 19.1, and 19.3.
- Tue 11/4:
Vetta's location game.
Optional original reference:
- Thu 11/6:
Out-of-equilibrium inefficiency bounds.
Introduction to regret-minimization.
- Tue 11/11:
Existence of no-regret algorithms, with application to
the minimax theorem in two-player zero-sum games. Reading:
- AGT book, Sections 4.3-4.4.2.
- Week 1 and Week 2
lecture notes from a course taught by Bobby Kleinberg.
- The von Neumann correspondence to Econometrica that I discussed is
- Thu 11/13:
Convergence of best-response dynamics to Nash equilibria
in congestion games: fast convergence to approximate equilbria.
- Tue 11/18:
PLS-completeness and negative convergence results. Primary reference:
Further good surveys:
- Thu 11/20:
PPAD-completeness of computing mixed-strategy Nash equilibria of
bimatrix games. Primary references:
- 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.
The Complexity of Computing a Nash Equilibrium, STOC 2006.
the Complexity of 2-Player Nash-Equilibrium, FOCS 2006.
- Tue 11/25: No class (Thanksgiving break).
- Thu 11/27: No class (Thanksgiving break).
- Tue 12/2: Proof of Nash's Theorem.
Introduction to approximate Nash equilibria.
For references on Nash's Theorem, see the following.
- 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 12/4: Hardness of approximately optimizing
over approximate Nash equilibria of a bimatrix game.