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