CS 656: Algorithmic Game Theory

Units: 3-0-0-9

Pre-requisites: CS340

1. Basics of utility theory - the von Neumann-Morgenstern axioms for utility theory and characterisation theorem.
2. Definition of strategic form games, examples.
3. Some fundamental types of solutions concepts based on dominance (strict, weak), stability (equilibrium) and security (maximin). Relationship between these solution concepts in general games and in the special case of two player zero sum games.
4. Mixed extension of a strategic form game. Solution concepts based on mixed strategies.
5. Nash’s Theorem.
6. Complexity of computation of Nash equilibrium. Special case - 2 player zero sum games, correspondence between strong duality in LP and minimax theorem.
7. Improvement dynamics and potential games. Monderer-Shapley characterisation.
8. Congestion games
9. Computation of pure strategy equilibria in potential games - PLS completeness
10. Graphical games. 0/1 polymatrix games and hardness of computing equilibria.
11. Some subclasses of games which allow efficient computation of equilibria.
12. Efficiency of equilibria (price of stability, price of anarchy)
13. Introduction to auction theory, first price auction, second price auction, incentive compatibility.
14. Introduction to mechanism design, Groves Mechanism, pivotal mechanism and Bailey Cavallo mechanism. Green-Laffont result.
15. Stable matching.
16. Matching markets and sponsored search.