Important Information
Time & Location: Thu, 1p-3p, BA 2135
Instructor: Nisarg Shah (SF 2301C, nisarg@cs)
Office hours: Any time, but send an email first
Teaching Assistant: Sepehr Abbasi Zadeh (sepehr@cs)
Course Page: This page!
Discussion Board: Piazza
Online Homework Submission: MarkUs
Overview
This is a 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 such as voting, fair division, matching, and facility location; cooperative game theory with focus on concepts such as the core and the Shapley value; non-cooperative game theory with focus on concepts such as the Nash equilibrium, price of anarchy, and congestion games; and social network phenomena such as diffusion of new technologies and influence maximization.
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 one homework (30%), a final project (60%), and class participation (10%).