CS60025 Algorithmic Game Theory

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:

Deadline for course project submission is November 20. You need to submit 5 things: (i) video of the presentation, (ii) slides of the presentation, (iii) source code, (iv) a readme.txt file clearly explaining how to compile and execute your code, and (v) name and roll number of group members. Share a folder containing these on Google Drive. Use "anyone with the link can view" to share in Google Drive so that we do not need to log-in or provide any password to download your submission. It is enough for only one person per group to submit.
Fourth class test is scheduled on November 13 (Saturday) from 10 AM. The test will be conducted in CSE Moodle.
Third class test is scheduled on October 23 (Saturday) from 10 AM. The test will be conducted in CSE Moodle.
Second class test is scheduled on September 25 (Saturday) from 10 AM. The test will be conducted in CSE Moodle.
First class test is scheduled on August 28 (Saturday) from 10 AM. The test will be conducted in CSE Moodle.
First class is on August 10, 2021 at 12 PM. Join the course Google group to receive meeting details.
Click here to join the course Google group. All announcements will be posted here. Write your name and roll number in the membership request message.

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)
August 23	MinMax Theorem
August 24	MinMax Theorem
August 28	First Class Test	Question paper: part 1, part 2; Sample Solution
August 30	Yao's Lemma	Reference: Chapter 3 in the lecture notes
August 30	Special Games, Support Enumeration Algorithm	Reference: Chapter 4 in the lecture notes Practice problems: here
August 31	Special Games, Support Enumeration Algorithm
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 25	Second 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	Reference: Chapter 5 in the lecture notes
October 2	Tutorial
October 4	Selfish Routing	Reference: Chapter 6 in the lecture notes
October 4	Selfish Load Balancing	Reference: Chapter 6 in the lecture notes
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
October 11	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 23	Third 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)
October 25	VCG Mechanism
October 26	Single Parameter Domain
October 30	Tutorial
November 1	Knapsack Mechanism	Reference: Chapter 10 in the lecture notes
November 1	Stable Matching	Reference: Chapter 11 in the lecture notes
November 2	Stable Matching	Reference: Chapter 11 in the lecture notes
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:

Nisan/Roughgarden/Tardos/Vazirani (eds), Algorithmic Game Theory, Cambridge University, 2007 (available for free from here).
Game Theory by Michael Maschler, Eilon Solan, and Shmuel Zamir.
Game Theory and Mechanism Design by Y. Narahari (equivalent lecture notes are available here).