CS60025 Algorithmic Game Theory - Winter 2021


Instructor: Palash Dey

Teaching Assistants: Amatya Sharma

Course overview:
 Game theory is the formal study of interaction between "self-interested" (or "goal-oriented") "systems" (or "agents" or "decision makers" or "players"), and strategic scenarios that arise in such settings. It began life in Economics in the 1940's with the work of von Neumann and Morgenstern, but has since been applied to an extraordinary range of subjects, including political science, evolutionary biology and even to inspection regimes for arms control.

Game theory has for years also played an important, if less recognized, role in several branches of computer science. Applications within computer science include the use of games in automated verification and model checking to model computing systems in an unknown and possibly adverse environment. In AI games are applied to the analysis of multi-agent systems. Recently, with the advent of the internet and e-commerce, many game theoretic questions in the interplay between economics and computing have received extensive attention. These include electronic auctions, and more generally mechanism design questions (inverse game theory) related to finding incentive structures for cooperation between independent entities on the internet.

Wherever game theory plays a quantitative role, algorithmic and computational questions related to "solving" games are also of central importance. This course discusses algorithmic aspects of game-theoretic models, with a focus on recent algorithmic and mathematical developments.

This is mainly a subject blonging broadly to theoretical computer science. You can find previous incarnations of this course here.


Prerequisites:
 Knowledge of probability theory, discrete mathematics, algorithm design, and an overall inclination towards theory are required.

Classes:
Monday 8-9:55 AM, Tuesday 12-12:55 PM, Saturday 10-11:30 AM

Grading:
4 Class tests: 60%, 4 Assignments: 20%, 1 Presentation (end of the semester): 10%, Class Participation and Attendance: 10%

Announcements: Assignments:
Assignment 1 (Programming Assignment) Due date: September 5, 2021
Assignment 2 Due date: September 18, 2021
Assignment 3 Due date: October 20, 2021
Assignment 4 Due date: November 9, 2021


Lectures: Lecture notes: here
August 11 Normal Form Game Reference: Chapters 1-2 in the lecture notes

Practice problems: here (Questions 1-12)
Class recording
August 16 Game Theoretic Assumptions
Examples of Normal Form Games
Dominant Strategy Equilibrium
WDSE for Second Price Auction
August 17 Nash Equilibrium
August 21 Tutorial
August 23 Value of Players Reference: Chapter 3 in the lecture notes
Practice problems: here (Questions 13-21)
MinMax Theorem
August 24
August 28First Class Test Question paper: part 1, part 2; Sample Solution
August 30 Yao's Lemma Reference: Chapter 3 in the lecture notes
Special Games, Support Enumeration Algorithm Reference: Chapter 4 in the lecture notes

Practice problems: here
August 31
September 6 Potential Games
September 7 Local Search
September 13 Complexity Classes: FNP, TFNP, PPAD
September 18 Tutorial
September 20 Correlated Equilibrium and Coarse Correlated Equilibrium Reference: Chapter 5 in the lecture notes

Practice problems: here
September 21 Multiplicative Weight
September 25Second Class Test Question paper: part 1, part 2; Sample Solution
September 27 No-Regret Dynamics Reference: Chapter 5 in the lecture notes
September 28 External-Regret to Swap-Regret
October 2 Tutorial
October 4 Selfish Routing Reference: Chapter 6 in the lecture notes
Selfish Load Balancing
October 5 Bayesian Game Reference: Chapter 7 in the lecture notes
October 9 No Tutorial
October 11 Extensive Form Game Reference: Chapter 7 in the lecture notes
Mechanism Design Basic Reference: Chapter 8 in the lecture notes
October 12 No Class (Institute holiday)
October 17 No Tutorial (Autumn break for students)
October 18 G-S Theorem Reference: Chapter 9 in the lecture notes
October 19 No Class (Institute holiday)
October 23Third Class Test Question paper: part 1, part 2; Sample Solution
October 25 Quasilinear Environment Reference: Chapter 10 in the lecture notes

Practice problems: here (Questions 1-3)
VCG Mechanism
October 26 Single Parameter Domain
October 30 Tutorial
November 1 Knapsack Mechanism Reference: Chapter 10 in the lecture notes
Stable Matching Reference: Chapter 11 in the lecture notes
November 2 Stable Matching
November 6 Tutorial
November 8 House Allocation Reference: Chapter 11 in the lecture notes
November 13 Fourth Class Test Question paper: part 1, part 2; Sample Solution
References:
  1. Nisan/Roughgarden/Tardos/Vazirani (eds), Algorithmic Game Theory, Cambridge University, 2007 (available for free from here).
  2. Game Theory by Michael Maschler, Eilon Solan, and Shmuel Zamir.
  3. Game Theory and Mechanism Design by Y. Narahari (equivalent lecture notes are available here).