Algorithmic Game Theory (August-November, 2025)

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

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)
Oct 29: Simple near-optimal auctions using prophet inequality (Ref)
Nov 5: Prior-free auctions and Bulow-Klemperor theorem (Ref as above)
Nov 7: Mechanism design without money - Stable matchings: Deferred acceptance algorithm, man-optimality, truthfulness (Ref: Section 3 of these notes
Nov 14: House allocation and kidney exchange (for HA and for kidney exchange)
Nov 19: Kidney exchange continued. Popular matchings: Algorithm for strict preferences (ref)
Nov 21: Popular matchings continued: strategic behavior, algorithm for weak preferences, popularity in two-sided preferences (ref for strategic behavior, ref for two-sided preferences)