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

Sep 9: Lecture Notes
 Sperner's Lemma.

References: See the original paper by Francis Su.

Sep 11: Lecture Notes
 Using Sperner's lemma to show a connected, envy-free cake division. Note that I described barycentric labelling incorrectly in class, and will fix this in the notes (TBD).

References: The above paper.

Sep 16: Slides: 1, 2, 3.
Fair division of indivisible items. EF1 via round-robin and envy-cycle elimination. EF1+PO via maximising Nash welfare. Slides today were courtesy Claude.
Sep 18: Lecture Notes
 EFX for identical agents, identically ordered agents, and EFX with charity.

References: The EFX with charity paper.

Sep 23: Lecture Notes
 A 0.618-approximate EFX algorithm for additive goods (lecture by Yeshwant).

References: The paper.

Sep 25: Lecture Notes
 MMS, an example of non-existence, and a 2/3-approximation for MMS. We only got to proving the reduction to ordered instances in the lecture.

References: The presentation is based on this paper by Garg, McGlaughlin, and Taki.

Assignments
Assignment policy
 You are encouraged to discuss the assignments with others in the class, and refer to any books or lecture notes. I strongly recommend that you write the solutions completely by yourself, and do not use LLMs at all for the assignments, including for latexing, checking your solutions, etc. You can turn in either PDFs or handwritten solutions.

It is mandatory to include, at the end of your assignment, if you discussed the solutions with anyone, or used the help of LLMs. This will not affect your grade.

I may ask you to explain some of your submitted solutions, and your ability to do so satisfactorily may affect your grade in the assignment.