Algorithmic Game Theory
The course will have three modules:
Game theory: Strategic form games, 2-player games, pure and mixed strategy Nash equilibrium, computation of Nash equilibrium etc.
Mechanism: auctions, voting, kidney exchange, stable matchings
Fair division: various fairness criteria like envy-freeness, proportionality and their relaxations.
Prerequisites
A basic course in algorithms, discrete maths, and mathematical maturity.
Evaluation
There will be assignments, midterm and endterm.
References
- Game Theory and Mechanism Design by Y. Narahari
- Algorithmic Game Theory by Nisan, Roughgarden, Tardos, Vazirani (online copy)
Lectures
Material covered so far in each lecture:
- Aug 6: Introduction, motivation, and overview, examples of games: Prisoners' Dilemma, Braess's Paradox, pollution control, rock-paper-scissors. Informal introduction to strategies, and equilibrium (Ref: Lecture 1 of these notes)
- Aug 8: Strategic form games, assumptions in the model, dominated and dominant strategies, dominant strategy equilibrium, examples: Prisoners' dilemma, second-price sealed bid auction (Ref: these and these notes)
- Aug 13: Nash equilibrium: pure and mixed, example: battle of sexes, necessary and sufficient condition for Nash equilibrium, example: coordination game (ref)
- Aug 20: Equilibrium computation: Iterated elimination of dominated strategies, computing pure Nash equilibrium in bimatrix games, two-player zero-sum games, maxmin and minmax values, saddle points (Ref: 4.1 and 4.2 of this)
- Aug 22: Nash equilibrium in two-player zero-sum games (reference)
- Aug 29: Existence of Nash equilibrium in finite games via Brouwer's fixed point theorem (these notes and these notes)
- Sep 3: Computation of Nash equilibrium in 2-player games by support enumeration, towards Lemke-Howson algorithm (Section 1 of these notes)
- Sep 5: Lemke-Howson algorithm (Reference same as above, also see these slides and first 5 sections of these notes)
- Sep 10: Complexity classes TFNP and PPAD, (a very brief) proof sketch of PPAD-completeness of Nash equilibrium computation, FNP-completeness of Nash equilibrium computation implies NP=co-NP (reference)
- Sep 12: Other notions of equilibrium: approximate Nash equilibrium,
correlated equilibrium (Section 2 of these notes)