Fairness in Multiwinner Elections

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

Instructors

Julian Chingoma: I am doing my PhD at the ILLC under the supervision of Ulle Endriss and Ronald de Haan, my research interests are mainly in Collective Decision Making and topics within Knowledge Representation and Reasoning such as defeasible reasoning and normative reasoning.

Jan Maly: I am currently pursuing my project "A holistic analysis of participatory budgeting" in which I want to explore Participatory Budgeting not as an isolated voting instance, but as a multi-year, city-wide process that consists of several stages. In general, I am interested in studying and developing tools that help people make better decision, individually or as a group. In particular, I currently work on non-standard voting frameworks such as Participatory Budgeting and Perpetual Voting, on the representation of preferences, and on computational complexity questions that arise in COMSOC and logic.

Simon Rey: PhD candidate at the ILLC under the supervision of Ulle Endriss and Ronald de Haan, I work in the area of computational social choice, taking a computational perspective on some collective decision-making problems with a special focus on participatory budgeting.

Useful resources

Most of the content for this project is based on the following book:

The following chapter offers a quick overview of the study of multiwinner elections in the context of computational social choice:

Schedule

Below you will find the schedule for the project.

Week 1

During the first week, we will give four lectures to give everyone the tools to understand the issues at stake when discussing fairness in multiwinner elections.

There will not be any homework or exercises to do between two lectures. You are however asked to review the lectures to make sure you assimilated everything and to go through the proofs to ensure you understand how to use the tools.

Week 2

The idea for the second week is to continue the lectures but this time with the students as presenters. Below you will find a list of the topics that can be discussed together with some references for them. Each topic is about an aspect of fairness in multiwinner elections that has not been discussed (or very lightly) in the lectures we gave. In the references you will typically find one book chapter that describes the theory of the concept and a paper showing applications of the technique in the context of computational social choice.

The presentation should be around 30 minutes long, 15 extra minutes will be scheduled afterwards for questions. The format is not fixed, but, you are asked to present the main definitions and findings about the topic you chose. You should think of it as a crash course you are giving the other students on your topic. There is the possibility to give the presentations online, if there is a good reason to.

Below you can find a list of the topics, together with their references. For each topic we give the part of the book discussing it as well as the reference paper for it. The latter should be your main source of information.

The assignment of presentations to students will be decided during the third and fourth lectures of the first week.

Presentations will be given on Thursday June 16, 13:00-15:00 (Room ILLC F2.19) and Friday June 17, 13:00-15:00 (Room ILLC F2.19).

Week 3

During the third week, we will have meetings with all the students to discuss their ideas and progress for their papers. Each meeting will be 30 minutes long and will be scheduled on Thursday June 23, 13:00-15:00 (Room to be announced later). On Friday June 24, 13:00-15:00 (Room to be announced later) we will also have a general session with everyone to discuss each others' ideas. You should all attend this last session.

Week 4

Last week is dedicated to the writing up of the paper. We will not plan anything during that week but if you need anything, please contact us.

The deadline to submit the paper is by the end of this week, to be exact on Friday July 3, 19:00.

The final paper

The final delivery for this project is a short paper that you will write on a topic of your choice. The content of the paper can be twofold. It can be a thorough analysis of an existing work that you explain in your own words. You can also choose to develop an original idea you had on the topic and present your findings. The second option might look scary but keep in mind that we do not expect you to have ground-breaking results after such a short project. Presenting the direction you followed as well as few findings is the kind of outcome we expect.

Any topic related to fairness in multiwinner elections will be fine. We do still ask you to submit your topic for approval in the middle of the third week.

The idea is that you write the final paper alone. Exceptions can be considered if there is a good reason to.

The paper should be typeset in LaTeX, using the IJCAI guidleines. It should look like a research article and thus should include an introduction with the motivation of the study, a (brief) review of the literature, some preliminaries explaining all the notations you will be using, the main findings and a conclusion. The paper should not exceed 6 pages including the references. Note that it is more than fine if you submit less than 6 pages, we value precision and conciseness more than anything! We strongly encourage you to read and follow the advice on writing a paper put together by Ulle Endriss.

The deadline for submitting your paper is on Friday July 3, 19:00. To submit it, email all of us with an appropriate header and the PDF file of your paper attached.

Assessment

At the end of the project, each student will receive a fail or pass grade. Two deliveries are expected for this project: the presentation and the final paper. Each of them will be graded with a fail or pass grade. The final grade of the project is the conjunction of these two grades.