Algorithmic Game Theory

ABOUT THE COURSE: Game theory is the formal study of interaction between "self-interested" (or "goal-oriented") "systems" (or "agents" or "decision makers" or "players"), and strategic scenarios that arise in such settings. It began life in Economics in the 1940's with the work of von Neumann and Morgenstern, but has since been applied to an extraordinary range of subjects, including political science, evolutionary biology and even to inspection regimes for arms control. Game theory has for years also played an important, if less recognized, role in several branches of computer science. Applications within computer science include the use of games in automated verification and model checking to model computing systems in an unknown and possibly adverse environment. In AI games are applied to the analysis of multi-agent systems. Recently, with the advent of the internet and e-commerce, many game theoretic questions in the interplay between economics and computing have received extensive attention. These include electronic auctions, and more generally mechanism design questions (inverse game theory) related to finding incentive structures for cooperation between independent entities on the internet.Wherever game theory plays a quantitative role, algorithmic and computational questions related to "solving" games are also of central importance. This course discusses algorithmic aspects of game-theoretic models, with a focus on recent algorithmic and mathematical developments.INTENDED AUDIENCE: Under-graduate And Post-graduatesPREREQUISITES: Knowledge of algorithmsINDUSTRY SUPPORT: All Software Companies Especially Google, Microsoft, Etc.

Week 1: Introduction to game theory: Non-cooperative game theory, Zero sum and general sum games Week 2:Minmax strategies, Nash equilibrium Week 3:Yao’s Lemma, Special Classes Games Week 4:Potential Games, Local Search Week 5:Complexity Classes: FNP, TFNP, PPAD Week 6:Correlated Equilibrium, Coarse Correlated Equilibrium, Multiplicative Weight Week 7:No Regret Dynamics, No Swap Regret Week 8:Selfish Routing, Selfish Load Balancing Week 9:Bayesian Games, Extensive Form Games, Mechanism Design Week 10:Gibbard Satterwaite Theorem, Quasi-Linear Environment Week 11:VCG Mechanism, Knapsack Mechanism Week 12:Stable Matching, House Allocation