Announcements


  • In our final class on April 12, we will have project presentations. The order of the groups is posted here.
  • For the embedded ethics module, the post-module survey and the post-module assignment are posted on the homework page. Both are due by 11:59pm ET on April 15.
  • The project report is due by 11:59pm on Apr 17. Please submit a single PDF named "report.pdf" to MarkUs. More information below.
    Page length
    • 5 pages + references + appendix (if any).
    • Please strictly abide by the page limit. Any material (other than references) that does not fit in the first five pages must be pushed to an appendix. There is no page limit on the appendix, but I may not be able to read the appendix for grading.
    Structure
    • Suggested list of sections: Introduction, Related/Prior Work, Notation/Preliminaries/Problem Formulation/Model, Experimental Setup, Results, Conclusion/Discussion
    • Of course, not all sections will be appropriate for every project. Please feel free to adjust the list of sections according to your needs.
    LaTeX formatting
    • There is no prescribed style file. Please use a reasonable font size (at least 11pt), reasonable margins (at least 1in on all sides), and a single-column format. Here is a suggested preamble:
      \documentclass[11pt,letterpaper]{article}
      \usepackage{fullpage}
  • For the embedded ethics module to be conducted on April 5, please fill out this pre-module survey by 3pm ET on April 5. Prior to the module, please also check out this web page and take a look at these suggested readings.
    • A survey on fairness in machine learning and algorithmic decision-making (link)
    • A book chapter on participatory budgeting, which is the topic of one of the in-class module activities (link)
  • Assignment 1 marks are now available on MarkUs. If you have any remark requests, please submit them via MarkUs by 11:59pm ET on April 10. Please indicate the question(s) or subquestion(s) you want me to take a look at, and for each of them, write a brief explanation of why you believe they should be marked differently.
  • Mid-project check-in: If you believe that another 1-1 discussion with your group about the state of your project and possible future directions can be helpful, please sign up for a 30-minute discussion. I have added slots from this Friday (Mar 25) till next Friday (Apr 1) to this Calendly link.
  • Project presentations: All project presentations will be held during the final lecture on April 12. There are 12 groups. The presentations will be up to 5 minutes long followed by 1-2 minutes of questions. Please sign-up here. Please note that this sign up sheet only determines the order in which the groups will go. Each presentation will start right after the previous one finishes.
    Please do not stress out about the presentation. The goal is mainly to communicate to your classmates the cool idea you thought of and have been working on, so everyone gets to see the range of ideas where the concepts studied in class can be applied.
  • The project proposal will be due by March 10, 11:59pm ET. As a reminder, if you haven't found teammates or started thinking about project ideas yet, I highly encourage you to do so soon.
    • Page limit: Ideally 1 page, but up to 2 pages (excluding references).
    • Structure: A short introduction of the high-level idea (1-2 paragraphs), related work (1-2 paragraphs), a list of reasonable goals that you're likely to achieve by the first week of April (try to include at least some easy empirical tasks), and a list of ambitious goals (What would you focus on if the project moves fast or if you decide to pursue it after the course ends?).
    • Template: No specific template. If you're using LaTeX (preferred), you can simply use the article class.
    • Topic: You do not have to choose the topic from the course syllabus (although you're free to do so). You can choose the topic from your own research as long as you explore an idea from this course (e.g. something related to fairness or incentives). For your reference, I have uploaded two example project proposals from previous years. You can find these in the Resources tab of Piazza. As you will see, one of the proposals is regarding a topic from this course (facility location) while the other explores a game-theory inspired idea in NLP.
  • For graduate courses, it has been decided that the following options are available regarding the mode of teaching:
    • Till Feb 6: Online-only
    • Feb 7 - Feb 20: Online-only or hybrid
    • Feb 21 onwards: Online-only, hybrid, or in-person-only
    For now and until a further update from me, the class will remain online-only as Ontario is still experiencing record hospitalizations. I will continue to monitor the situation and act accordingly.
    Throughout this semester, we will not use the "in-person-only" option; if we return to in-person teaching, it will be in a hybrid mode. I hope that this helps you plan accordingly.
  • The first lecture will be held on Zoom on Jan 11, 2022 (Tuesday), 3-5pm ET. Please find the details below.

Important Information


Time & Location: Tuesday, 3-5pm Eastern Time
  • Until at least Jan 31: Zoom Link (password should emailed to you)
  • If/when the course becomes in-person: BA 1240
Instructor: Nisarg Shah (nisarg@cs)

Office hours: By appointment (email the instructor)

Teaching Assistants: Evi Micha, Soroush Ebadian

Course Page: This page!

Discussion Board: Piazza

Online Homework Submission: MarkUs


Overview


This course surveys algorithms that aid a group of biological or artificial agents in making collective decisions. The course specifically focuses on the area of computational social choice, which lies at the intersection of computer science and economics. This area has recently seen a growing number of real-world applications and this course reviews the theoretical foundations at the core of its success.

The course will investigate issues which arise when a group of agents interact. This includes fairness, efficiency, preference elicitation, and strategic manipulations. These will be examined through various frameworks and models. The topics include social choice theory with focus on voting, fair division, matching, and facility location; mechanism design with focus on auctions, and non-cooperative game theory with focus on Nash equilibria, price of anarchy, and congestion games.


Prerequisites


The course is highly theoretical and as such it will assume strong background in mathematical reasoning and formal proofs. It will also assume preliminary background in computer science (algorithmic thinking, worst-case approximations, NP-hardness) and mathematics (linear algebra, probability, statistics), but no prior knowledge of economics.


Textbook


There are a number of excellent books on topics covered in this course. Here are a few with freely accessible online versions. The first two will be the primary references for this course.

  • Handbook of Computational Social Choice  edited by Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia. Online Version
  • Algorithmic Game Theory  edited by Noam Nisan, Tim Roughgarden, Eva Tardos and Vijay Vazirani. Online Version
  • Game Theory, Alive  by Anna Karlin and Yuval Peres. Online Version
  • Introduction to Game Theory  by Martin Osborne. Online Version
  • Networks, Crowds and Markets  by David Easley and Jon Kleinberg. Online Version

Grading and Policies


Grading will be based on two assignments (40%), a final project (50%), embedded ethics module (5%), and class participation (5%).