Algorithmic Game Theory

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.

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

Evaluation for this course will be based on

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

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 and Mechanism Design by Y. Narahari (equivalent lecture notes are available here).

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