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.