Outline
This course is an introduction to Algorithmic Game Theory (AGT).
Notes
Usually, I will not provide any notes. The following table gives a preliminary schedule of the course. Actually, I expect that we will have to drop a few topics at the end.
| Topic | Date(s) covered | Slides |
|---|---|---|
| Introduction | Sep 18 | Introduction |
| Ch. 17: Inefficiency of equilibria, and Ch. 18: Network routing games | Sep 25, Oct 16 | |
| Ch. 19: Network design games | Oct 23, 30 | |
| Ch. 9: Mechanism design | Oct 30, Nov 6, 13, 20 | |
| Ch. 10: Stable matching and house allocation | Dec 4, 11, 24 | |
| Ch. 2: The complexity of finding Nash equilibria | Dec 25 | |
| Final exam | Jan 15, 9-11 | |
Textbook
This course will use material from the following book, which Fudan students can download here.
- Algorithmic Game Theory, by Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani, Cambridge University Press 2008.
- Errata of the first edition of the textbook.
Some Related Materials:
Blocked pages may be accessed via Proxin proxy server.- Game theory lecture notes on GameTheory.net.
- Noam Nisan's CGT Blog. Here you can find many interesting new developments in AGT.
- Tim Roughgarden's Algorithmic Game Theory Primer.
Evaluation
Course Project
Instead of a midterm exam, we will have a course project. Your task is to write a report on where game theory appears in your daily life. That is, you should identify one or several real life situations that can be modeled as games, and try to analyze them using the techniques you will learn in the course, for example, computing Nash equilibria, the price of anarchy, mechanism design to guarantee a socially more acceptable outcome, etc. Simple examples would be the course registration system at Fudan where many students compete for courses with capacity restrictions, or the monthly car license plate auction in Shanghai. Your report must be submitted before Dec 30 in electronic form (pdf). You should work in teams of 3-4 students.Exams
There will be one exam in this course, the final exam. You need at least 50% of the points to pass the exam. The exam will be closed book, no cheat sheet will be allowed. The exam is worth 50% of the final mark.
Final Grade
I reserve the right, where appropriate, to adjust raw marks downward in the case of cheating and upward in other situations. The following table shows hows to calculate your final grade from your raw marks.
|
|
|
Policies
Grade Adjustments
Note that university regulations require that if a student completes an exam, the grade in the course (in particular, a failing grade) will not be changed, even if the student subsequently claims that his/her performance was affected by illness or other personal problems and submits documentation.
Students who fail a course sometimes ask the instructor if they can write another exam or do some extra work in order to raise their mark. We do not offer supplementary exams or other ad-hoc methods of raising marks.