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
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

Auctions and Optimal Mechanism Design, Myerson's lemma, VCG auctions
Jan 21, 24, 28, 31,
Feb 11, 15
Notes lec6

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.