Tutorial on Proportionality-Based Fairness in Social Choice

The tutorial is about collective decision making, where we wish to reach a decision on which the preferences of each participant have had an (approximately) equal amount of influence. This equal-influence target is desirable, for example, in the elections of representative bodies, in participatory budgeting, and in the division of public resources. While we usually refer to the participants as voters, the preference aggregation rules we study are applicable beyond the political domain (e.g., in finding responses to database queries, in group recommendations, or in selecting validators in consensus protocols such as the blockchain). The tutorial is devoted to the analysis of formal rules that map collections of voters’  preferences into decisions.  We formalize the idea of equal influence through properties that guarantee fairness to groups of voters. These properties usually guarantee a certain utility level to groups of voters with similar preferences, with the guaranteed utility level being proportional to the group’s size. Thus, these are properties establishing that a rule provides proportional representation. We (1) discuss how one can define these formal criteria, and (2) describe rules that provably exhibit particularly strong properties pertaining to proportionality.

Organizers

Dominik Peters is a CNRS researcher at Université Paris Dauphine, working on topics in voting, fair allocation, and proportional representation. His 2019 doctoral dissertation at the University of Oxford won the 2019 EurAI Distinguished Dissertation Award  and the 2020 IFAAMAS Victor Lesser Distinguished Dissertation Award. He worked as a postdoctoral fellow with Ariel Procaccia at Carnegie Mellon University and Harvard University (2019–21) on topics combining machine learning and social choice, and with Nisarg Shah at the University of Toronto (2021-22) on topics concerning participatory budgeting.

Piotr Skowron works at the Institute of Informatics of the UW Faculty of Mathematics, Informatics and Mechanics. His research interests combine topics from various fields, including mathematics, computer science, and theoretical economics. In 2015, he received a runner-up award for the best doctoral dissertation on multi-agent systems (IFAAMAS Victor Lesser Distinguished Dissertation Award). After doctoral studies at the University of Warsaw, Piotr Skowron did two postdocs at the University of Oxford (2016–2017) and at the Technical University of Berlin (2017–2018). In 2020, he received the IJCAI Computers and Thought Award for his contributions to computational social choice, and to the theory of committee elections. He is the author, with Martin Lackner, of the book Multi-Winner Voting with Approval Preferences, published by Springer.

Equal Shares

In 2019, Dominik Peters and Piotr Skowron proposed the Method of Equal Shares, a voting rule for participatory budgeting that guarantees proportional representation. This method will be used in 2023 for the participatory budgets of two cities, in Switzerland and Poland.

Tutorial Outline

Below we outline the topics covered in the tutorial:

  1. Proportional apportionment.
  2. Proportional portioning.
  3. Proportional committee elections.
  4. Participatory budgeting.

Target Audience

The tutorial is mainly addressed to students and researchers interested in (computational) social choice. In addition, the tutorial will be of interest to those working in fair division, cooperative game theory, and algorithmic fairness. Parts of the tutorial will be interesting also for researchers interested in the blockchain and market design (especially in the design of markets with public goods). 

Slides

The tutorial consists of two parts:

  1. First part (apportionment and committee elections) [slides].
  2. Second part (participatory budgeting, committee elections with rankings as inputs, sequential decision making, fair mixing) [slides].