This is an interdisciplinary course on algorithmic game theory and mechanism design. These fields sit at the interface between computer science and economics, and have recently seen a growing number of real-world applications. This course will review the foundational models and core theoretical insights that have been instrumental in their development. The course will be organized in three parts and will cover (a subset of) the following topics:
Game theory: Nash equilibria, Price of anarchy (PoA), congestion games and Braess paradox, zero-sum games and the minimax theorem, Stackelberg equilibrium and security games, and equilibria computation.
Mechanism design with money: Bayes-Nash equilibria, dominant strategy equilibria, the revelation principle, VCG auction, Myerson's auction, 1st and 2nd price auctions, the revenue equivalence theorem, greedy approximation algorithms.
Mechanism/algorithm design without money: facility location, matching markets, social choice theory --- axiomatic, statistical, and utilitarian approaches, Arrow's and Gibbard-Satterthwaite impossibility, fair division of divisible and indivisible goods.
Course Website: https://www.cs.toronto.edu/~nisarg/teaching/304f22/index.html