6.896: Topics in Algorithmic Game Theory
Spring 2010
As Computer Science struggles to understand the Internet and its capabilities, computer scientists are incorporating concepts and methodologies from
Economics and Game Theory into their discipline. In the past decade, there
has been a tremendous growth in research, centering around the following
questions: what game-theoretic tools are applicable to computer systems?
How far is the performance of a system from optimality due to the conflict
of interests of its users and administrators? And how can we design a system whose performance is robust with respect to the potential conflict of
interests inside the system?
This class aims to tackle some of the fundamental problems at the interface of Computer Science and Game theory, with an emphasis on algorithms and computational complexity. Our main focus will be on algorithms for equilibria, the complexity of equilibria and fixed points, algorithmic tools in mechanism design, learning in games, and the price of anarchy.
Another Class of Potential Interest: 6.254 --- Game Theory with Engineering Applications
Course Information
- Instructor: Constantinos Daskalakis
Office Hours: Send me an email.
- TA: Yang Cai
Office Hours: Send Yang an email.
- Lecture: Mondays and Wednesdays 2:30-4:00, 4-145.
- Textbook: Algorithmic Game Theory, by Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani (eds.), Cambridge University Press, September 2007.
- Lecture Notes: Lecture notes and/or presentations will be provided.
- Prerequisites: A course in algorithms (6.046 or equivalent), probability (6.041 or equivalent), and discrete mathematics (6.042 or equivalent).
- Assessment: Students will be required to scribe one or two lectures, do a small number of homework problems, and a research-oriented final project. This could be either a survey, or original research; students will be encouraged to relate the project to their own research interests.
Course Outline
There is a significant dynamic component to the course, as topics drop
in and out, or get longer or shorter treatment, depending on audience
interest/reaction/resistence. We consider this a feature. Given this,
here is a rough outline of the course material:
- Introduction
- Examples of games and basic solution concepts, such as the Nash and the correlated equilibrium;
- Nash equilibria in 2-player zero-sum games, min-max solutions & relation to Linear Programming Duality.
- Nash Equilibria
- Existence of equilibria: proof via Sperner's lemma; emphasis on the combinatorial proofs of existence;
- Algorithms for computing Nash equilibria: the Lemke Howson
algorithm, support enumeration algorithms, sampling methods,
simplicial approximation algorithms;
- Complexity theory of total search problems and fixed points: definition of the complexity classes PLS, PPAD, PPP and relation
to P, NP;
- The complexity of computing a Nash equilibrium: PPAD-completeness
results;
- The complexity of pure Nash equilibria in congestion games:
PLS-completeness results;
- Description method vs computational complexity in games; alternative game representations: graphical games, action graph
games; emphasis on modeling the structure of the player interactions;
- Symmetries in games: algorithms for symmetric games; algorithms for anonymous games; relation to Central Limit Theorems
in probability theory.
- Algorithms for Correlated Equilibria.
- Market Equilibria
- Arrow-Debreu existence theorem;
- Algorithms for markets with linear utility functions;
- PPAD-hardness of markets with Leontief utility functions and
markets with piecewise-linear utility functions.
- Learning in games: fictitious play, experts algorithm, no-regret algorithms; convergence for zero-sum games; cycling behavior
for general games.
- Mechanism Design
- algorithmic mechanism design;
- auctions for digital goods;
- combinatorial auctions: path auctions in networks and VCG;
- computational hardness of approximate combinatorial public project
auctions;
- Bayesian Mechanism Design.
- Price of Anarchy : selfish routing in networks; PoA results for
atomic and non-atomic congestion games.
Please us the scribe template to produce your notes. The template contains commands for Theorem, Lemma, Corollary, Proposition, Claim, Definition, Construction, Remark etc. An example file where this template is used is here .
- Lecture 1 (February 3rd): Introduction to Algorithmic Game Theory and Overview of the Class. Examples of Games; Nash Equilibrium; Computation of equilibria; Price of Anarchy; Mechanism Design. Slides; Slides in no-animation pdf file .
- Lecture 2 (February 8th): Definitions of Games and Equilibria; Zero-Sum Games; Minmax Theorem; Proof using Linear Programming Duality. Notes.
- Lecture 3 (February 10th): Fictitious Play; Robinson's Proof and rate of Convergence; Karlin's Conjecture; Beyond Fictitious Play: Learning from Expert Advice; Follow the Leader and Hedging Algorithms. Notes.
- Lecture 4 (February 16th): Quadratic convergence of the Hedging Algorithm against an adversary; Tightness of the bound; Implications for Zero-Sum Games. Notes.
- Lecture 5 (February 17th): Multiplayer Games; Nash equilibria; Proof of Nash's Theorem via Brouwer's Fixed Point Theorem; Proof of Sperner's Lemma in 2 dimensions; Proof of Brouwer's theorem via Sperner's lemma in 2 dimensions. Slides; Slides in no-animation pdf file; Notes.
- Lecture 6 (February 22nd): Multi-dimensional version of Sperner's Lemma; Canonical Simplicization of the Hypercube; Legal Coloring; Proof of Sperner's Lemma; Direction in the space. Slides; Slides in no-animation pdf file; Notes.
- Lecture 7 (February 24th): Total Search Problems; FNP; Computational Problems SPERNER, BROUWER, NASH; Complexity Theory of Total Search Problems; PPAD. Slides; Slides in no-animation pdf file; Notes.
- Lecture 8 (March 1st): Complexity Theory of Total Search Problems: PPAD, PPA, PPP, PLS; PPAD-completeness of SPERNER. Slides; Slides in no-animation pdf file; Notes.
- Lecture 9 (March 3rd): PPAD-completeness of BROUWER; towards a PPAD-completeness of NASH: game gadgets. Slides; Slides in no-animation pdf file .
- Lecture 10 (March 8th): PPAD-completeness of NASH. Slides; Slides in no-animation pdf file .
- Lecture 11 (March 10th): Algorithms for Nash Equilibria: Simplicial Approximation Algorithms; Support Enumeration; Lipton-Markakis-Mehta; Symmetrization. Slides; Slides in no-animation pdf file .
- Lecture 12 (March 15th): The Lemke-Howson Algorithm; Inapproximability Results for Nash equilibria; Constant Approximation Algorithms; Algorithms for Graphical Games; the Total Variation Distance bound. Slides; Slides in no-animation pdf file .
- Lecture 13 (March 17th): Multiplayer Zero-Sum Games; Anonymous Games; Probabilistic Approximation Theorems; Introduction to Market Equilibria. Slides Part a and Part b ; Part a in no-animation pdf file and Part b in no-animation pdf file .
- Lecture 14 (March 29th): Proof of the Arrow-Debreu Theorem for exchange economies; Utility Functions; Fisher's Model ; Eisenberg-Gale Convex Program for Fisher Markets. Slides; Slides in no-animation pdf file .
- Lecture 15 (March 31st): Complexity of Exchange Markets; Excess Demand Functions; Gross-Substitutability (GS) Condition; Computation of Equilibria under (GS); Tatonnement Procedure for (GS) markets. Slides; Slides in no-animation pdf file .
- Lecture 16 (April 5th): Introduction to Social Choice Theory; Majority Voting ; Arrow's Impossibility Theorem.
- Lecture 17 (April 7th): Proof of Arrow's Impossibility Theorem. Manipulability of social choice functions.
- Lecture 18 (April 12th): Gibbard-Satterthwaite Theorem; Introduction to Mechanisms with Money; Vickrey's Second Price Auction. Slides; Slides in no-animation pdf file .
- Lecture 19 (April 14th): Incentive Compatible Mechanisms; VCG mechanisms; Clarke Pivot Rule; Examples; Games with Strict Incomplete Information.
- Lecture 20 (April 21st): Implementation in Dominant Strategies; The Revelation Principle; Characterization of Incentice Compatible Mechanisms: Direct Characterization, and Weak Monotonicity.
Slides; Slides in no-animation pdf file .
- Lecture 21 (May 3rd): Frugality in Auctions: Path Auctions and Spanning Tree Auctions.
Slides; Slides in no-animation pdf file .
- Lecture 22 (double) (May 5th): Single-Parameter Settings; Bayesian Mechanism Design; Characterization of Truthful Mechanisms; Myerson's Optimal Mechanism; Vickrey Auction with Reservation Price.
Hartline's notes.
- Lecture 23 (May 10th): Congestion games; Price of Anarchy.
Roughgarden's notes.
- Lecture 24 (double) (May 12th): Project Presentations.
Online Resources
Different incarnations of the class at other universities: