Announcements
- Homework 2 is released. It is due by Apr 4, 11:59pm ET.
- The project proposal is due by March 11, 11:59pm ET. Please see the Piazza post for details on the structure of the proposal as well as for sample proposals from previous years.
- Homework 1 is released. It is due by Feb 18, 11:59pm ET.
Important Information
Time & Location: Thu, 1-3pm Eastern Time, Zoom Link (Password will be emailed)
Instructor: Nisarg Shah (SF 2301C, nisarg@cs)
Office hours: TBA
Teaching Assistant: Evi Micha (emicha@cs)
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%), and class participation (10%).