Introduction To Game Theory And Mechanism Design

ABOUT THE COURSE:This course is an introduction to game theory and mechanism design. The goal is to equip students with a general purpose tool to analyze strategic behavior in multi-agent interaction. Though primarily a topic of economic flavor, it has significant applications in the decision process of a multi-agent environment like sponsored advertisements, crowdsourcing, social media, internet-based trade, and several settings of social choice and welfare. This course is a backend of such applications and discusses the mathematical details of analyzing and designing strategic interactions.INTENDED AUDIENCE:Pre-final and final year undergraduates, early graduate studentsPREREQUISITES :Familiarity with formal mathematical reasoning, probability theory, calculus,basics of computational complexity, and (soft constraint) familiarity with computer programming.INDUSTRY SUPPORT :Management wing of any company that is interested in mathematical handling of strategic planning will have interest in this course.

Week 1: Introduction, the game of chess, proof of chess theorem, normal form games Week 2:Dominance, Nash equilibrium, Maxmin strategies, elimination of dominated strategies, preservation of pure Nash equilibrium (PSNE), matrix games, relation between maxmin and PSNE in matrix games Week 3:Mixed strategies, mixed strategy Nash equilibrium (MSNE), finding MSNE, MSNE characterization theorem, algorithm to find MSNE Week 4:Correlated equilibrium (CE), computing CE, extensive form games, subgame perfection, limitations of subgame perfect Nash equilibrium Week 5:Imperfect information extensive form games (IIEFG), strategies in IIEFGs, equivalence of strategies in IIEFGs, perfect recall Week 6:Equilibrium in IIEFG, game theory in practice: P2P file sharing, Bayesian games, strategy and utility in Bayesian games, equilibrium in Bayesian games Week 7:Introduction to mechanism design, revelation principle, introduction and proof of Arrow’s impossibility result, introduction to social choice setup Week 1:Introduction and proof of Gibbard-Satterthwaite theorem, domain restriction, median voter theorem Week 9:Task sharing domain, uniform rule, mechanism design with transfers, examples of quasi-linear preferences, Pareto optimality and Groves payments Week 10:Introduction to VCG mechanism, VCG in Combinatorial allocations, applications to Internet advertising, slot allocation and payments in position auctions, pros and cons of VCG mechanism Week 11:Affine maximizers, single object allocation, Myerson’s lemma, optimal mechanism design Week 12:Single and multi-agent optimal mechanism design, examples of optimal mechanisms