Announcements


  • Assignment 2 marks are now available on MarkUs. If you disagree with the marking on any questions or subquestions, please submit a remark request via MarkUs by 11:59pm on Dec 31st and include a justification for each question/subquestion.
  • Assignment 3 solutions are posted.
  • There is no tutorial this week. But an office hour will be held at this slot, i.e. this Thursday, 4-5pm ET, at the usual Zoom link.
  • Midterm 2 solutions are posted.
  • Tutorial 8 is posted.
  • Assignment 2 solutions are posted.
  • Tutorial 7 solutions are posted.
  • As announced earlier, the second midterm will take place this Thursday. Here are some more details.
    • Date: Thursday, November 24
    • Time: 4:10-5pm ET
    • Location: EX 100 (Exam Centre, 255 McCaul Street, Toronto, ON M5T 1W7) --- Same room as the first midterm
    • Format: In-person only
    • Syllabus: Mechanism Design with Money
      • Includes all topics taught from the start of mechanism design in the lecture on Oct 11 to the end of the lecture on Oct 25
      • In particular, includes VCG auction, sponsored search, and Bayes-Nash equilibria
    • Aid: You are allowed to bring one 8.5" x 11" sheet with handwritten notes on one side.
    • Clarifications: Co-instructor Evi Micha will be present in the exam room to answer any clarification questions that may arise during the exam.
  • Assignment 3 is posted.
  • Tutorial 7 is posted.
  • Another important update: Apologies for the delay caused in the course during the past two weeks. As a result, I'm making the following changes.
    • Assignment 2: A2 deadline is extended by one week. It is now due by 11:59pm on Nov 18. Groups using two late days can submit by at most 11:59pm on Nov 20. A2 solutions will be uploaded to the course web page on Nov 21.
    • Midterm 2: Midterm 2 is also postponed by one week. It will be conducted during 4:10pm-5pm on Nov 24. The room details will be made available soon.
    • Office hours and lectures: Co-instructor Evi Micha will resume office hours and lectures at their usual times and usual Zoom links starting next week. The office hour on Monday, Nov 14 will give you an opportunity to ask questions related to A2.
  • Important update: My wife and I welcomed our little one to this world last Thursday. Co-instructor Evi Micha, who is a senior PhD student conducting research on this subject, will take over the course from this point on. Since the little one decided to show up much earlier than expected, the transition will be a bit rough. I kindly ask you to be a bit patient regarding possible delays in announcements, grading, and posting of course materials. I will also work out details of office hours with the co-instructor, so that you have office hour availability for questions regarding assignment 2 and midterm 2.
    Most importantly, I am cancelling this week's lecture and tutorial, so that the course team has both this week and the next week (reading week) to work out the transition. We have finished the second portion of the course, so assignment 2 and midterm 2 will only cover the syllabus on mechanism design up to the end of the lecture on Oct 25. On Nov 15, we will begin the third and final portion of the course on social choice.
    Thank you for your understanding!
  • Due to reduced tutorial attendance, the number of tutorial sections will be reduced to 2 starting Oct 27. Students with birth month in Jan-Jun should go to BA 2135, and those with birth month in Jul-Dec should go to BA 2195. Note that there will be no tutorial in BA 2165.
  • Assignment 2 is posted.
  • Tutorial 6 is posted.
  • Due to an unmovable commitment, I'm rescheduling the office hour of Oct 24, 3-4pm ET to Oct 27, 10-11am ET.
  • Assignment 1 solutions are posted.
  • Tutorial 5 solutions are posted.
  • Tutorial 5 is posted.
  • Tutorial 4 solutions are posted.
  • As announced in the last class and in the course syllabus, the first midterm will be held on Thursday, Oct 20, 4:10pm-5:00pm ET. Here are some more details.
    • Date: Thursday, October 20
    • Location: EX 100 (Exam Centre, 255 McCaul Street, Toronto, ON M5T 1W7)
    • Format: In-person only
    • Time: 4:10-5pm ET
    • Syllabus: Game Theory
      • Includes all topics taught from the start of game theory in the first lecture on Sep 13 to the end of the game theory in the lecture on Oct 11
      • In particular, includes normal form games, strict and weak domination, iterated elimination, Nash equilibria, the indifference principle, prices of anarchy and stability, cost-sharing games, zero-sum games, and Stackelberg equilibria
    • Aid: You are allowed to bring one 8.5" x 11" sheet with handwritten notes on one side.
    • Clarifications: I (the instructor) will be present in the exam room to answer any clarification questions that may arise during the exam.
  • Due to thanksgiving (happy thanksgiving to all!), the office hour on Oct 10 is moved to Oct 11 (Tuesday), 11am-noon.
  • Tutorial 4 is posted.
  • Assignment 1 is posted. It is due by 11:59pm ET on October 15.
  • Tutorial 3 solutions are posted.
  • Tutorial 3 is posted.
  • As announced in the lecture last week, office hours will be held on Mondays, 3-4pm ET. The first one will be today (9/26). Here is the Zoom link and it uses the same password as the rest of the course (see Piazza).
  • Tutorial 2 solutions are posted.
  • Tutorial 2 is posted.
  • Tutorial 1 solutions are posted.
  • Tutorial 1 is posted.
    PLEASE READ: I was not able to cover as much material in yesterday's class as I had hoped for. Since we only covered one relatively easy concept of domination, the tutorial is significantly easier than a usual tutorial, and much easier than a usual assignment or exam. Hence, I am CANCELLING the first tutorial tomorrow (Sep 15). Instead, please solve the posted problem set at home. This will help you make sure that you're following the course. If you have any questions, please feel free to post on Piazza. I will post written solutions on Friday.
  • The first lecture will be on Sep 13.

Important Information


Lectures: Tue, 3-5pm, BA 1190, Zoom link (Password will be emailed to you and is available on Piazza)

Tutorials: Thu, 4-5pm
     Effective Oct 26:
     Tutorial A (birth month: Jan-Jun) BA 2135
     Tutorial B (birth month: Jul-Dec) BA 2195

Instructor: Nisarg Shah (SF 2301C, csc304-2022-09@cs.toronto.edu)

TAs: Soroush Ebadian, Mohamad Latifian, Devansh Shringi, Fengwei Sun

Instructor Office Hours: Mondays, 3-4pm ET, Zoom link (the usual course password)

Course Page: This page!

Discussion Board: Piazza

Online Homework Submission: MarkUs


Due Dates


Assignment 1: Oct 14

Assignment 2: Nov 18

Assignment 3: Dec 5

Midterm 1: Oct 20

Midterm 2: Nov 24


Overview


This is an interdisciplinary course on 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 foundational models and core theoretical insights that have been instrumental in their development. The course will be organized in three parts and will cover (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: The lecture slides will be our primary reference material.

Primary textbook: 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
  • A Course in Game Theory  by Martin J. Osborne and Ariel Rubinstein. Online Version
  • Networks, Crowds and Markets  by David Easley and Jon Kleinberg. Online Version

For information about homeworks, exams, grading, and policies, refer to the course syllabus.