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