Announcements


  • (Nov 6): Assignment 1 is now graded on MarkUs. Please submit any remark requests through MarkUs by November 11, 11:59PM.
  • (Nov 5): During the reading week, Monday 4pm-5pm office hours would be shifted to Wednesday 4pm-5pm. Office hours on Thursday 1pm-2pm would continue as usual.
  • (Nov 2): There will be NO tutorial today.
  • (Oct 25): Midterm 2 will be on November 16 (Friday) during the tutorial slot (3pm-4pm) in the tutorial rooms (BA 1200 and BA 1220).
  • (Oct 25): Midterm 1 has been graded. If you haven't already, you can collect your midterm after the class. Please also make sure that your midterm 1 marks are reflected accurately on MarkUs.
  • (Oct 11): The second practice problem set is posted.
  • (Oct 10): In the first midterm, you will be allowed to bring ONE TWO-SIDED 8.5" X 11" SHEET OF HANDWRITTEN NOTES. No other aids are permitted (e.g., calculator).
  • (Oct 4): The first midterm will be held on Friday, Oct 19 during the tutorial slot (3pm-4pm) in the tutorial rooms (BA 1200 and BA 1220).
  • (Oct 4): The first assignment has been posted. It is due on Monday, Oct 15, by 3pm. Please submit your solution as a single PDF on MarkUs.
  • (Sep 24) : Today's lecture will be a guest lecture by Prof. Allan Borodin. On Wednesday (9/26), there is no lecture. Solutions to the first practice problem set have been posted here. Please attempt the problems yourself before looking at the solution. The solutions will be discussed in the tutorial on Friday (9/28).
  • (Sep 20) : The first practice problem set is posted.
  • (Sep 10) : There will be *no tutorial on Sep 14*.
  • (Sep 11) : Office hours will be held on Mondays 4pm-5pm and Thursdays 1pm-2pm in the instructor's office (SF 2301C).

Important Information


Lectures: Mon-Wed, 3pm-4pm, MP 134

Tutorials: Fri, 3pm-4pm
     Tutorial A (birth month: Jan-Jun) BA 1220
     Tutorial B (birth month: Jul-Dec) BA 1200

Instructor: Nisarg Shah (SF 2301C, nisarg@cs.toronto.edu)

TAs: Deeksha Adil (deeksha@cs.toronto.edu), Paraskevi (Evi) Micha (emicha@cs.toronto.edu), Tyrone Strangway (tyrone@cs.toronto.edu)

Instructor Office Hours: Mon 4pm-5pm, Thu 1pm-2pm, SF 2301C

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. Username and password to access the page will be emailed to you.

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 course information sheet.