Algorithmic Game Theory

Two-player zero-sum games, minimax theorem, bimatrix games, Nash equilibrium, n-player finite games. Computational complexity of Nash equilibrium and the class PPAD. Correlated equilibrium, online convex optimization and regret minimization, swap-regret and correlated equilibrium. Congestion games and selfish routing games, pure Nash equilibrium, potential functions and convergence to equilibrium, the class PLS, price of anarchy and price of stability, how to mitigate price of anarchy. Social choice and mechanism design, dominant strategies and truthfulness, impossibility results of Arrow and Gibbard-Satterthwaite, voting rules, single-peaked preferences, generalized median mechanisms, facility location games. Stable matchings, top-trading cycles. Welfare and revenue maximization, single-parameter bidders, Myerson’s characterization, Myerson’s optimal auction, multidimensional bidders, VCG mechanism, combinatorial auctions, computationally efficient mechanisms, valuation functions, demand and value queries, computationally efficient mechanisms for submodular and XOS valuations. Procurement auctions and budget feasible mechanisms. Mechanisms for revenue maximization. Simple non-truthful auctions and price of anarchy analysis through smoothness. Generalized Second Price mechanism and electronic advertisement. Spectrum auctions.