COV886: Special Module in Algorithms, Spring Semester 2022

Computational Social Choice

How to make group decisions, and what's computation got to do with it.

Instructor: Rohit Vaish ()

Course Information

What this course is about

This course is about algorithms for making group decisions. These have countless real-world applications such as in voting, in matching applicants with jobs or organ donors with patients, in allocating resources fairly and efficiently among the participants, and many more.

We will study the theoretical foundations of group decision-making (or social choice) with a focus on economic issues such as fairness, efficiency, and incentives and how they interact with computation. This line of research is known as computational social choice---a fast-growing area at the interface of computer science, economics, and artificial intelligence.

Who is this course aimed at

Students interested in research in algorithmic aspects of economics/game theory should find the course relevant.

Prerequisites

We will not assume any background in economics, but a good grasp of algorithms and computational complexity is needed (so, COL351 or an equivalent course).

Reference text

A frequent reference will be Handbook of Computational Social Choice, although individual lectures will refer to different papers shared in the table below.

Admin

Lecture timings+venue

Saturday 3PM. We will use Microsoft Teams for meeting and announcements.

Office hours

By email.

Evaluation policy

Project presentation and report (60%), class participation (20%), and lecture scribing (20%). Depending on the class size, it might be possible to do lecture scribing [template] and projects in groups.

For the projects, you are expected to read a paper (or a set of closely-related papers)---a suggestive list of papers is here. Your presentation should clearly convey the problem studied by the paper(s), the status of prior work, the main contribution of the paper(s) and why you think it is novel and interesting, as well as directions for future research. If, during your study, you came up with new observations or insights, you are strongly encouraged to present those as well.

How to register

Send an email to Rohit with information about your prior coursework and any relevant projects/research experience.

Date	Topic	References
Part I: Voting
Lecture 1 Jan 15, 2022.	Voting Rules Introduction to social choice theory and axiomatic properties of voting rules.	Lecture video and slides Notes by Akash and Aniket Chapters 1 and 2 of the handbook Procaccia (2011)
Lecture 2 Jan 22, 2022.	Manipulation of Voting Rules Proof of the Gibbard-Satterthwaite theorem.	Lecture video and slides Gibbard (1973) and Satterthwaite (1975) Reny (2001)
Lecture 3 Jan 29, 2022.	Computational Barriers to Manipulation Using NP-hardness to prevent tactical voting in elections (and a bit about sports elimination).	Lecture video and slides Bartholdi, Tovey, and Trick (1989) Kern and Paulusma (2004) Faliszewski and Procaccia (2010) Chapter 6 in the handbook.
Lecture 4 Feb 05, 2022.	Structured Preferences Circumventing negative results with single-peaked preferences.	Lecture video and slides Black (1948) Bartholdi and Trick (1986) Elkind, Lackner and Peters (2017)
Part II: Matching
Lecture 5 Feb 12, 2022.	Housing Markets and Kidney Exchange Top-trading cycle algorithm and its application to kidney exchange.	Lecture video and slides Shapley and Scarf (1974) Roth, Sönmez, and Ünver (2004) Roth, Sönmez, and Ünver (2005) BBC Earth story about cyclic trades among hermit crabs
Lecture 6 Feb 19, 2022.	Stable Matchings Introduction to the stable matching problem and its structural properties.	Lecture video and slides Gale and Shapley (1962) Roth (2008) Biró (2017)
Lecture 7 Feb 26, 2022.	Incentives in the Stable Matching Problem Impossibility of truthful stable matching mechanisms.	Lecture video and slides Dubins and Freedman (1981) Roth (1982) Vaish and Garg (2017) and this chapter.
Lecture 8 Mar 05, 2022.	Fairness in the Stable Matching Problem A linear programming approach for finding a median stable matching.	Lecture video and slides Teo and Sethuraman (2001)
Part III: Fair Division
Lecture 9 Mar 12, 2022.	Cake Cutting Algorithms for proportional and envy-free cake division.	Lecture video + slides. Chapter 13 in the handbook Wiki article
Lecture 10 Mar 19, 2022.	Fair Rent Division Using Sperner's lemma to achieve rental harmony.	Lecture video + slides. Su (1999) Rent division apps on Spliddit and The New York Times
Lecture 11 Mar 26, 2022.	Fair Division of Indivisible Goods Algorithms for achieving envy-freeness up to one good.	Lecture video + slides. Lipton, Markakis, Mossel, and Saberi (2004) Markakis (2017)
Lecture 12 Apr 02, 2022.	Fairness and Efficiency Simultaneously achieving envy-freeness up to one good and Pareto optimality (and a recap of the course).	Lecture video + slides. Barman, Krishnamurthy, and Vaish (2018) - EF1+PO Caragiannis, Kurokawa, Moulin, Procaccia, Shah, and Wang (2019)
Apr 03, 2022.	Project Presentations Akash Agarwal and Aniket Mishra Fairness in Multiagent Multi-Armed Bandit Framework Dipika Tanwar Which Is the Fairest (Rent Division) of Them All? Jitender Kumar Yadav and Surendra Kumar Chauhan Fair Division of a Graph Shivangi Bithel and Amit Prasad Individual and Group Fairness in the Allocation of Indivisible Goods Hardeep Singh How to Make Envy Vanish Over Time Siddharth Grover and Simarpreet Singh Saluja Two-Sided Matching Meets Fair Division Harish Kumar Yadav and Prakhar Mangal Three Fast Algorithms for Four Problems in Stable Marriage Isha Chaudhary Mix and Match: A Strategyproof Mechanism for Multi-Hospital Kidney Exchange Sarthak Singla and Devesh Pant Using Computational Social Choice for Moral Decision Making Aayush Kumar Singh and Ayush Gupta Efficient Allocation of Individuals to Positions Akshay Sarashetti and Amar Agnihotri Approximating optimal social choice under metric preferences

Project Suggestions
Voting
Junta Distributions and the Average-Case Complexity of Manipulating Elections by Procaccia and Rosenschein (JAIR 2007) Can Approximation Circumvent Gibbard-Satterthwaite? by Procaccia (AAAI 2010) Approximately Strategy-Proof Voting by Birrell and Pass (IJCAI 2011) Justified Representation in Approval-Based Committee Voting by Aziz, Brill, Conitzer, Elkind, Freeman, and Walsh (SCW 2017) Computer-aided Methods for Social Choice Theory by Geist and Peters (Trends in COMSOC, 2017) Approximating Optimal Social Choice under Metric Preferences by Anshelevich, Bhardwaj, Elkind, Postl, and Skowron (AIJ 2018) Resolving the Optimal Metric Distortion Conjecture by Gkatzelis, Halpern, and Shah (FOCS 2020)
Matching
The Efficient Allocation of Individuals to Positions by Hylland and Zeckhauser (JPE 1979) Three Fast Algorithms for Four Problems in Stable Marriage by Gusfield (SICOMP 1987) A New Solution to the Random Assignment Problem by Bogomolnaia and Moulin (JET 2001) A Size-Popularity Tradeoff in the Stable Marriage Problem by Kavitha (SICOMP 2014) Mix and Match: A Strategyproof Mechanism for Multi-Hospital Kidney Exchange by Ashlagi, Fischer, Kash, and Procaccia (GEB 2015) On the Stable Matchings that can be Reached When the Agents Go Marching in One by One by Cheng (SIDMA 2016) Centralized Admissions for Engineering Colleges in India by Baswana, Chakrabarti, Chandran, Kanoria, and Patange (EC 2019) The Complexity of Interactively Learning a Stable Matching by Trial and Error by Emamjomeh-Zadeh, Gonczarowski, and Kempe (EC 2020)
Fair Division
Dominant Resource Fairness: Fair Allocation of Multiple Resource Types by Ghodsi, Zaharia, Hindman, Konwinski, Shenker, and Stoica (NSDI 2011) Which Is the Fairest (Rent Division) of Them All? by Gal, Mash, Procaccia and Zick (JACM 2017) Fair Division of a Graph by Bouveret, Cechlárová, Elkind, Igarashi, and Peters (IJCAI 2017) How to Make Envy Vanish Over Time by Benade, Kazachkov, Procaccia, and Psomas (EC 2018) Group Fairness for the Allocation of Indivisible Goods by Conitzer, Freeman, Shah, and Wortman Vaughan (AAAI 2019) Simultaneously Achieving Ex-Ante and Ex-Post Fairness by Aziz (WINE 2020) The Price of Fairness for Indivisible Goods by Bei, Lu, Manurangsi, and Suksompong (TOCS 2021)