Course Detail: Game Theory and Algorithmic Mechanism Design
Course number CS6001, Offered in CSE, IIT Bombay
Instructor: Dr. Swaprava Nath
The proposed course is primarily a course on Algorithmic Mechanism Design, which is the ‘reverse engineering’ of Game Theory. Mechanism design starts with certain objectives (also called social goals) in a multi-agent strategic environment and shows possibilities (or impossibilities) of certain sets of social goals. Then it also asks algorithmic questions of how to achieve those achievable goals in a computationally efficient way, and if those goals were impossible, how to achieve them in some approximate way. This is where this course differs significantly from the current game theory courses offered in the institute.
To make the course self-contained, the initial part of the course discusses game theory, which is to build the background for the mechanism design part of this course, and thus has ‘game theory’ in the title. This course will be useful for all students who want to learn an essential tool to mathematically model, analyze, and provide provable guarantees in strategic environments and apply them in multi-agent environments like sponsored search auctions, resource allocation, crowdsourcing, social networks, internet-based trade, and several similar settings. The course will be useful for a large set of audience – a representative set of the academic audience will be from (but not limited to) Economics, Mathematics, Operations Research, Management Science, Electrical Engineering, in addition to Computer Science.
Mathematics, IEOR, Electrical Engineering, HSS (Economics), Management Science (SJMSOM)
Desired background for taking the course: familiarity with formal mathematical reasoning, probability theory, calculus, basics of computational complexity, and (soft constraint) familiarity with computer programming.
A tentative list of topics are as follows.
• Non-cooperative game theory – foundation for discussing mechanism design
◦ Quantitative models of strategic interaction: rationality, intelligence, common knowledge
◦ Complete information simultaneous move games – normal form representation
▪ Ideas of equilibria: domination of strategies, Nash equilibrium
▪ Existence results for mixed and pure Nash equilibrium
▪ Complexity of computing Nash equilibrium
▪ Correlated equilibrium.
◦ Complete information sequential move games – extensive form representation
▪ Perfect and imperfect information extensive form games
▪ Equilibria concepts – subgame perfect equilibrium, perfect Bayesian equilibrium, analogies with pure and mixed Nash equilibrium
◦ Incomplete information games
▪ Bayesian games
▪ Equilibria concepts tied to the belief system
▪ Nash and Bayesian equilibria in incomplete information games
• Introduction to mechanism design
◦ Incomplete information to player types
◦ Social welfare function, Arrow’s impossibility result
◦ Social choice function, Gibbard-Satterthwaite result
◦ Domain restriction
◦ Single-peaked preferences
◦ Task allocation domain
◦ Quasi-linear preferences
• Some real world applications of mechanism design
No specific textbook. However, the following books and lecture notes may be useful.