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.