Important Information
Time & Location: Mon-Wed, 3p-4p, BA 1230
Instructor: Nisarg Shah (SF 2301C, nisarg@cs.toronto.edu, 416-946-8477)
Occasional guest lectures by Prof. Allan Borodin
Office hours: Fri, 3p-4p, SF 2202
Teaching Assistant: Tyrone Strangway (tyrone@cs.toronto.edu), Andrew Perrault (perrault@cs.toronto.edu)
Course Page: This page!
Discussion Board: Piazza
Online Homework Submission: MarkUs
Overview
This is a relatively new interdisciplinary course that introduces students from computer science and related disciplines to the well established fields of algorithmic game theory and mechanism design. These fields sit at the interface between computer science and economics, and have recently seen a growing number of real-world applications. This course will review the basic models and core theoretical insights that have been instrumental in the development of these fields. The course will be organized in three parts: game theory, mechanism design with money, and mechanism design without money. In particular, it will cover (possibly a subset of) the following topics:
- Game theory: Nash equilibria, Price of anarchy (PoA), congestion games and Braess paradox, zero-sum games and the minimax theorem, Stackelberg equilibrium and security games, and equilibria computation.
- Mechanism design with money: Bayes-Nash equilibria, dominant strategy equilibria, the revelation principle, VCG auction, Myerson's auction, 1st and 2nd price auctions, the revenue equivalence theorem, greedy approximation algorithms.
- Mechanism/algorithm design without money: facility location, matching markets, social choice theory --- axiomatic, statistical, and utilitarian approaches, Arrow's and Gibbard-Satterthwaite impossibility, fair division of divisible and indivisible goods.
Textbook
Primary reference: Economics and Computation by David C. Parkes and Sven Seuken. The book is under development, so you are advised to not share any part of the book publicly. Please send any feedback to nisarg@cs.toronto.edu, and add "[PS-Book]" to the subject line.
The book can be accessed from here. Email me for the username and password.
Other useful reference books:
- Game Theory, Alive by Anna Karlin and Yuval Peres. Online Version
- Algorithmic Game Theory edited by Noam Nisan, Tom Roughgarden, Eva Tardos and Vijay Vazirani. Online Version
- Handbook of Computational Social Choice edited by Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia. Online Version
- Introduction to Game Theory by Martin Osborne. Online Version
- Networks, Crowds and Markets by David Easley and Jon Kleinberg. Online Version
Related courses with excellent notes/slides:
- Tim Roughgarden's notes on Algorithmic Game Theory
- Ariel Procaccia's slides on Truth, Justice, and Algorithms
For information about homeworks, exams, grading, and policies, refer to the handout that will be distributed in the first lecture.