Proportional representation captures a fundamental fairness principle: a group that makes up a certain fraction of a population should receive roughly the same fraction of representation in a collective outcome. Making this principle precise requires identifying which groups deserve representation and what it means for those groups to be represented. Over the past decade, work on proportional representation has been studied extensively in committee elections and participatory budgeting. This work has led to a range of solution concepts, many with roots in economics, and to the application of techniques from the algorithms community. This Dagstuhl Seminar will advance the systematic study of proportional representation in committee elections and four other domains in which the concept is becoming increasingly important.

Committee Elections. In committee elections (a.k.a. multi-winner elections), voters express preferences over alternatives, and a voting rule selects a committee of fixed size. Despite extensive progress on proportionality, especially under approval preferences, key questions remain: Which proportionality guarantees can committee-monotone voting rules achieve? Do core-stable committees always exist? How can proportionality be formalized and achieved when preferences are expressed via ordinal ballots?

Divisible Public Goods. A divisible resource, such as money or time, must be allocated among projects according to the preferences of voters or other decision makers, with applications including donor coordination and certain forms of participatory budgeting. While proportional representation is well understood for simple utility functions, key challenges include extending the theory to richer utility classes, combining proportionality with other normative properties, and connecting divisible and indivisible outcomes through best-of-both-worlds randomization.

Rank Aggregation. Rank aggregation combines several individual rankings into a single collective ranking, with applications including hiring decisions, university rankings, and search engines. Proportional approaches offer an alternative to traditional majoritarian methods by seeking to reflect all sufficiently large groups of voters in the collective ranking.

Clustering. Clustering partitions a set of data points or agents into groups, and traditional approaches generally focus on global objectives such as minimizing the average distance to the nearest cluster center. Proportionality instead seeks to represent sufficiently large and cohesive groups, with entitlements growing with group size.

Electoral Redistricting. Redistricting divides a geographic region into electoral districts subject to legal, demographic, and geographic constraints, while the spatial distribution of voters limits which electoral outcomes are attainable. Therefore, traditional fairness and proportionality concepts are not always attainable. Given the major real-world consequences of districting, particularly in the United States, researchers have developed alternative ways to assess fairness, such as comparing an enacted map with an ensemble of districting plans generated according to neutral criteria.

This Dagstuhl Seminar will bring together researchers working on these four domains, including domain experts and practitioners alongside researchers in computational social choice, mathematics, and theoretical computer science. Our goals are to identify gaps between practical requirements and existing formal models, formulate central open problems, and promote the transfer of solution concepts and techniques across domains. These will include but are not limited to solution concepts such as core stability, market-based approaches, and neutral benchmark distributions, and techniques such as randomized rounding, optimization, fixed-point methods, and Markov chain sampling.

Creative Commons BY 4.0

Robert Bredereck, Moon Duchin, Dominik Peters, and Ulrike Schmidt-Kraepelin