COL866: Special Topics in Algorithms - Algorithmic Game Theory

Announcements Please register yourself on Piazza by clicking here. Use course number as signup code.
LecturesLectures will be held from 3 to 4:30pm in 501 Bharti on the dates specified below.
The first 10 lectures will be discussion sessions where we will clarify any doubts you may have on the corresponding videos. It is therefore very important that you complete the reading and viewing assignment before coming to the lecture.
Tentative Lecture outline with topics
Topics Date Reading/viewing assignment (to be completed before class)
Additional reading
Introduction and Mechanism Design Basics
Jan 7
TRL1, TRL2, Lect 1, 2 from [1]

Myerson's lemma and Algorithmic Mechanism Design. Jan 12
TRL3, TRL4, Lect 3, 4 from [1]

Revenue maximizing auctions, Simple Near-optimal auctions
Jan 19
TRL5, TRL6, Lect 5, 6 from [1]

VCG Mechanism, Spectrum Auctions
Feb 2
TRL7, TRL8, Lect 7, 8 from [1]
Beyond Quasi-linearity, Stable matchings
Feb 4
TRL9, TRL10, Lect 9, 10 from [1]
Selfish routing, Price of Anarchy, Ntwork Over provisioning
Feb 9
TRL11, TRL12, Lect 11, 12 from [1]
Hierarchy of Equilibroum concepts, Smooth Games
Feb 18
TRL13, TRL14, Lect 13, 14  from [1]
Best Case and Strong Nash Equilibria, Best Response Dynamics
Feb 23
TRL15, TRL16, Lect 15, 16 from [1]
No-regret Dynmaics, Swap regret, Minimmax
Mar 8
TRL17, TRL18, Lect 17, 18 from [1]
Pure Nash Equilibrium, PLS-completeness, Mixed NE, PPAD-completeness.
Mar 15
TRL19, TRL20, Lect 19, 20 from [1]
Reading material [1] Lecture Notes by Tim Roughgarden
[2] Algorithmic Game Theory, by Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani (eds.), Cambridge University Press, September 2007.
[3] Linear Programming Duality
Assignments Assignments are to be done individually. Any help taken from outside sources (websites, books) should be clearly mentioned.
Evaluation Assignments (5, each of 6 marks), Midterm (30 marks), Major (40 marks)
Attendance Policy Attendance is compulsory in the lectures.