CSL863: Special Topics in Theoretical Computer Science - Algorithmic Game Theory

Announcements Major exams (for graduating students only) will be on June 27 (10am-1pm) 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 Zero-Sum 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 CoViD-19

Hierarchy of Equilibria, Best-case and strong Nash Equilibria, Best-response dynamics and no-regret dynamics, Pure nash equilibria and PLS-completeness

Chapters 13-19 from Tim Roughgarden's notes. Watch corresponding videos


Arrow's and Gibbard-Satherthwaite 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 (3-4 pages) on a game-theory 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.