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.

Oct 7: Lecture Notes 11, and 12
.		 Completed the 2/3-approximation for MMS. Started voting: SCFs, SCCs, and SWFs. Axioms. Arrow's theorem.

References: Chapter 2 of BCELP, and Section 9.2 in the AGT book.

Oct 9: Lecture Notes
.		 Proof of the Gibbard-Satterthwaite theorem.

References: Chapter 2 of BCELP, and Section 9.2 in the AGT book.

Oct 14
.		 Midsems.
Oct 23: Lecture Notes
.		 Single-peaked preferences, Black's theorem, and the median voting rule.

References: Section 3 from the paper "Preference Restrictions in Computational Social Choice: A Survey" by Elkind, Lackner, and Peters (available here).

Oct 28: Lecture Notes
.		 Tournament solutions: Copeland, top cycle, and uncovered set. Maximal lotteries (though we didn't get to actually proving their properties).
Oct 29: Lecture Notes
.		 Distortion in metric and non-metric settings (lecture by Soumyajit).

References: The paper "Optimal social choice functions: a utilitarian view" by Boutilier et al. discusses the non-metric bounds. For the metric distortion bounds, see "Plurality Veto: a simple voting rule achieving optimal metric distortion" by Kizilkaya and Kempe, and Prasanna Ramakrishnan's blog post.

Oct 30: Lecture Notes
.		 Continuing distortion in metric settings, and a brief introduction to linear programming.

References: For linear programming, see CLRS Chapter 9, particularly sections 29.1, 29.2, 29.4.

Nov 4: Lecture Notes
.		 Linear programming duality. Multiwinner voting (we only got as far as justified representation).

References: For linear programming, see CLRS Chapter 9, particularly sections 29.1, 29.2, 29.4. For multiwinner voting, the book "Multi-Winner Voting with Approval Preferences" by Lackner and Skowron available here will be our primary reference.

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 You must turn in clear and concise solutions in Latex.

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.

  • Assignment 1, due September 30.
  • Assignment 2, due October 21 26. The assignment is incomplete, I will add 2-3 more questions by October 12th, depending on how much we cover by then.
  • Assignment 3, due November 11. The assignment is incomplete, I will add 3-4 more questions by November 2nd, depending on how much we cover by then.