6.853: Topics in Algorithmic Game Theory
Fall 2011
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.
The course will be offered concurrently with a similar course at UC Berkeley by Christos Papadimitriou, see here. The courses will not be simulcasted or otherwise synchronized, but will cover highly overlapping materials and will share resources like lecture notes.
Course Information
- Instructor: Constantinos Daskalakis
Office Hours: send me an email.
- TA: Matt Weinberg
Office Hours: Mondays and Wednesdays, 12pm-2pm, 32-G604.
- Lecture: Tuesdays and Thursdays 2:30-4:00, 1-134 (both are subject to change).
- 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: The grade comprises the following components (which may sum to more than 100%):
- 25% from scribing a lecture, improving on existing lecture notes. Bonus of 10% if you scribe a second lecture.
- 35% from weekly homework problems; these are assigned in class and posted here, and are due the next Tuesday from when they are given. Every week's problems are worth 10 points.
- 40% from the final project: this could either be 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
- Games, solution concepts, auctions.
- Zero-sum Games
- Min-max theorem & Linear Programming Duality;
- Game Dynamics: fictitious play;
- No-regret Learning: multiplicative weights update method;
- Multi-player Zero-sum games.
- General Games
- Existence of Nash 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.
- Correlated Equilibria.
- Algorithms: Ellipsoid against hope;
- No internal-regret algorithms.
- Market Equilibria
- the Arrow-Debreu existence theorem;
- Algorithms for markets with linear utility functions;
- Tatonnement;
- PPAD-hardness of markets with Leontief utility functions.
- Mechanism Design
- Social Choice Theory: Arrow's impossibility theorem, the Gibbard-Satterthwaite theorem;
- Mechanisms with Money: second-price auction, digital goods, Vickrey-Clarke-Groves mechanism;
- Combinatorial Auctions: path auctions, frugality, inapproximability results;
- Bayesian Mechanism Design: Myerson's Theorem, prior-independent mechanisms;
- Multi-dimensional Mechanism Design.
- Price of Anarchy : selfish routing in networks, PoA in congestion games.
Homework
Problems are due the next Tuesday after they are given and will be accumulating in this file.
Please use 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. As scribes become available, the will be published here. At the same time, the list below will contain notes/presentations produced by the instructor.
- Lecture 1 (Sept 8th): Introduction to Algorithmic Game Theory: Incentives in Large Systems; Games; Nash Equilibria and their computation; the Price of Anarchy; Mechanism Design. Slides.
- Lecture 2 (Sept 13th): Two-player Zero-sum Games and Linear Programming. Notes.
- Lecture 3 (Sept 15th): Multiplayer Zero-Sum Games. Notes.
- Lecture 4 (Sept 20th): Distributed Dynamics for Zero-sum Games: Fictitious Play, Multiplicative-Weights-Updates. Notes.
- Lecture 5 (Sept 22th): Multiplicative-Weights-Updates Performance; Application of Online-Learning to Zero-Sum Games; Nash's Theorem. Notes.
- Lecture 6 (Sept 27th): Brouwer's Theorem; Visualization of Nash's Construction; Combinatorial proof of Brouwer's Theorem via Sperner's Lemma: the 2-dimensional case. ppt.
- Lecture 7 (Sept 29th): Sperner's Lemma in general dimensions: Simplicization of the hypercube; Sperner Colorings; Direction in high-dimensional Euclidean space. ppt.
- Lecture 8 (Oct 4th): Total Search Problems; FNP; Computational Problems SPERNER, BROUWER, NASH; Complexity Theory of Total Search Problems; PPAD. ppt.
- Lecture 9 (Oct 6th): Complexity Theory of Total Search Problems: PPAD, PPA, PPP, PLS; PPAD-completeness of SPERNER. ppt.
- Lecture 10 (Oct 13th): PPAD-Completeness of BROUWER; PPAD-Completeness of Nash Equilibrium in Graphical Games. ppt.
- Lecture 11 (Oct 18th): PPAD-completeness of 2-Player Games; Algorithms for Nash equilibrium: Simplicial Approximation, Support Enumeration, Lipton-Markakis-Mehta. ppt.
- Lecture 12 (Oct 20th): Symmetric Games; Lemke-Howson; Complexity of Approximating a Nash equilibrium. ppt.
- Lecture 13 (Oct 25th): Algorithms for Special Classes of 2-player and graphical games; Multi-player zero-sum games; Anonymous games. The Total Variation Distance bound. Proper Central Limit Theorems and their application to anonymous games. ppt.
- Lecture 14 (Oct 27th): Adam Smith-Augustin Cournot-Leon Walras. The Exchange Market Model. Walrasian Equilibria. The Arrow-Debreu Theorem. CES utilities. Fisher's Model.ppt.
- Lecture 15 (Nov 1st): The Eisenberg-Gale Program. Complexity of the Exchange Model. Gross-Substitutability. Weak-Axiom of Revealed Preferences (WARP).ppt.
- Lecture 16 (Nov 3rd): Exchange Economies with Gross-Substitutability: Centralized Computation (WARP as a Separation Oracle) and Distributed Computation (via Tatonnement). Convex Programs for CES Exchange Economies.ppt; notes.
- Lecture 17 (Nov 8th): Introduction to Mechanism Design. Vickrey Auction. Mechanisms without Payment. Incentive Compatibility. Gibbard-Satterthwaite Theorem. notes.
- Lecture 18 (Nov 10th): Arrow's Impossibility Theorem. see here
- Lecture 19 (Nov 15th): Proof of the Gibbard-Satterthwaite Theorem. see here
- Lecture 20 (Nov 17th): Vickrey-Clarke-Groves Mechanisms. see here
- Lecture 21 (Nov 17th): VCG Examples. The Revelation Principle. ppt.
- Lecture 22 (Nov 19th): Characterization of Incentive Compatible Mechanisms: Direct Characterization, Weak Monotonicity. Characterization of Implementable Social Choice Functions: Roberts Theorem. Bayesian Mechanisms; Bayes-Nash Implementation. First Price Auction. Revenue Equivalence Theorem. ppt.
- Lecture 23 (Dec 1st): Myerson's Revenue Optimal Auction. my notes. Also: Hartline's Notes.
- Lecture 24 (Dec 6th): Examples of Myerson's Auction. Bulow-Klemperer. Prior-Free Revenue Maximization. Competitive Analysis. Matt's Slides.
- Lecture 25 (Dec 8th): Price of Anarchy. Roughgarden-Tardos Paper.
- Lecture 26 (Dec 13th): Project Presentations.
Online Resources
Previous incarnation of this class:
Similar Classes in other universities