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 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 (Tentative)

Evaluation for this course will be based on

Class Tests - 20%
Term project (details to be shared later) - 10%
Mid-Semester Examination - 25%
End Semester Examination - 45%

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

Practice Problems

Problem Set 1

Problem Set 2

References

Lecture Notes on Algorithmic Game Theory (CS60025) by Palash Dey (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).