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)