Announcements


  • Project report submission deadline is extended to April 30, 11:59pm.
  • Homework 2 deadline is extended to March 24, 11:59pm.
  • Course lectures will be moving online starting 3/20. Here's the zoom link: https://zoom.us/j/464182480
    Please read the following instructions before clicking that link.
    • Please do not join this link outside of our Friday 3-5 pm slot, as there may be other lectures going on. The department has bought a limited number of channels, and they will be re-used by courses running at different times.
    • If you want to test that the link works for you, you can try joining outside of business hours to minimize the risk of intruding on another presentation.
    • When you first click the link, you'll be given an option to download the (very lightweight) Zoom app. I suggest doing that for a smooth experience. When you click the link again, it will give you the option of joining in via the Zoom app. But you can also always join through your browser.
    • By default, your audio and video will be muted. To optimize for bandwidth, I suggest keeping them muted unless you have a question.
    • You will also be able to use the chat feature to ask questions. I may not be able to keep an eye on the chat while delivering the lecture, but your peers may be looking at it. I hear that students in other courses love to chat and answer each other's quick questions over there. But please keep in mind that I will be able to read the chat :-)
    • Finally, I plan to record the lectures as they are delivered and post them online. So in case your internet is acting up during the lecture slot on Friday, don't worry. You'll be able to listen to it afterwards.
    If you have any questions, please post them on Piazza or email me.
  • Homework 2 is posted. It is due by Mar 19, 11:59PM.
  • Project proposal is due by Mar 6, 11:59PM. Ideally in 1 page (but in no more than 2 pages), introduce the problem you're planning to work on, describe what relevant work has been done in the past, and outline precise goals you hope to achieve during the project.
  • Homework 1 deadline is extended to Feb 16, 11:59PM.
  • Homework 1 is posted. It is due by Feb 13, 11:59PM.
  • There will be no class on Feb 7.

Important Information


Time & Location: Fri, 3p-5p, HA 316

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

Office hours: In SF 2301C, any time, but email me first

Teaching Assistant: Evi Micha (emicha@cs)

Course Page: This page!

Discussion Board: Piazza

Online Homework Submission: MarkUs


Overview


This is a relatively new graduate course that surveys algorithms that aid a group of biological or artificial agents in making collective decisions. The course specifically focuses on the interdisciplinary research in 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 problems that arise when a group of agents interact such as collaboration, coordination, fairness, or the effect of social network. This will be examined through various frameworks for modelling different real-world scenarios. The course will cover: topics in social choice theory with focus on voting and fair division; non-cooperative game theory with focus on Nash equilibria, price of anarchy, and congestion games; mechanism design with money with focus on auctions; and mechanism design without money with focus on matching and facility location.


Prerequisites


The course will 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%), and class participation (10%).