Algorithmic Game Theory

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

Instructor	Somindu Chaya Ramanna
Teaching assistant	Golla Meghanandh Manvith Prabhash
Classes	THUR: 15:00-16:55; FRI: 15:00-15:55 at CSE-302
	Tutorials on Saturdays

Notices and Announcements

Class Test 1 is scheduled on 3 September from 3 PM to 4 PM in CSE-302 and CSE-119. Here is the seating plan. Syllabus includes everything covered up to Week 5.
First quiz to be held on 14 August at 2:30 PM in the classroom.
I will take the first class on the 23rd of July.
Approval for joining the course 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. No prior knowledge of game theory is required.

Evaluation Plan (tentative)

Teacher's Assessment	40% [30% Class Tests/Quizzes + 10% Attendance]
Mid-Semester Examination	30%
End Semester Examination	30%

Lectures

Week	Date	Topics Covered
1	23 July	Introduction to Game Theory, Normal Form Games, Examples
1	24 July	Dominant Strategy Equilibria (Strong/Weak/Very Weak Dominance), WDSE for Second-Price Auctions
2	30 July	Nash Equilibrium: PSNE, MSNE, Examples Necessary and Sufficient Condition for MSNE
2	31 July	Matrix Games: Examples, Saddle Points, PSNE and Saddle Points Mixed Strategies, Minmaximisation and Maxminimisation
3	6 August	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)
3	7 August	Application of the max-min inequality for matrix games: Yao's Lemma
4	13 August	Support Enumeration Algorithm, Succint Games
4	14 August	Quiz 1 Potential Games, PSNE in Potential Games, Best Response Dynamics
5	20 August	Approximate PSNE, Max Gain Best Response Dynamics
5	21 August	Polynomial Local Search (PLS), PLS-Completeness Finding PSNE for Congestion Games is PLS-Complete
6	27 August	MSNE in Bimatrix Games, FNP, TFNP, PPAD, PPAD-Completeness Sperner's Lemma
6	28 August	Correlated Equilibria and Coarse-Correlated Equilibria
7	3 September	Class Test 1
7	4 September	Institute Holiday (Janmashtami)

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.

Solutions for Tests/Exams

Quiz 1

Practice Problems

Problem Set 1 (Tutorial on 8 August)

Problem Set 2 (Tutorial on 28 August)