Announcements


  • Jan 25: Full Homework 1 are posted. The due date is Feb 10, 11:59PM.
  • Jan 21: Two questions in Homework 1 are posted.

Important Information


Time & Location: Wed, 3p-5p, CB 114

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

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

Teaching Assistant: Gregory Rosenthal (rosenthal@cs)

Course Page: This page!

Discussion Board: Piazza

Online Homework Submission: TBA


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%).