Announcements


  • Assignment 3 is posted. It is due on Dec 2 by 3pm. Remember that you can use any remaining late days (max 2) towards this assignment.
  • As announced in the class, Midterm 2 will be on Monday, Nov 18 during the tutorial slot (3:10-4pm), in your usual tutorial room (GB 248 for birth month Jan-Jun, and LM 155 otherwise). The syllabus will be mechanism design (VCG to Myerson). As always, you will be allowed to bring one 8.5"x11" sheet of handwritten notes on one side.
  • Midterm 1 marks are now available on MarkUs. Exam papers will be distributed in today's class, Friday's class, and Friday's office hours. For any remark request, it would be best to approach me during the office hours on Friday. But if that is not possible, email me with your availability this or next week.
  • Assignment 2 is released. It is due by 3pm on Nov 9. Remember that the number of late days you can use towards this assignment is max(2,your remaining late days).
  • Here are a few selected problems from the "Game Theory, Alive" book (link provided below), which can be solved using what you've learned in the course. Easier exercises: 4.2, 4.3, 4.6, 4.13. Harder exercises: 4.5, 4.7.
  • You no longer need to solve Q4 from Assignment 1, as it was mistakenly included in Tutorial 3 (for which solutions are uploaded). You will get full points for that question even if you do not write anything for that question.
  • Midterm 1 will be on Oct 21, 3:10pm-4pm (i.e. during the tutorial slot). It will be in your assigned tutorial room (that is, GB 248 if your birth month is between Jan and Jun, and LM 155 if your birth month is between Jul and Dec). You are allowed to bring one 8.5"x11" aid sheet of handwritten notes on one side.
  • Tutorial 3 has been posted.
  • Assignment 1 has been posted. The assignment is due on Oct 14 by 3pm. Remember that you can use at most two late days towards any assignment.
  • Tutorial 2 has been posted.
  • Tutorial 1 has been posted.
  • There will be *NO LECTURE ON SEP 27* to allow everyone to effectively participate in the climate strike.
  • There will be no office hour on Sep 6. Office hours will start from Sep 13. Also, there will be no tutorial on Sep 9. The first tutorial will be on Sep 16.
  • Please note that lectures will be on Wed and Fri 3-4pm, while tutorials will be on Mon 3-4pm. Office hours will be held by the instructor on Fri, right after the class, 4-5pm in instructor's office (SF 2301C). Please see the room information below.

Important Information


Lectures: Wed-Fri, 3-4pm, GB 248

Tutorials: Mon, 3-4pm
     Tutorial A (birth month: Jan-Jun) GB 248
     Tutorial B (birth month: Jul-Dec) LM 155

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

TAs: Evi Micha (emicha@cs.toronto.edu), Calum MacRury (calum.macrury@gmail.com), Stephanie Knill (knill.stephanie@gmail.com)

Instructor Office Hours: Fri 4-5pm, SF 2301C

Course Page: This page!

Discussion Board: Piazza

Online Homework Submission: MarkUs


Approximate Due Dates


Assignment 1: Oct 14

Assignment 2: Nov 9

Assignment 3: Apx. Dec 2

Midterm 1: Oct 21

Midterm 2: Apx. Nov 18


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.