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

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

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.