
CSL863:
Special Topics in Theoretical Computer Science  Algorithmic Game Theory

Announcements 
Major exams (for graduating students only) will be on June 27 (10am1pm) at your homes. 
Tentative Lecture
outline with topics 
Topics 
Date 
Reading
material 
Scribes

Introduction
to Algorithmic Game Theory 
Dec
31

Slides 

Definitions
of Games and Equilibria; Two player ZeroSum Games; Proof of
Nash
Equilibria using Linear Programming Duality. 
Jan
3, 7, 10, 14, 17

Notes 
lec1
lec2
lec3
lec4
lec5

Auctions
and Optimal
Mechanism Design, Myerson's lemma, VCG auctions

Jan
21, 24, 28, 31,
Feb 11, 15

Notes 
lec6
lec7
lec8
lec9
lec10
lec11

Price
of
Anarchy in network routing games, Atomic routing games, Potential
function games 
Feb
18, 25
Mar 2, 6

Notes1,
Notes2,
Notes3,
Notes4,
Notes5, Notes6 
lec12
(wrongly marked lec 11)
lec13.1,
lec13.2
lec14.1,
lec14.2

Classes Suspended due to CoViD19




Hierarchy of Equilibria, Bestcase and strong Nash
Equilibria, Bestresponse dynamics and noregret dynamics, Pure nash
equilibria and PLScompleteness


Chapters 1319 from Tim Roughgarden's notes.
Watch corresponding videos


Arrow's and
GibbardSatherthwaite thms


Chapter 9 of
Nisan et.al.



Supplementary reading
materials 
Algorithmic
Game
Theory, by Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V.
Vazirani (eds.), Cambridge University Press, September 2007.
Linear Programming Duality
Tim
Roughgarden notes

Other Courses

Tim Roughgarden
Constantinos
Daskalakis
Eva
Tardos
Jason
Hartline

Assignments 
Assignments are to
be done individually. Any help taken from outside sources (websites,
books) should be clearly mentioned. 
Evaluation 
Assignments (2,
each of 10 marks), Midterm (25 marks), Major (35 marks), Lecture Quiz
(5 marks), Scribe (15 marks)
Assignment (10 marks), Midterm (25 marks), Major (35 marks), Scribe (15 marks).

Lecture Scribes

Signup
here
for choosing a scribe date. Use this
latex template for scribes.
Scribes should be mailed within a week of the lecture. Those
who could not scribe a lecture
will instead write a short report (34 pages) on a gametheory topic of
their
choice which has not been done in class. You can consult the book by
Nisan et.al. for possible topics. Report should be submitted by June 30. 
Attendance Policy 
Attendance is
compulsory in the lectures. 