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