2nd Semester 2021/22: Fairness in Multiwinner Elections

Instructors

Julian Chingoma, Jan Maly and Simon Rey

ECTS

6

Description

Elections are one of the most prevalent and natural instances of collective decision-making. A common goal is producing an outcome that is, in some sense, `fair' to the voters. Such fairness concerns become more pertinent when one has to elect, not one, but multiple candidates, to form a winning committee. Common applications are parliamentary elections. In those elections, we seek to select a committee of representatives. It is critical that this committee is a fair representation of the entire society. Focusing on real-world parliamentary elections, we can observe a wide variety of methods to achieve this fairness requirement. The goal of this project is to dive into such fairness issues within the context of multiwinner voting.

While exploring this topic, we will touch on some of the different fairness notions that have been proposed, examine some voting rules designed to provide fairness, and look at some computational aspects of finding fair committees.

This topic lies in the larger area of computational social choice which deals with the aggregation of individual opinion into a collective outcome. This field is grounded in the social choice literature in economics and uses techniques from theoretical computer science (algorithmic theory, computational complexity, multiagent simulations,…).

Organisation

The first week will be dedicated to lectures given by the instructors. The second week will consist of student presentations surveying some work from the multiwinner voting literature. A selection of relevant papers and book chapters, from which students will choose what to present, will be provided. The last two weeks are for students to work on a paper of their own, with this paper being the final deliverable of the project. This may take on various forms, with examples including: a survey of the work done on a particular fairness property or adapting a multiwinner rule to a slightly richer setting.

Prerequisites

A fair degree of mathematical maturity is needed. Prior knowledge in computational complexity (mainly P and NP) can be helpful but is not necessary.

Assessment

The final grade will based on the two deliverables: the second-week presentations, and the final paper due at the project's end. This will be a pass/fail grade.

References

The following are good references to get familiar with the topic:

- Multi-Winner Voting with Approval Preferences, M. Lackner and P. Skowron, 2022 (available here: https://arxiv.org/pdf/2007.01795.pdf)

- Multiwinner Voting: A New Challenge for Social Choice Theory, P. Faliszewski, P. Skowron, A. Slinko, and N. Talmon, Chapter 2 in Trends in Computational Social Choice, Editor: U. Endriss, 2017 (available here: https://research.illc.uva.nl/COST-IC1205/BookDocs/TrendsCOMSOC.pdf)