COMP/MATH 553: Algorithmic Game Theory
Fall 2014
Course Information
- Instructor: Yang Cai
Office Hours: Wednesday after class.
- TA: Faizy Ahsan
Office Hours: Tuesday 4pm-5pm, MC 106 (faizy dot ahsan at mail dot mcgill dot ca)
- Lecture: Mondays and Wednesdays 4:05 pm-5:25 pm, Rutherford Physics Building 118.
- Course Description: Broad survey of topics at the interface of theoretical computer science and economics, with an emphasis on algorithms and computational complexity. Our main focus will be on algorithmic tools in mechanism design, algorithms and complexity theory for learning and computing Nash and market equilibria, and the price of anarchy. Case studies in Web search auctions, wireless spectrum auctions, matching markets, and network routing, and social networks.
- Textbook: Algorithmic Game Theory, by Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani (eds.), Cambridge University Press, September 2007.
- Lecture Notes: Lecture notes and/or presentations will be provided.
- Prerequisites: A course in algorithms (COMP 360 or equivalent) and probability (MATH 323 or equivalent).
No prior knowledge of Economics or Game Theory is required.
- Assessment: The grade comprises the following components (which may sum to more than 100%):
- 5% from games played in class; will play a few games with your classmates in class, and your score depends on your performance in these games.
- 15% from scribing a lecture; in a team of two or three students.
- 40% from homework problems; there will be 3-4 problem sets.
- 40% from the final exam or the final project (you can choose either one, or do both). The project could either be a survey, or original research; students will be encouraged to relate the project to their own research interests.
Course Outline
There is a significant dynamic component to the course, as topics drop
in and out, or get longer or shorter treatment, depending on audience
interest/reaction/resistence. We consider this a feature. Given this,
here is a rough outline of the
course material.
Homework
Please use the
scribe template to produce your notes. The template contains commands for Theorem, Lemma, Corollary, Proposition, Claim, Definition, Construction, Remark etc. An example file where this template is used is
here. As scribes become available, they will be published here. At the same time, the list below will contain notes/presentations produced by the instructor.
- Lecture 1 (Sept 4th): Introduction to Algorithmic Game Theory: Incentives in Large Systems; Games; Nash Equilibria and their computation; the Price of Anarchy; Mechanism Design. Slides.
Online Resources
Previous incarnation of this class:
Similar Classes in other universities:
Other reference books: