One-sentence Summary

IIIT Hyderabad, CNRS, LAMSADE, and Université Paris Dauphine - PSL show that Sequential Phragmén, Method of Equal Shares, and Proportional Approval Voting satisfy proportionality axioms inspired by multi-winner voting for sequential decision making, with experiments on synthetic data, U.S. elections, and preference models trained on the moral machine dataset demonstrating more equal utility distribution across demographics compared to a single global preference model.

Key Contributions

• The work formulates proportionality axioms for sequential approval voting, requiring every group of α% of voters that agrees in every round to approve at least α% of the decisions, and requiring groups agreeing in a β fraction of rounds to approve β · α% of the decisions.

• The analysis identifies three voting rules that satisfy axioms of this style: Sequential Phragmén operates online, while Method of Equal Shares and Proportional Approval Voting satisfy stronger versions of the axioms under semi-online and offline decision-making, respectively.

• Experiments on synthetic data, U.S. political elections, and the moral machine dataset show that aggregating votes from country-level preference models with these rules yields a more equal utility distribution across demographics than using a single global preference model.

Introduction

The paper studies repeated collective decisions made through approval voting, where the same voters choose among changing alternatives over many rounds, a setting relevant to hiring, automated virtual democracy, and coalition policy design. Standard majority or plurality decisions can concentrate influence on a fixed majority, leaving smaller aligned groups persistently underrepresented. Prior work on perpetual voting and multiwinner proportionality proposed group fairness guarantees, but left open efficient algorithms for the strongest online and fully justified representation criteria. The authors formalize PJR and EJR axioms, introduce stronger online variants, and present rules based on Phragmén, Equal Shares, and PAV that satisfy these guarantees under online, semi-online, and offline constraints, along with impossibility results and experiments showing improved fairness in virtual democracy settings.

Dataset

• The authors add a real-world dataset of U.S. political general election records, available publicly at https://osf.io/t6p7s/, to evaluate voting rules beyond synthetic data.
• Source: public anonymized Cast Vote Records (CVR) from federal, state, and local offices and yes/no ballot initiatives.
• Composition and scale: 16 counties in California and Colorado, covering elections from 2020 and 2022 where data was available.
• Processing and filtering: the authors use counties and election years for which public CVR data exists; the records already show each voter’s simultaneous votes across all issues, and no additional filtering or voter identification is described.
• Usage: the dataset is used as an empirical evaluation set, not for model training. The authors apply voting rules to real ballots and compare outcomes such as Gini coefficients, including how Approval Voting compares with alternative rules.

Method

The authors leverage a modular framework for perpetual decision making in which a sequence of decisions must remain proportionally representative over time. The input consists of $n$n voters $N$N, $T$T decision rounds $R=\{1,\ldots,T\}$R={1,…,T}, a set $C_j$Cj​ of alternatives in round $j$j, and binary approvals $A_j^i\subseteq C_j$Aji​⊆Cj​ for voter $i$i in round $j$j. A decision sequence is a tuple $D=(d_1,\ldots,d_T)$D=(d1​,…,dT​) with $d_j\in C_j$dj​∈Cj​, and the utility of voter $i$i is the number of rounds in which that voter approves the chosen alternative, written as $U_D^i$UDi​.

A central component of the framework is an axiom layer that defines what proportional representation means for such sequences. A group of voters $S\subseteq N$S⊆N agrees in round $j$j if there exists at least one alternative approved by every voter in the group, i.e. if $\bigcap_{i\in S}A_j^i\neq\varnothing$⋂i∈S​Aji​=∅. The axioms then require that sufficiently large agreeing groups receive a proportional number of accepted decisions. Refer to the implication diagram below.

The weaker pairwise justified representation property, PJR, applies to groups that agree in every round. If $S$S agrees in all $T$T rounds and has size $|S|\ge \ell n/T$∣S∣≥ℓn/T, then at least $\ell$ℓ decisions must be approved by at least one member of $S$S:

Strong PJR relaxes the requirement that the group must agree in every round. If $S$S agrees in only $k$k rounds, its size must be larger, namely $|S|\ge \ell n/k$∣S∣≥ℓn/k, before it receives the same guarantee that at least $\ell$ℓ decisions are approved by someone in the group. Thus, agreement in fewer rounds reduces the number of guaranteed happy rounds unless the coalition is correspondingly large.

The extended justified representation axioms, EJR and Strong EJR, impose a stricter individual-level guarantee. For a group $S$S that agrees in all $T$T rounds and satisfies $|S|\ge \ell n/T$∣S∣≥ℓn/T, EJR requires that there exists a voter $i\in S$i∈S with $U_D^i\ge \ell$UDi​≥ℓ. Strong EJR extends this to groups that agree in only $k$k rounds, requiring $|S|\ge \ell n/k$∣S∣≥ℓn/k and still guaranteeing that at least one voter in $S$S approves at least $\ell$ℓ decisions. The key architectural difference between PJR and EJR is therefore the unit of protection: PJR can satisfy a coalition by rotating happiness among its members, whereas EJR ensures that one member can accumulate a proportional share of approved decisions.

On top of the axiom layer, the authors instantiate three algorithmic decision rules that correspond to different operating regimes.

The first module is Sequential Phragmén, an online load-balancing rule. Each voter $i$i maintains a load $x^i$xi, initialized to zero. Every chosen alternative generates a total load of $1$1, which must be distributed among voters who approve it. The rule selects alternatives that allow this unit of load to be spread in a way that minimizes the maximum resulting load on any voter. For each alternative $c\in C_j$c∈Cj​, the rule computes

Here, $S$S is a candidate coalition of approving voters over which the load can be distributed. The rule chooses the alternative with the smallest value $s_c$sc​. As shown in the figure below, $s_c$sc​ can be visualized through a water filling process: one unit of load is poured onto the current loads of approving voters, and the water level after filling determines the new load level for the selected coalition.

After selecting alternative $d_j$dj​, the rule identifies the coalition $S$S attaining the minimum in the definition of $s_{d_j}$sdj​​ and raises the loads of voters in that coalition to the level $s_{d_j}$sdj​​. Voters outside the coalition keep their previous loads, and no voter’s load decreases. This sequential design makes the rule online, meaning it produces decisions without knowing future alternatives or future approvals. It also satisfies a prefix-style guarantee: if the realized sequence satisfies Strong PJR, that guarantee applies not only to the entire sequence but also to each prefix processed by the online mechanism.

The second module is the Method of Equal Shares, MES, a semi online budget-based rule. The rule assumes knowledge of the total number of rounds $T$T in advance, but it does not need future voter preferences. Each decision has a fixed price

and each voter starts with a budget $b_i=1$bi​=1. An alternative $c\in C_j$c∈Cj​ is called $\rho$ρ-affordable if its approving voters can pay the price $p$p without any voter contributing more than $\rho$ρ:

In each round, the rule selects the alternative that is affordable for the smallest value of $\rho$ρ. If voter $i$i approves the selected alternative $d_j$dj​, their budget is updated by

Thus, a voter who has already benefited from earlier decisions has less budget left and becomes less able to support future decisions, while a voter who has been less satisfied can afford a larger share of future costs. If no alternative is affordable in some round, the core procedure stalls, and the remaining rounds must be completed by an auxiliary completion strategy. The authors use an epsilon-completion approach that approximates the lowest affordable alternative, preserving the spending logic of MES.

The third module is Proportional Approval Voting, PAV, an offline optimization rule. Here the mechanism knows the full sequence of alternatives and approvals in advance and selects the decision sequence $D$D that maximizes a harmonic objective:

The inner sum rewards a voter for each approved decision, but with diminishing returns: the first approved decision contributes $1$1, the second contributes $1/2$1/2, the third contributes $1/3$1/3, and so on. This diminishing-return structure penalizes decision sequences that concentrate satisfaction on a small subset of voters while ignoring others. Exactly maximizing the PAV score is computationally hard, so the authors also analyze a local search variant that iteratively swaps individual decisions to increase the objective. The local search rule can be implemented in polynomial time and retains the same key proportionality guarantee as full PAV.

These three modules are connected by the axiom layer. Sequential Phragmén operates online and satisfies Strong PJR, but it does not satisfy EJR. MES requires knowledge of $T$T and satisfies EJR, but it fails Strong PJR and Strong EJR because greedy budget spending can exhaust affordability after a coalition agrees only in early rounds. PAV and local-search PAV operate offline and satisfy the strongest considered axiom, Strong EJR. The authors also examine the limits of stronger guarantees: if the coalition-size threshold in Strong PJR is relaxed by any positive $\varepsilon$ε, the resulting epsilon-strong PJR requirement can be infeasible even offline, and no semi online rule can always return a feasible sequence whenever one exists.

Experiment

The experiments evaluate the proposed rules against existing proportional rules and simple baselines on synthetic voter-approval settings, real U.S. election records, and a moral-machine preference-learning setup. Synthetic tests show that approval voting maximizes average satisfaction but yields unequal outcomes, while proportional methods and round-robin generally provide fairer utility distributions. Results on political data and learned preferences from the moral machine similarly indicate that commonly used aggregation methods favor majority or plurality opinions, whereas proportional rules achieve more equitable support for voters or groups.

The results show that proportional multi-winner rules can satisfy strong fairness guarantees in polynomial time, with the achievable axioms depending on how much information the rule receives in advance. Online sequential Phragmén provides PJR and Strong PJR, while the existence of an online rule satisfying EJR or Strong EJR remains an open problem. The semi-online method of Equal Shares meets PJR and EJR but not their strong versions, whereas the offline PAV rule satisfies all four axioms. Online sequential Phragmén offers a polynomial-time rule with PJR and Strong PJR, but its ability to meet EJR remains unresolved. More information improves axiom satisfaction, as semi-online Equal Shares meets PJR and EJR, while offline PAV meets all four axioms.

The example shows approval sets for four voters across successive paired rounds. Most voters keep the same approved alternatives over time, while two voters revise their approval in the final round. Shared approvals and single-alternative approvals illustrate how voter preferences can remain stable, overlap, or change. Voter 1 and Voter 2 keep the same approval sets throughout all rounds. Voter 3 and Voter 4 approve alternative d for most rounds, then shift to different singleton alternatives in the final round. Alternative a receives overlapping approval from Voter 1 and Voter 2, while the final round introduces more divergent approval patterns.

The evaluation examines online, semi-online, and offline multi-winner voting rules under different information settings, using paired-round examples to trace voter approvals and preference shifts. It validates how greater advance information improves achievable fairness guarantees, with online methods supporting weaker axioms, semi-online methods expanding coverage, and offline rules offering the strongest satisfaction. The approval-set example shows that voter preferences can remain stable or overlap across rounds but may also change sharply in later rounds. These findings support the broader conclusion that information availability and dynamic preferences jointly shape the fairness of collective decisions.