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.
Introduction To Game Theory And Mechanism Design
This course may be unavailable.
Overview
Syllabus
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
Taught by
Prof. Swaprava Nath
