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:
Module 1: Games and Equilibria
- 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)
Module 2: Fair division
- Sep 17: Fair division: cake cutting and rent division using Sperner's lemma (reference)
- Sep 19: Fair division of indivisible items: envy-free and EF1 allocations by round-robin and envy-cycle elimination algorithms (Notes)
- Sep 24: Social welfare and Pareto optimality, EF1+PO allocations via maximum Nash welfare (ref)
- Sep 26: Proportionality, Moving knife algorithm, PROP1 allocations, EF1 implies PROP1, definitions of EFX, PROPX and open questions
Module 3: Mechanism design
- Oct 8: Single item auctions: first and second price auctions, awesome auctions, single parameter environments and sponsored
search auctions, statement of Myerson's lemma (ref)
- Oct 15: Proof of Myerson's lemma (ref)
- Oct 17: DSIC mechanisms for single item and sponsored search auctions using Myerson's lemma, knapsack auctions, approximate
social surplus maximization using 1/2-approximation for knapsack (ref For greedy knapsack, and an approximation algorithm, see these notes)
- Oct 22: Revelation principle, revenue maximizing auctions (Ref)
- Oct 24: Revenue maximization: Bayesian analysis (Ref)