CS60025 Algorithmic Game Theory - Winter 2022

Instructor: Palash Dey

Teaching Assistants: Mayank Raj, Tushar Parshottambhai Punad

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:
Venue: CSE-107. Timing: Monday 8-9:55 AM, Tuesday 12-12:55 PM, Saturday 10-11:30 AM (for tutorial and class test)

Grading:
2 Class tests: 10%, 3 assignments: 10%, Attendance and teacher's evaluation: 10%, Mini project: 10%, Mid-semester: 25%, Final: 35%

Announcements:
Assignments:
Assignment 1 (Programming Assignment) Due date: August 30, 2022
Assignment 2 Due date: September 15, 2022
Submit here


Lectures: Lecture notes: here
August 2 Introduction to Game Theory Practice problems: here
August 8 Game Theoretic Assumptions, Examples of Normal Form Games,
SDSE, WDSE, VWDSE, WDSE for Second Price Auction
August 9 Institute Holiday (Muharram)
August 15 Institute Holiday (Independence Day)
August 16 Nash Equilibrium
August 22 Matrix Games
August 23 Yao's Lemma
August 29 Support Enumeration Algorithm, Succint Games, Potential Games Practice problems: here
August 30 Max-Gain Best Response Dynamics
September 5 Complexity Classes: PLS, FNP, TFNP, PPAD. Sperner's Lemma
September 6 1/2-Additive Approximation Algorithm for MSNE, CE, CCE
September 12 No External Regret Dynamics, MW Algorithm, epsilon-CCE Practice problems: here
September 13 Black-box Reduction from No External Regret to No Swap Regret, epsilon-CE
September 19 Mid-Semester Break
September 20
September 26
September 27
October 3 Institute Holiday
October 4
October 10 Price of Anarchy, Selfish Atomic Routing
October 11 Selfish Load Balancing
October 17 Bayesian Games, First Price Auction, Extensive Form Games
October 18 Mechanism Design, Revelation Principle Practice problems: here
October 24 Institute Holiday (Diwali)
October 25 Properties of Social Choice Function, Gibbard-Satterwaite Theorem
October 31 Quasi-Linear Environment, VCG Mechanism
November 1 Second Class Test


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).