Computational Social Choice
Course outline
 Social choice studies how groups of agents aggregate their preferences to reach a collective decision. In this course, we are interested in both computational and analytical aspects of this decision making. We plan to cover classical and recent results in computational social choice, particularly in fair division, voting, and matching. Evaluation will be on the basis of assignments, quizzes, in-class exams, and either a project or a paper presentation.
Prerequisites
 The course will be easier if you've taken algorithms, linear and nonlinear programming, and algorithmic game theory. You are welcome to take the course if you haven't taken these, though some extra effort may be required.
Details
 Classes will be held Wed / Fri 11:30-1 pm in A-201.

Classes begin on Friday, August 21st.

Reference material
 The following courses also cover similar material:
  • A list of COMSOC courses.
  • A course by Rohit Vaish at IITD (for some reason, Rohit's website doesn't work from the TIFR network; you may have to use your phone network).
  • A course by Piotr Skowron at the University of Warsaw.
Lectures
Aug 21: Lecture Notes
 An introduction to fair division and computational social choice. Cake cutting, proportionality, and envy-freeness. An O(n^2) algorithm for PROP (the Dubins-Spanier, or "last diminisher" algorithm). Cut-and-choose for 2 players, and exact cake divison (the "Austin moving-knife" procedure).

References: Chapter 13 of BCELP (Handbook of Computational Social Choice), Lecture 7 in Rohit's course

Aug 26: Lecture Notes
 The Even-Paz algorithm for proportional cake division. Envy-freeness, and a protocol for 3 agents. Pareto-optimality for 2 agents.

References: A lower bound for proportional cake cutting, and a recent upper bound. Also chapter 13 of BCELP (Handbook of Computational Social Choice).

Aug 28: Lecture Notes
 Fractional knapsack, Fisher markets, and CEEI. CEEI + non-satiation gives EF and PO.

References: Chapter 13 of BCELP (Handbook of Computational Social Choice).

Sep 2: Lecture Notes
 Nash welfare and CEEI for divisible goods. Also a (very) very brief primer on convex programming and duality.

References: Chapter 13 of BCELP (Handbook of Computational Social Choice).

Assignments