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

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

Lectures

Week Date Topics Covered
1 24 July Introduction to Game Theory, Normal Form Games, Examples
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
1 August Mixed Strategy Nash Equilibria (MSNE)
3 8 August Necessary and Sufficient Conditions for MSNE;
Matrix Games: Examples, Saddle Points, PSNE and Saddle Points, Mixed Strategies, Minmaximisation and Maxminimisation
9 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)

References

  1. Lecture Notes on Algorithmic Game Theory (CS60025) by Palash Dey (available here).

  2. Course on Algorithmic Game Theory -- Lecture Notes by Tim Roughgarden (available here).

  3. Algorithmic Game Theory, Edited by Nisan, Roughgarden, Tardos and Vazirani, Cambridge University Press, 2007 (available for free from here).

  4. Game Theory by Michael Maschler, Eilon Solan, and Shmuel Zamir.

  5. Game Theory and Mechanism Design by Y. Narahari (equivalent lecture notes are available here).

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