Algorithmic Game Theory

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

Instructor	Somindu Chaya Ramanna
Teaching assistant	Tadigoppala Sumanth
Classes	THUR: 15:00-16:55; FRI: 15:00-15:55 at CSE-108
	Tutorials on Saturdays

Notices and Announcements

Second Class Test to be held on 7th of November, 2025 during class hour (3 PM to 4 PM) at CSE-108. Syllabus includes everything convered up to week 12 (see coverage below).
First Class Test to be held on 28th of August, 2025 from 3:10 PM (sharp) to 4:10 PM during class hours at CSE-108. Syllabus includes everything convered up to week 4 (see coverage below).
Class on 21st August (Thursday) will be for 1 hour from 3:30 PM to 4:30 PM.
First class will be held on the 24th of July.
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 algorithms. These topics will not be covered in the course.

Evaluation Plan (tentative)

Evaluation for this course will be based on

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

Lectures

Week	Date	Topics Covered
1	24 July	Introduction to Game Theory, Normal Form Games, Examples
1	25 July	Class Cancelled -- Due to heavy rain alert
2	31 July	Dominant Strategy Equilibria (Strong/Weak/Very Weak Dominance), WDSE for Second-Price Auctions, Pure Strategy Nash Equilibria
2	1 August	Mixed Strategy Nash Equilibria (MSNE)
3	7 August	Necessary and Sufficient Conditions for MSNE; Matrix Games: Examples, Saddle Points, PSNE and Saddle Points, Mixed Strategies, Minmaximisation and Maxminimisation
3	8 August	Matrix Games: Optimisation Problems for the 2 Players, Equivalent LPs, Minimax Theorem, Implications on MSNE for Matrix Games (Look at reference no. 6 for an exposition on linear programming)
4	14 August	Max-min Inequality, Yao's Lemma
4	15 August	Institute Holiday (Independence Day)
5	21 August	Support Enumeration Algorithm, Succint Games
5	22 August	Potential Games, PSNE in Potential Games, Best Response Dynamics, Network Congestion Games
6	28 August	Class Test 1
6	29 August	Approximate PSNE, Max Gain Best Response Dynamics
7	4 September	Local Search, PLS, PLS-Completeness, PSNE in Congestion Games
7	5 September	Institute Holiday (Id-E-Milad)
8	11 September	Class Cancelled
8	12 September	PPAD Completeness, Sperner's Lemma, Computing MSNE in Bimatrix Games
	18 - 26 September	Mid-Semester Examination
	27 September - 5 October	Autumn Break
9	9 October	Correlated Equilibria and Coarse-Correlated Equilibria
9	10 October	Approximate CCE, No External Regret Dynamics, Multiplicative Weights Algorithm
10	16 October	Approximate CCE, Swap Regret
10	17 October	Black-box Reduction from No External Regret to No Swap Regret
11	23 October	Price of Anarchy, Selfish Atomic Routing
11	24 October	Selfish Load Balancing
12	30 October	Extensive Form Game,
12	31 October	Bayesian Games, First Price Auction

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

Combinatorial Optimization: Algorithms and Complexity by Christos H. Papadimitriou and Kenneth Steiglitz.

Practice Problems

Problem Set 1

Problem Set 2

Problem Set 3