Algorithmic Game Theory

CS60025, Autumn 2024, LTP: 3-0-0

Instructor	Somindu Chaya Ramanna
Teaching assistant	Umika Agrawal
Class Slots	THUR: 15:00-16:55; FRI: 15:00-15:55
	Tutorials on Saturdays

Notices and Announcements

Class Test 2 will be held on Wednesday, the 14th of November, 2024 from 3 PM to 4 PM
Class Test 1 will be held on 3rd September, 2024 from 6 PM to 7 PM at CSE-106
Approval for joining the couse will be based on CGPA. Those who are not familiar with the course prerequisites (mentioned below) are strongly discouraged from joining this course.

Prerequisites

I assume familiarity with probability theory, discrete mathematics and algorithm design. These topics will not be covered in the course.

Evaluation Plan

Evaluation for this course will be based on

Class Tests - 20%
Mid-Semester Examination - 30%
End Semester Examination - 50%

Lectures

Week	Date	Topics
1	25 July	Introduction to Non-Cooperative Game Theory, Normal Form Games, Examples
1	26 July	Solution Concepts: Dominant Strategy Equilibria; Strong/Weak/Very Weak Dominance, WDSE for Second-Price Auctions
2	1 August	Nash Equilibrium: PSNE, MSNE, Examples
2	2 August	Necessary and Sufficient Condition for MSNE
3	8 August	Matrix Games: Examples, Saddle Points, PSNE and Saddle Points, Mixed Strategies, Minmaximisation and Maxminimisation
3	9 August	Matrix Games: Optimisation Problems for the 2 Players, Equivalent LPs, Minimax Theorem, Implications on MSNE for Matrix Games
4	15 August	Institute Holiday (Independence Day)
4	16 August	Yao's Lemma
5	22 August	Support Enumeration Algorithm, Succint Games, Potential Games
5	23 August	PSNE in Potential Games, Best Response Dynamics
6	29 August	Approximate PSNE, Max Gain Best Response Dynamics
6	30 August	Local Search, PLS, PLS-Completeness
7	5 September	No Class
7	6 September	No Class
8	12 September	MSNE in Bimatrix Games, Classes FNP,TFNP,PPAD
8	13 September	PPAD Completeness, Sperner's Lemma
	17 - 25 September	Mid-Semester Examination
9	26 September	Correlated Equilibria and Coarse-Correlated Equilibria
9	27 September	No External Regret Dynamics, MW Algorithm
10	3 October	Approximate CCE, Swap Regret
10	4 October	No Class
	5 - 13 October	Autumn Break
11	17 October	No Class
11	18 October	Black-box Reduction from No External Regret to No Swap Regret, epsilon-CE
12	24 October	Price of Anarchy, Selfish Atomic Routing
12	25 October	No Class -- Cyclone Dana
13	31 October	Institute Holiday (Deepavali)
13	1 November	Selfish Load Balancing
14	7 November	Extensive Form Games
	8 November	Bayesian Games, First Price Auction
	9 November	Doubt-Clearing Session
12	14 November	Class Test
12	15 November	Institute Holiday (Gurunanak Jayanti)
	18 - 26 November	End Semester Examination

Practice Problems

Problem Set 1

Problem Set 2

Problem Set 3

References

Lecture Notes on Algorithmic Game Theory (CS60025) by Palash Dey (available here).

Course on Algorithmic Game Theory -- Lecture Notes by Tim Roughgarden (available here).

Algorithmic Game Theory, Edited by Nisan, Roughgarden, Tardos and Vazirani, Cambridge University Press, 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).