AI 5040: Game Theory and Mechanism Design

Course Information: 

Game theory is a mathematical framework to analyze the outcome of the interaction between self-interested agents (either one time or over multiple rounds).  In this course, we will study different situations where agents compete (non-cooperative game theory)  or cooperate (cooperative game theory) to obtain their objectives.  We will also study mechanism design, a prescriptive approach, where one can set the rules of the game (strategic environment) to obtain the desired objective resulting from strategic interactions following these rules.   The students will be exposed to various tools, ideas and solution concepts in game theory to reason about various multi-agent settings. 

Instructor:
Dr. Ganesh Ghalme,
Room 112 -D, C block, IITH.

Class timing/Location:
B-105,  Monday 16:00- 17:25 , Thursday 14:30- 15:55

Note: Classes will be completely offline unless some unforeseen events force us to go to the online model.

Syllabus (tentative):
Module 1 (Non-cooperative game theory): private, public and common knowledge, extensive form games and strategic form games, zero-sum and  non-zero-sum matrix  games, Von-Neumann's minimax theorem, subgame perfect equilibria, Dominant strategy equilibria, mixed strategy equilibria, Nash's theorem, bargaining  games
Module 2 (Cooperative game theory): Correlated equilibria, coalitional games with transferable utility, the core, Shapley value, nucleolus
Module 3 (Mechanism Design): Social choice theory, Arrows impossibility theorem, Gibbard-Satterthwaite theorem, VCG mechanisms, Revenue maximizing auctions and Myerson's result, BIC mechanisms
Module 4 (Applications*): House allocation, fair division, routing games and price of anarchy, sponsored search auctions

*time permitting.

  Text/References: 

Below is a partial list of references. I will not follow any one book end-to-end. 

1. Game Theory, Alive by Anna Karlin and Yuval Peres ( free online copy available here)

2. Game Theory and Mechanism Design (lecture notes available here)

3. Algorithmic Game Theory by  N. Nisan, T. Roughgarden, E. Tardos, V. Vazirani (Online version available here)

4. Game Theory  by Michael Maschler, Eilon Solan and Schmuel Zamir 

5. Game Theory by Drew Fudenberg and Jean Tirole 

Prerequisites: 

There are no prerequisites for the course. However, familiarity with applied probability, convex optimization and real analysis will be useful.

   TAs: to be announced soon.

Evaluation:

1. Mini project/Reading exercise:  20% 

2. Two mid-term exams: 20% each 

3. Final Exam: 40%