Societal Impact of Computational Social Choice

We study a problem faced by a national food rescue platform that matches each donation to the first recipient who claims it. Recipients have very different response rates, leading to a few highly responsive recipients claiming the bulk of the donations. We ask whether priority lists, which control when the donation is announced to each recipient, are a remedy for inequitable outcomes. We give efficient algorithms to find the n-stage and binary priority lists that optimize a class of Rawlsian objective functions focusing on the worst-off recipients. The simple idea is to give higher priority to recipients who have received less in the past and to those who were slower in responding to notifications. This can be codified into an index by which to rank order eligible recipients. Computational experiments calibrated by historical data confirm that even binary priority lists lead to significantly more fair allocations than the existing first-come-first-serve allocation system.

We provide the first large-scale data collection of real-world approval-based committee elections. These elections have been conducted on the Polkadot blockchain as part of their Nominated Proof-of-Stake mechanism and contain around one thousand candidates and tens of thousands of (weighted) voters each. We conduct an in-depth study of application-relevant questions, including a quantitative and qualitative analysis of the outcomes returned by different voting rules. Besides considering proportionality measures that are standard in the multiwinner voting literature, we pay particular attention to less-studied measures of overrepresentation, as these are closely related to the security of the Polkadot network.

In many allocation problems with indivisible goods, fairness notions widely accepted by society, such as envy-freeness (EF), may fail to exist – famously, when two agents compete for a single item. While relaxations like EF1/EFX guarantee existence and have driven much recent progress, they risk masking genuine impossibility by labeling inherently unfair situations as “fair.” In my talk, I advocate a complementary agenda centered on the decision problem: does a fair solution exist at all?

For situations where fair outcomes do not exist in classical allocation settings, researchers have developed several workarounds: shared use, partial allocation, donations of goods, a fine-grained view of possible envy relations via social networks, or minimal subsidies. My talk advocates algorithmically assessing the feasibility of such interventions and identifying inherently unfair situations instead of hiding them.

We ran a short pilot experiment on Approval Voting during this Dagstuhl Seminar. To investigate participant preferences, participants had to choose among a set of desserts to be served during cake time. The participants were split into two groups: half of them first had to choose among six candidates (then twelve candidates), while the other half first chose among twelve (then six candidates). Our goal was to check what would be the impact of the number of candidates in the election on the average number of approved candidates per voter. Does the average number of approvals double if we double the number of candidates, remain constant, or follow a linear or sublinear relationship? As we expected, we observed in this experiment that voters tend to lower their “approval threshold” when there are fewer alternatives in the election. We aim to repeat this experiment with more participants and by applying the different changes that were proposed during the discussion with the seminar’s participants.

Since 2002, 22 voting experiments have been conducted in parallel to French presidential elections, testing alternative voting methods such as Approval voting, Borda, Instant runoff voting, Evaluative voting, or the Majority Judgement. Most of these experiments took place on specific French cities on the day of the election, in official voting stations: after voting in the actual election, voters could take part in the experiment. Since 2012, some voting experiments have also been conducted online, enabling them to reach a high number of participants. These datasets are of significant interest for social choice experiments. Indeed, they cover many different ballot formats, and in some cases, voters provided their preferences with different ballot formats, allowing to compare voting rules based on different formats. Moreover, the political context often facilitates the interpretation of experiment results. Finally, because the context is the same over the years, one can study the evolution of the preferences over time. This motivated us to clean these datasets and make them freely accessible online (including those not previously available), and we aim to compile them into a dedicated library (similar to Pabulib), alongside comparable experiments conducted in other countries.

We consider ordinal elections, where each voter ranks the available candidates from the most to the least appreciated. In principle, each voter can cast an arbitrary preference order, but it is often convenient to consider structured domains of such preferences. For example, in the single-peaked domain there is a societal axis of the candidates (e.g., politicians ranked from the most left-wing to the most right-wing one) and for each preference ranking, each prefix is a contiguous interval of the axis. Such preference domains capture various rationality criteria that we expect the voters to follow.

In this talk, we discuss several ways in which one could measure diversity of structured preference domains. First, we mention the richness-based approach, studied, e.g., by Ammann and Puppe (Preference diversity. Review of Economic Design, 2025) or by Karpov et al. (Local diversity of Condorcet domains, arXiv 2024) that relies on counting various substructures in the votes. Then we introduce our concepts of inner and outer diversity. Under the former, we say that a domain is diverse if it is difficult to cluster, and under the latter we say that a domain is diverse if every possible vote is similar to some vote from the domain. We instantiate inner diversity using the k-Kemeny problem (where given an election we want to partition it – or, cluster – into a given number of subelections whose sum of Kemeny scores is lowest). To define outer diversity, we measure the expected swap distance between a random vote and the closest vote in the domain. For a number of standard structured domains (including single-peaked, single-crossing, group-separable, and Euclidean ones) we evaluate their diversity using our approaches and find that inner and outer diversity give similar results. Further, we provide a number of algorithmic and complexity-theoretic results related to computing diversity of these domains.

Election results or the outcomes of participatory budgeting campaigns are typically presented to voters as a ranked list of alternatives based on scores. However, from a user or voter perspective, we believe this method fails to adequately explain why a particular candidate is elected or a project is approved. In this presentation, I will discuss our ongoing work on applying techniques used to explain black-box machine learning algorithms to transparent voting rules. Our explanations identify the smallest subsets of collected preference data that either support the winning candidate or, if altered, could change the outcome – these are known as counterfactual explanations. I will introduce algorithms for computing these formal explanations, along with refinements and bounds on their size, particularly for the case of tournament solutions.

Citizens’ assemblies are an emerging form of democratic participation, in which a panel of randomly selected constituents weigh in on a policy question. In this talk, I will speak about the past, present, and future of Panelot.org, a not-for-profit website on which practitioners can run sampling algorithms based on fair division. First, I will summarize our collaboration with the Sortition Foundation came to be and how this collaboration impacted the design of the sampling algorithm. Second, I will talk about our algorithm deployment and the extent to which we can (and cannot) evaluate its societal impact. Finally, I will present ongoing work on overhauling Panelot, as well as several new algorithms derived from recent social choice research, which we plan to add as functionalities.

Unlike Europe’s multi-member district systems, the United States relies on single-member geographic districts, creating a complex optimization problem where boundaries must satisfy numerous competing objectives: equal population, compactness, community preservation, Voting Rights Act compliance, and state-specific criteria ranging from competitiveness to incumbent protection. This patchwork of requirements across 50 states defies uniform mathematical treatment.

Building on recent computational social choice work in redistricting, this conversation identifies where algorithmic advances could impact reform efforts. Key challenges include defining “fairness” when stakeholders fundamentally disagree on objectives, exploring the vast space of valid maps efficiently, and developing interpretable metrics that withstand legal scrutiny.

This conversation will examine why consensus remains elusive – from tensions between mathematical elegance and political feasibility to communicating technical concepts to non-technical audiences. Drawing from practical experience in US election reform, Sam will discuss what tools and measurements would most benefit practitioners and explore whether “optimal” districting is even well-defined in a pluralistic democracy. Attendees will gain insights into translating theoretical advances into real-world impact in one of America’s most contentious political processes.

Parta is a decision making method and tool that is used for different purposes: In participation councils, area development & energy transition. Parta uses the one person one vote principle to calculate the results. But is this always the most logical approach? In one specific use case, parents voted on classroom composition by age and academic level in an elementary school. Currently, in Parta, there is no information about the voter, nor can you weigh votes differently. We did an external analysis of the votes, based on an external tool. There was a difference between the preference of parents of younger children and the parents of children that were about to leave the school. The decision had more impact on the younger children. The same occurs in area development: Citizens in the area are impacted more than citizens that are casual visitors or live further away. We are considering giving stakeholders with a higher stake more votes. How should we present the outcome based on the different weights and what are the pitfalls of this approach?

People increasingly turn to LLMs for information, including answering socially contested prompts, so responses should reflect the different viewpoints of sufficiently large groups. We formalize this goal by adapting proportionally representative fairness (PRF) from social choice in metric spaces and introduce inference-time PRF: for any in-scope prompt, large cohesive groups are proportionally represented, and groups that are more cohesive are represented more closely, in the final answer. We present the first system with provable inference-time guarantees over the full response space. We train a personalized reward model that learns prompt-specific user-preference embeddings and a personalized LLM optimized for it. At inference time, a fast social-choice algorithm (a stream-lined version of the Spatial Expanding Approval Rule) selects k representative embeddings; the personalized LLM generates k conditioned responses that are merged into a pluralistic output. Assuming the model optimizes (resp. approximately optimizes) the reward, PRF over the embedding space implies PRF (resp. approximate PRF) over the response space, automatically adapting represented groups to each prompt. This is the first formalization and implementation with guarantees for viewpoint pluralism in LLMs.

I would like to argue that one of the goals the computational social choice research community should pursue today is to use our knowledge and methods to solve specific problems coming from the real world. What I call “social choice engineering” is the design of tools for solving real-world collective decision-making problems. We can distinguish two types: (1) Project-based social choice engineering: we start from the specification of an actual need, followed by a theoretical analysis of what can or cannot be done, and the implementation of a software with a suitable interface to be tested and then delivered to the client(s). (2) Product-based social choice engineering: one thinks hard about which product to develop; then a software is designed, implemented, and tested on benchmarks or pilot studies, and the last step consists of finding customers willing to use it, and possibly helping them configure it. Some works of each type exist (especially in matching), and I give several examples; still, these are too few. I try to explain why this is the case, and I argue that, in my opinion, computational social choice is threatened by the (relative) lack of engineering work.

In approval-based committee (ABC) voting, the goal is to choose a subset of predefined size of the candidates based on the voters’ approval preferences over the candidates. While this problem has attracted significant attention in recent years, the incentives for voters to participate in an election for a given ABC voting rule have been neglected so far. This paper is thus the first to explicitly study this property, typically called participation, for ABC voting rules. In particular, we show that all ABC scoring rules even satisfy group participation, whereas most sequential rules severely fail participation. We furthermore explore several escape routes to the impossibility for sequential ABC voting rules: we prove for many sequential rules that (i) they satisfy participation on laminar profiles, (ii) voters who approve none of the elected candidates cannot benefit by abstaining, and (iii) it is NP-hard for a voter to decide whether she benefits from abstaining.

Participatory Budgeting (PB), and in particular, proportionality in PB, has received significant attention from the Computational Social Choice community in recent years. This led to the discovery of voting rules like the Method of Equal Shares, that selects outcomes in a fair and representative fashion. However, these rules assume that the set of possible projects is given in advance. In this talk, I describe a new framework, that we call online PB, in which projects are revealed one by one and a binding funding decision has to be made on the spot. We consider several classical fairness axioms from the offline PB literature in this online setting, namely priceability and the most prominent axioms of justified representation, JR, PJR and EJR. We see that priceability is always satisfiable in the online setting and find tight approximations for the justified representation axioms. Additionally, we discuss experiments showing that, in practice, a simple greedy online PB rule produces outcomes that are nearly as fair as the outcomes produced by the Method of Equal Shares (without completion) in offline PB.

The problem of fairly allocating a set of indivisible items is a well-known challenge in the field of (computational) social choice. This classic problem typically assumes a single allocation, but in practice, items often need to be distributed repeatedly. For example, the items may be recurring chores to distribute in a household. Motivated by these observations, we initiate the study of the repeated fair division of indivisible goods and chores. We show that, if the number of repetitions is a multiple of the number of agents, there always exists a sequence of allocations that is proportional and Pareto-optimal. On the other hand, irrespective of the number of repetitions, an envy-free and Pareto-optimal sequence of allocations may not exist. For the case of two agents, we show that if the number of repetitions is even, it is always possible to find a sequence of allocations that is overall envy-free and Pareto-optimal. We then prove even stronger fairness guarantees, showing that every allocation in such a sequence satisfies some relaxation of envy-freeness.

The German Federal Election Law was amended in 2024. The talk illustrates how the amended law works using the election to the 21st Deutscher Bundestag in February 2025. The presentation details the procedure how votes are converted into seats, outlines the constitutional objectives as laid down in the German Basic Law, points to the fundamental goal of verifying the principle of One Person, One Vote, and provides an overview of the work of the Bundestag Reform Commission which negotiated in 2022 and 2023 the new amendment and in which the speaker participated as an expert member.

In citizens’ assemblies, a group of constituents is randomly selected to weigh in on policy issues. We study a two-stage sampling problem faced by practitioners in countries such as Germany, in which constituents’ contact information is stored at a municipal level. As a result, practitioners can only select constituents from a bounded number of cities ex post, while ensuring equal selection probability for constituents ex ante.

We develop several algorithms for this problem. Although minimizing the number of contacted cities is NP-hard, we provide a pseudo-polynomial time algorithm and an additive 1-approximation, both based on separation oracles for a linear programming formulation. Recognizing that practical objectives go beyond minimizing city count, we further introduce a simple and more interpretable greedy algorithm, which additionally satisfies an ex-post monotonicity property and achieves an additive 2-approximation. Finally, we explore a notion of ex-post proportionality, for which we propose two practical algorithms: an optimal algorithm based on column generation and integer linear programming and a simple heuristic creating particularly transparent distributions. We evaluate these algorithms on data from Germany, and plan to deploy them in cooperation with a leading nonprofit organization in this space.

My talk was a presentation of the book titled “Condorcet Domains: The Mathematics of Coherent Collective Decision-Making” written by myself jointly with Prof. Clemens Puppe (KIT). I outlined the structure of the book and gave examples of results from several chapters. As Herve Moulin noted in his foreword “The theory of Condorcet domains straddles the social sciences and discrete mathematics. This interdisciplinary volume is already a canonical reference in both communities.”

We present the results of an analysis of more than 1400 real-world participatory budgeting instances. In particular, we examine how different types of ballots influence citizens’ behavior, specifically in terms of the projects they propose and their voting patterns. Moreover, we provide recommendations on which types of ballots to use in practice

Cost utilities are those additive utilities in which every agent assigns the same utility for an item (aka its cost) that they approve, and zero utility for an item that they do not approve. They have been called generalised binary utilities and various other names. By restricting to cost utilities, the action space for agents is reduced – agents can only declare their utility for an item is equal to zero or the item cost. In fact, this is enough of a restriction to ensure that several fair division procedures become strategy proof. In this talk, I demonstrate that cost utilities are an interesting and practical domain restriction that ensures a range of good normative properties in addition to strategy proofness.

We study proportional representation in the framework of temporal voting with approval ballots. Prior work adapted basic proportional representation concepts – justified representation (JR), proportional JR (PJR), and extended JR (EJR) – from the multiwinner setting to the temporal setting. Our work introduces and examines ways of going beyond EJR. Specifically, we consider stronger variants of JR, PJR, and EJR, and introduce temporal adaptations of more demanding multiwinner axioms, such as EJR+, full JR (FJR), full proportional JR (FPJR), and the Core. For each of these concepts, we investigate its existence and study its relationship to existing notions, thereby establishing a rich hierarchy of proportionality concepts. Notably, we show that two of our proposed axioms – EJR+ and FJR – strengthen EJR while remaining satisfiable in every temporal election.

Computational social choice (COMSOC) studies principled ways to aggregate conflicting individual preferences into collective decisions. Although inspired by concrete applications such as voting and participatory budgeting, much of the published COMSOC research has focused on abstract, foundational questions, with comparatively little emphasis on deploying these ideas in practice.

In this working group, we discussed the need for increased effort towards Computational Social Choice: Research & Development (COMSOC-R&D), a problem-driven research agenda that explicitly aims to design, implement, and test collective decision-making systems in the real world. After the seminar, we collected the ideas raised in the working group in a position paper that captures this call for action. In the paper, we first articulate the defining features of COMSOC-R&D and argue that such work is a necessary next step for the community to achieve meaningful real-world impact. Subsequently, we identify key roadblocks to COMSOC-R&D and discuss potential remedies at the individual and community level. Finally, we propose desiderata and evaluation criteria for future COMSOC-R&D projects.

Our research typically starts from preferences elicited from voters in the form of rankings, pairwise comparisons, or approval ballots. Given that contemporary AI gives us powerful text-based interfaces, what are principled approaches to do social choice starting from text input? In this group we first tackled the problem of surveying datasets containing both texts and votes on texts (deliberative platforms such as Polis, parliamentary discussions, participatory budgeting, collective statement generation…). Then, participants gave talks and tutorials on their preliminary work on this topic, in particular merging natural language processing techniques or LLMs with classical social choice algorithms. Finally, we sketched a “blue sky” paper on the topic of the working group, detailing in a systematic way the different aspects of a collective decision that can profit from the use of textual processing techniques such as LLMs.

In broad strokes, social choice problems can be typically described as follows: given complete information about individual attitudes (e.g., approval, preferences) over a set of alternatives, find an outcome (e.g., an alternative, or a set of alternatives) that satisfy a given societal objective (e.g., some variant of proportional representation). In the working group we focused on investigating generalizations of the above question where: information over attitudes is incomplete and possibly sparse; the set of alternatives is not fixed and grows over time; outcomes meeting the desired objective should be computed at each time step. Social choice problems of this sort underpin applications in digital democracy and crowd-sourcing and interface directly with topics in learning theory (e.g., exploration/exploitation tradeoffs in online decision-making). The group reviewed relevant literature and proceeded to sketch a first formalization of the problem.

In this working group, one of the practical use cases of Parta was studied. In this use case, a convincing majority ( 60-70%) was preferred to move ahead with a proposal that would move 3 grades into one classroom. At first, this majority was not achieved. The vote was split 56% in favour and 44% against. After analysing the data, it was concluded that the parents of the younger children voted more heavily in favour of the proposal. The principal concluded that this group has a higher stake and decided to move ahead with the proposal, even though the majority was not as convincing as preferred. In this working group, it was explored to see whether it’s possible to take this discrepancy in stakes into account within the voting process itself. An important question was quickly raised: How do we elicit these stakes. It was first concluded that the stakes should be based on objective criteria. An idea was then proposed to democratically determine these weights. Voters are asked to assign a weight to other voters (anonymously and maybe even hypothetical) based on objective characteristics. Those weights are then averaged, before they’re used in the actual process. Another important aspect for acceptance of such a decision is the legitimacy of the final decision. To ensure this, it was concluded that the weighing process should be transparent and that the weighing should be determined in the constitutional phase. With this in mind, democratically deciding the weights will enhance legitimacy. When objective public observable criteria are not available. A number of voting mechanisms were explored to see if they would fit. Quadratic voting, the Pivotal Voting Mechanism and Storable votes were explored. A combination was proposed, where fictional money would be used over multiple decisions, to assure that the weights are elicited fairly and correctly. Using delegation to make stakes count has also been explored. Here, the weights are assigned implicitly, since voters with higher stakes will convince other voters to delegate their vote to them. This will mitigate the tyranny of the majority and therefore give voters with a higher stake more influence in the vote.