CS60025 Algorithmic Game Theory

CS60025 Algorithmic Game Theory - Winter 2020

Instructor: Palash Dey

Teaching Assistants: Aditya Anand and Gourab Patro

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.

You can find previous incarnations of this course here.

Prerequisites:
Knowledge of probability theory, discrete mathematics, and algorithm design is required.

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

Grading:
4 Class tests: 50%, 4 Assignments: 20%, 1 Viva (middle of the semester): 15%, 1 Presentation (end of the semester): 15%

Announcements:

Question papers: First class test, Second class test, Third class test, Fourth class test
Student presentation is due on November 8 EOD.
Viva is scheduled on November 16 and 17. The syllabus will be the material covered from October 20 till the end.
Class test 4 is scheduled on November 14 (Saturday) from 9:15 AM. Syllabus is the material covered during October 20 - November 2.
Class test 3 is scheduled on October 31 (Saturday) from 9:15 AM. Syllabus is the material covered during September 22 - October 19.
Class test 2 is scheduled on October 3 (Saturday) from 9:15 AM. Syllabus is the material covered during September 8-21.
Class test 1 is scheduled on September 12 (Saturday) from 9:15 AM. Syllabus is the material covered during September 1-7.
If you have any question in the lecture videos, then ask here
Microsoft Teams link for Monday's tutorial (8:30-9:30 AM): here
Microsoft Teams link for Tuesday's class (12-12:55 PM): here
First class is on September 1, 2020 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	Deadline: September 21
Assignment 2	Deadline: October 5
Assignment 3	Deadline: October 12
Assignment 4	Deadline: November 3
Assignment 5	Deadline: November 15

Lectures: Lecture notes: here

September 1-7	Lec1.1 - Normal Form Game	Reference: Chapters 1-2 in the lecture notes Practice problems: here (Questions 1-12)
	Lec1.2 - Game Theoretic Assumptions
	Lec1.3 - Examples of Normal Form Games
	Lec1.4 - Dominant Strategy Equilibrium
	Lec1.5 - WDSE for Second Price Auction
	Lec1.6 - Nash Equilibrium
September 8-14	Lec 2.1 - Value of Players	Reference: Chapter 3 in the lecture notes Practice problems: here (Questions 13-21) Class lecture
	Lec 2.2 - MinMax Theorem
	Lec 2.3 - Yao's Lemma
September 15-21	Lec 3.1 - Special Games, Support Enumeration Algorithm	Reference: Chapter 4 in the lecture notes Class lecture: part 1,part 2
	Lec 3.2 - Potential Games
	Lec 3.3 - Local Search
September 22-28	Lec 4.1 - Complexity Classes: FNP, TFNP, PPAD	Reference: Chapter 5 in the lecture notes Practice problems: here (Questions 1-6) Class lecture
	Lec 4.2 - Correlated Equilibrium and Coarse Correlated Equilibrium
	Lec 4.3 - Multiplicative Weight
September 29 - October 5	Lec 5.1 - No-Regret Dynamics	Reference: Chapter 5 in the lecture notes Class lecture
	Lec 5.2 - External-Regret to Swap-Regret
October 6-12	Lec 6.1 - Selfish Routing	Reference: Chapter 6 in the lecture notes Practice problems: here (Questions 7 and 8) Class lecture
	Lec 6.2 - Selfish Load Balancing
October 13-19	Lec 7.1 - Bayesian Game	Reference: Chapter 7 in the lecture notes Class lecture
	Lec 7.2 - Extensive Form Game
October 20-26	Lec 8.1 - Mechanism Design Basic	Reference: Chapters 8 and 9 in the lecture notes Practice problems: here Class lecture
	Lec 8.2 - G-S Theorem
October 26 - November 2	Lec 9.1 - Quasilinear Environment	Reference: Chapter 10 (till 10.6) in the lecture notes Practice problems: here (Questions 1-3) Class lecture
	Lec 9.2 - VCG Mechanism
November 2-9	Lec 10.1 - Single Parameter Domain	Reference: Chapters 10 and 11 in the lecture notes Practice problems: here (Questions 4-5) Class lecture
	Lec 10.2 - Knapsack Mechanism
	Lec 10.3 - Stable Matching 1
	Lec 10.4 - Stable Matching 2 and House Allocation
November 10	Doubt clearing session	Class lecture

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