CS 711: Introduction to Game Theory and Mechanism Design

Units: 3-0-0-0 (9)

Pre-requisites:

Familiarity with formal mathematical reasoning, probability theory, calculus, basics of computational complexity, and computer programming.

Description

This course is an introduction to classical game theoretic ideas and results with the aim to design mechanisms that satisfy desirable axioms. The course will introduce ideas of rationality and intelligence, cover non-cooperative games (including complete information simultaneous move and sequential games, and later incomplete information games), cooperative games (ideas of coalition, core, Shapley value, neucleolus etc), and introduce mechanism design framework (social choice and welfare functions, Arrow’s impossibility result, unrestricted preferences and Gibbard-Satterthwaite result, domain restriction: single-peaked, task allocation domains, quasi-linear preferences), and demonstrate applications of these ideas in practice.

A tentative list of topics are as follows.

1. Non-cooperative game theory
   1. Quantitative models of strategic interaction: rationality, intelligence, common knowledge
   2. Complete information simultaneous move games – normal form representation
      1. Ideas of equilibria: domination of strategies, Nash equilibrium
      2. Existence results for mixed and pure Nash equilibrium
      3. Correlated equilibrium.
   3. Complete information sequential move games – extensive form representation
      1. Perfect and imperfect information extensive form games
      2. Equilibria concepts – subgame perfect equilibrium, perfect Bayesian equilibrium, analogies with pure and mixed Nash equilibrium
   4. Incomplete information games
      1. Bayesian games
      2. Equilibria concepts tied to the belief system
      3. Nash and Bayesian equilibria in incomplete information games
   5. Cooperative Game Theory
      1. Utility representation in form of coalition
      2. Transferable utilities game
         1. Imputation, core, Shapley value, nucleolus
   6. Introduction to mechanism design
      1. Incomplete information to player types
      2. Social welfare function, Arrow’s impossibility result
      3. Social choice function, Gibbard-Satterthwaite result
      4. Domain restriction
      5. Single-peaked preferences
      6. Task allocation domain
      7. Quasi-linear preferences
   7. Some real world applications of mechanism design

   References

   No specific textbook. However, the following books and lecture notes may be useful.

   1. Yoav Shoham and Kevin Leyton-Brown: Multiagent Systems (www.masfoundations.org)
   2. Martin Osborne: An Introduction to Game Theory
   3. Y. Narahari: Game Theory and Mechanism Design
   4. Debasis Mishra
      1. Game Theory course notes: http://www.isid.ac.in/~dmishra/gm1doc/notes_2016.pdf
      2. Mechanism Design course notes: http://www.isid.ac.in/~dmishra/gmdoc/mdnotes.pdf

Note: This course has some content overlap with CS656 and CS785. However, the proposed course provides a view of the evolution of the ideas in non-cooperative games – it differs particularly in the areas of sequential games and their equilibria concepts. It also covers cooperative games. On the mechanism design front, it provides a panoramic view of different domains of social choice and welfare that helps distinguish the advantages and limitations of these domains.