In this paper
AbstractIntroductionContributionRelated WorkElection SettingProportionality GuaranteesThe SCR Rule under General ConstraintsAlgorithmic Aspects of the SCR RuleLimitations of SCR under Approval VotingEmpirical Analysis of the SCR RuleStrictly Ordered Truncated BallotsApproval BallotsConclusionTechnical AppendixThe Modified Solid Coalition Refinement RuleOmitted ProofsAdditional Findings and DetailsReferencesWorksComputer Science
Proportionality in Elections under Feasibility Constraints and Ranked Ballots: The Solid Coalition Refinement Rule
Abstract
We study elections with ranked ballots and general feasibility constraints, which indicate which sets of candidates are allowed as outcomes. We introduce the first proportionality axiom for this general setting and show that it extends the established notions from specific models that fit our general framework. We extend the Solid Coalition Refinement (SCR) rule to general constraints and prove that it satisfies our axiom exactly for matroid constraints. Although the naive implementation of SCR involves a step that is computationally intractable for weak orders, we show that in practical cases it can be implemented in polynomial time or efficiently in FPT time. We also illustrate limitations of this rule for approval ballots and provide its first empirical evaluation.
Introduction
The formal model of an election involves two largely independent choices. First, one specifies how voters express their preferences. This can be done through approval ballots, numerical scores, or rankings. Second, one specifies what qualifies as a valid outcome. In a committee election, this may mean selecting at most a fixed number of candidates. In participatory budgeting, the chosen projects must fit within the available budget. When several issues are decided simultaneously, the outcome may need to contain exactly one option for each issue. Some combinations of alternatives may also be ruled out because they are incompatible. We refer to all such requirements as feasibility constraints. We study the setting in which voters submit ranked ballots and the outcome is subject to arbitrary such constraints. By doing so, we take a step toward a general theory of fairness in voting. We formalize fairness through proportionality: if a group comprising an -fraction of the electorate has sufficiently cohesive preferences, it should influence approximately an -fraction of the outcome.
Ranked ballots. Rankings are a fundamental language for expressing preferences: each voter submits a strict or weak order over all or a subset of the candidates. They are used in elections for national legislatures and local governments [39], as well as in participatory budgeting [38]. Controlled experiments suggest that citizens prefer rankings to other ballot formats [41]. Beyond politics, ranked preferences underlie matching markets, including school and internship assignment, some Academy Award procedures [1], search and recommendation systems, AI alignment, and expert selection processes.
Feasibility constraints. A feasibility system specifies which subsets of candidates may be selected, thereby abstracting away from the details of a particular application. It can represent selecting a committee of bounded size, choosing one alternative for each of several issues, or funding projects subject to a budget constraint. It can encode logical consistency requirements in judgment aggregation and restrictions such as demographic diversity bounds, regional quotas in participatory budgeting, or limits on the number of selections from each given category. It captures settings where some candidates are required to be selected. Such constraints arise in many real-world elections and are explicitly specified in their bylaws and regulations. For example, the AAAI Executive Council requires fewer than half of its members to have potential conflicts of interest; the Green parties in Germany and Poland impose gender quotas; PB processes restrict the joint selection of conflicting projects (e.g., in Katowice) or impose neighbourhood-specific budget limits (e.g., in Amsterdam); World Athletics Council elections impose gender and geographical constraints; and CoARA Steering Board elections additionally impose quotas on the representation of different types of organizations, such as universities, research centres, and funding organizations.
Each of these two dimensions is already well understood when the other is restricted. In particular, there is a developed theory of fairness for arbitrary feasibility constraints combined with approval ballots, i.e., dichotomous rankings [25]. Similarly, there is already quite a good understanding of fairness for ranked ballots combined with a simple cardinality constraint, i.e., for committee elections. Combining ranked ballots with arbitrary feasibility constraints, however, poses a qualitatively different challenge.
Methods developed for approval preferences under general constraints do not extend directly to rankings; nor do the more recent methods designed for numerical scores [35]. Nevertheless, these methods typically follow a common template: they construct the outcome sequentially and, at each step, disregard candidates whose addition to the current partial solution would violate the feasibility constraints. This observation suggests a natural approach to our problem: start from a committee-monotonic rule for ranked ballots, i.e., a rule whose outcome for a committee size is a superset of its outcome for a committee size for any , and adapt its selection process to accommodate general feasibility constraints. This approach, however, need not lead to a satisfactory outcome. In particular, feasibility cannot simply be imposed after first computing a proportional ranking. To see this, consider an election over the candidates , subject to the constraint that exactly one candidate from each pair must be selected. Suppose that 51% of the voters rank , whereas the remaining 49% rank . Reverse-sequential variants of Single Transferable Vote and the Expanding Approvals Rule [6]—committee-monotonic rules satisfying strong proportionality guarantees—would produce the alternating ranking . This ranking represents the two groups almost perfectly: candidates preferred by the two groups appear in alternating positions. However, scanning the ranking from top to bottom and selecting each candidate whenever feasibility permits yields the outcome , because, once is selected, its counterpart becomes infeasible, and hence almost half of the electorate receives no representation at all.
Thus, preferences and feasibility must be handled jointly, rather than in two separate stages. We show that another committee-monotonic rule for ranked preferences—the Solid Coalition Refinement (SCR) rule [6]—can be successfully extended to arbitrary feasibility constraints.
Contribution
We introduce the first proportionality axiom for ranked voting under general outcome constraints. Our axiom combines ideas from the proportionality axioms developed for ranked ballots in committee elections [6] and approval ballots with feasibility constraints [25]. We show that our axiom generalizes the established properties in these two restricted settings.
We provide a voting rule with provable guarantees for our setting, which is obtained as a natural extension of the Solid Coalition Refinement rule [6]. We show that it satisfies our proportionality notion whenever the outcome constraints form a matroid, a class that captures multiple natural and important relevant applications such as committee elections, public decision making over multiple issues and elections with disjoint candidate attributes. Complementing this result, we construct a family of instances showing that, for every non-matroid structure, there exists an election in which the rule fails to produce a proportional outcome.
We also present a comprehensive set of findings on the computational complexity of the proposed rule. Although SCR is polynomial-time computable for strict rankings (and continues to be so under general outcome constraints), it becomes intractable for weak rankings unless P = coNP [6, 8]. We identify the first natural parameters for weak rankings where SCR admits fixed-parameter tractable algorithm, even in the presence of general constraints. The rule becomes tractable for two preference levels (approval ballots), whenever the equivalence classes in the weak rankings are bounded (a relaxation of strict rankings that is particularly practically relevant [27]), and for elections with a small number of voters.
Finally, motivated by the tractability of SCR for approval ballots, we take a closer look at this special case and provide a more fine-grained analysis of its fairness guarantees in the committee elections setting. We study the proportionality degree [34] of SCR and show that it can be surprisingly low. We prove this result by first constructing a tailored hand-crafted instance and then using computer-aided instance generation to strengthen it—a technique that may be of independent interest. An additional limitation is that the rule fails to guarantee Pareto optimality.
We complement our theoretical findings with the first empirical analysis of SCR. We use real-world datasets that cover the tractable cases we identified.
Related Work
The question of proportional representation under general feasibility constraints has only recently begun to receive attention. For the approval setting, Masarík et al. [25] showed how PAV and Phragmén’s rule can be extended from committee elections to arbitrary constraints and proved that these rules satisfy a generalizations of the well-known EJR [4] and PJR [36] axioms, respectively, if and only if the given constraints forms a matroid. PAV is also considered by [26], who showed that yet another generalization of EJR (see [25] for a comparison of the two notions), called restrained-EJR, is satisfied when the constraints are independent sets of a matroid. Beyond approval ballots, this work also considers cardinal ballots (i.e., where each voter assigns a numerical value to each candidate), aiming for approximate versions of the cardinal-utility-centric core stability property [12, 14, 24]. Proportionality aspects for elections with general feasibility constraints under cardinal ballots have also been considered in a recent work by [35], where adaptations of MES [30], Phragmén’s rule [9], and BOS [29] to the general setting are introduced and proportionality guarantees of these rules are established.
For ranked ballots, within the framework of committee elections, the classic proportionality notion is proportionality for solid coalitions (PSC), introduced by Dummett [13] and extended to weak rankings (IPSC) by Aziz and Lee [3]; quantifiable versions of PSC have been proposed by Bardal et al. [7]. These properties guarantee representation proportional to the size of groups of voters that rank the same block of candidates above all others, irrespective of their internal ordering. PSC has been described as an absolutely essential condition for proportionality [40] and is satisfied by rules including STV [37, 40], and the Expanding Approvals Rule [2]. The Solid Coalition Refinement rule was very recently proposed by Aziz et al. [6] as the first rule satisfying both PSC and committee monotonicity—the property that electing candidates should yield a superset of the winners for any smaller committee size. A candidate-monotone probabilistic voting rule based on Phragmén’s Ordered Rule [17] that also satisfies PSC in expectation was proposed by Peters [31]. Strengthenings of IPSC have been proposed by Brill and Peters [8], such as rank-PJR+, which is satisfied by EAR but not by STV. Other stronger notions of proportionality include local stability [5] and the core [18, 10, 32], yet these properties are not always satisfiable. Alternative notions that focus on pairwise comparisons between input and output rankings have been considered by Lederer [22] and Lederer et al. [23].
Over the recent years proportionality has become a central theme of social choice, with applications extending well beyond political elections [16, 19, 28].
Election Setting
An election under ranked voting is a quadruple , where is a set of candidates, is a set of voters, is a nonempty family of feasible outcomes, and is a profile of weak orders over , representing voters’ preferences. If the feasible outcomes consist of exactly sets of size at most , for some integer , we refer to this setting as committee elections. If no voter is indifferent between any two candidates, we classify their ballots as strict rankings. If each voter’s ranking has at most two tiers, so called dichotomous rankings, we refer to the corresponding setting as approval voting. In the latter case we denote by the upper tier of voter . A selection rule, or simply a rule is a function mapping an election to an outcome .
Proportionality Guarantees
In this section, we introduce our main notion for group fairness for the considered general setting of elections. We build on the notion of a solid coalition for weak rankings, or, in short solid coalition, originally termed generalized solid coalition by Aziz and Lee [2].
Definition 1. Given an election , a solid coalition of is a pair , where and , such that every voter in weakly prefers each candidate in to each candidate in .
Towards a proportionality axiom, we require that any solid coalition is represented in the outcome by candidates that the voters in find acceptable as substitutes for those in . Specifically, a candidate is an acceptable substitute if at least one voter in ranks no worse than some candidate in . Following the terminology of Aziz and Lee [2], we capture this via the periphery of with respect to : the set of all candidates that some voter in considers at least as good as some candidate in . This relaxation of the set satisfaction of voters in is necessary for ensuring satisfiability of the corresponding axiom [2].
Definition 2. Given an election , and a solid coalition we define .
We now define the axiom of Proportionality for Solid Coalitions for Election under Feasibility Constraints, or, in short, Proportionality. The periphery naturally sets the stage: a coalition is -represented in the outcome if at least members of appear in , capturing the idea that acceptable substitutes count toward the coalition’s share. The subtle challenge is deciding when has a legitimate claim to representatives. We proceed in the spirit of the axioms introduced by Masarík et al. [25] to capture proportionality under general feasibility constraints in the approval voting setting. Granting representatives to could block other voters from candidates they care about, due to feasibility constraints. Take any . Although arbitrary, it intuitively represents the candidates over which the voters in can exercise their influence. If and candidates from can coexist in a feasible outcome, there is no conflict and the claim of can be guaranteed. If they cannot coexist, the claim remains legitimate as long as is proportionally large enough to outweigh the rest—formally, that the claim of to candidates is stronger, relative to its size, than the remaining voters’ claim to . This is captured by , which is equivalent to , whenever and . A solid coalition deserves candidates when no set forms valid evidence against its claim, and the axiom that we propose demands that every deserving coalition is indeed represented.
Definition 3. Given an election , we say that a solid coalition deserves candidates in if for every either there exists a set with such that or . We say that an outcome satisfies Proportionality if for every positive integer and every solid coalition that deserves candidates in we have .
To position our definition of proportionality within the literature, we provide the following findings. First, it extends generalized PSC [2] from committee elections to arbitrary feasibility constraints. The axiom called generalized Droop-PSC is satisfied by a committee as long as for every natural number and for every solid coalition with , it holds that contains at least candidates from .
Theorem 1. Given a committee election under ranked voting , an outcome with satisfies generalized Droop-PSC if and only if satisfies proportionality in .
Second, the known equivalence [2] from the committee election setting between generalized PSC and PJR does not immediately carry over to the setting with feasibility constraints. PJR under feasibility constraints is defined by Masarík et al. [25] as follows.
Definition 4. Given an approval voting election and an outcome , we say that a group of voters deserves candidates in if for each set either there exists a set with such that or the following inequality holds: . We say that an outcome of an election satisfies Proportional Justified Representation if for every group of voters that deserves candidates we have .
We show that Proportionality always implies PJR, while the reverse is not always true. In particular, we show that they are equivalent whenever all inclusion-wise maximal feasible outcomes have the same size (e.g., under matroid constraints; see Definition 5), and that this condition is also necessary in the sense that whenever it is violated, there exists an election in which PJR is strictly weaker than Proportionality.
Theorem 2. Given an approval voting election under feasibility constraints , if an outcome satisfies Proportionality then satisfies PJR in .
Theorem 3. Given a family of feasible outcomes , if each inclusion-wise maximal set is the same size, then for each election and an inclusion-wise maximal outcome satisfying PJR, also satisfies Proportionality. If there exist two inclusion-wise maximal outcomes with different sizes, then there exists an election and an inclusion-wise maximal outcome satisfying PJR but not Proportionality.
The SCR Rule under General Constraints
The Solid Coalition Refinement (SCR) rule, introduced by Aziz et al. [6] for committee elections, starts from the empty outcome and repeatedly selects the candidate that best addresses the strongest underrepresented coalition. The underrepresentation value of a solid coalition under the current committee quantifies how far is from being proportionally represented: the higher the value, the stronger the claim of to the next seat. This value is defined as . When the most underrepresented coalition is , the rule adds a candidate from . If several such candidates exist, it must decide which one in particular to select. To do so, it applies a process of refinement: the selection procedure is applied iteratively to the candidates in , narrowing the set down until it contains only one candidate not in , which is then added to the committee. We denote the committee formed after a number of selections of candidates by .
The only modification needed to extend the rule to (downward-closed) feasibility constraints is to ensure feasibility is maintained at every step. Moreover, each refinement step should ensure that at least one electable candidate survives. We call the resulting rule the Solid Coalition Refinement for Feasibility Constraints, or, in short Solid Coalition Refinement (SCR) rule. The pseudocode is given in Algorithm 1, where we assume a deterministic tie-breaker ensuring that the function returns a single output.
Theorems 1 to 3 hold for arbitrary feasibility constraints. Henceforth we restrict attention to downward-closed constraints. However, this assumption is not restrictive as any family of feasible sets can be transformed into a downward-closed one without affecting our theoretical results: given a family , we define to consist of all sets that can be extended to some set in . By construction, is downward closed and can then be used within the SCR rule. Then, any outcome returned by SCR is already feasible under since SCR returns an inclusion-wise maximal set.
Algorithm 1: Solid Coalition Refinement rule for elections under feasibility constraints.
Our main axiomatic result (Theorem 4) shows that its outcome is proportional, in the sense of Definition 3, provided that the input feasibility constraints form a matroid. Note that the proportionality guarantees provided by Masarík et al. [25] are also contingent on the feasibility constraints forming a matroid.
Definition 5. A family of feasibility constraints is a matroid if for each such that , there exists such that .
The intuition is that candidates carry similar weight in a matroid and if removing two or more candidates from an outcome can make room for some new candidate, then in fact removing just one of them suffices. As noted by Masarík et al. [25], matroid constraints already capture several natural settings, including committee elections, public decisions, and elections with disjoint candidate attributes. That said, important frameworks fall outside this class and would require separate treatment, such as Participatory Budgeting [33] or elections with both positive and negative ballots [20]. We view these as particularly important future directions.
Theorem 4. Given an election where is a matroid, satisfies Proportionality.
Proof Sketch. The proof of the result is based on two technical lemmas. The first guarantees that SCR continuously protects coalitions admitting feasible representation: if, at the beginning of a step, they support a candidate that can feasibly be added to the committee, then, after the step, they cannot remain excessively underrepresented.
Lemma 1. Given an election , where is a matroid, after each step of the SCR rule, for every solid coalition , if there exists such that then .
To show Lemma 1 we build on the payment-scheme approach that was used for proving that SCR satisfies PSC for committee elections [6]. While this lemma’s underrepresentation value suffices for committee elections, going beyond it requires an additional step. In particular, while the proof of Lemma 1 indeed largely follows the arguments of Aziz et al. [6], the proof of Lemma 2 is entirely novel—it is independent of any specific rule and establishes a general invariant whose preservation is sufficient for satisfying the axiom. According to Lemma 1, SCR maintains this invariant ensuring that, after each selection, every deserving coalition can still achieve proportional representation.
Lemma 2. Given an election , where is a matroid, let be the outcome of SCR in . After each step of the SCR rule, for every solid coalition that deserves candidates in , there exists a set such that and .
Lemma 2 guarantees that at every step , for each solid coalition deserving candidates in the outcome of the rule (in the sense of Definition 3), there exists a set that can still be elected and electing it will result in being -represented. From this, Theorem 4 follows directly, because, when the rule terminates, no further feasible candidate can be added, meaning that is already -represented.
We conclude the section by establishing tightness for Theorem 4 with respect to the considered families of constraints: moving beyond matroids leads to a negative result.
Theorem 5. For each non-matroid family of feasibility constrains , there is an election , where fails Proportionality.
Algorithmic Aspects of the SCR Rule
SCR performs particularly well under strict preferences. Not only it achieves strong proportionality guarantees even in the presence of general feasibility constraints making it the first rule known to produce proportional outcomes in such a broad framework under ranked ballots, but it is also polynomial-time computable [6]. However, once we move to weak rankings, the naive implementation of the rule involves a step that is computationally hard, already in the setting of committee elections [6]. We address this issue by establishing parameters of the input ballots that admit a fixed-parameter tractable algorithms, even under general feasibility constraints.
We note that the transition from committee elections to general feasibility constraints introduces no additional computational burden. In particular, this holds under the assumption that we have access to an oracle that, given a subset of the candidates, determines whether it is feasible. Such an oracle can be implemented in polynomial time for most of the natural feasibility constraints, and we assume its existence for the results of this section. The only component whose polynomial-time implementability is not immediate is the maximization procedure in Steps 5–6 of Algorithm 1. It is this maximization problem that is arising in the refinement loop of SCR that is coNP-complete when weak rankings are allowed in the input ballots [6, 8]. The intractability result relies on weak rankings with three preference levels with a number of candidates per level that is a function of . This leaves open two regimes in which tractability may still be possible:
preference structures of two levels—approval ballots,
indifference classes in voters’ ballots of bounded size—the first step beyond strict rankings.
We show that both admit efficient algorithms. Then, we complement these positive results by studying the parameterized complexity of the rule with respect to the number of voters and candidates, obtaining additional tractability results.
We begin with the setting of approval voting. For a solid coalition , we distinguish two cases. In the first, . For this, we show that the periphery of with respect to is not affected by the size or the members of , so the rule only needs to consider singleton sets , since their supersets would yield the same underrepresentation value. This makes the refinement step unnecessary, as any refinement sequence resulting in electing a candidate can skip the intermediate refinements. The second case is when there exists some voter such that . Then we have , so again this does not depend on the set . Therefore, we can restrict coalitions of this kind to those that refine the current set by removing only a single candidate from it. Taken together, these two cases imply that the refinement simplifies to either immediately electing or removing a candidate. This decision is based on a maximization that we show that it can be performed in polynomial time via a reduction to a submodular optimization problem—an approach that resembles a previously used one by Brill and Peters [8] for a conceptually different problem.
Theorem 6. In the approval voting setting, the outcome of the SCR rule can be computed in polynomial time.
The second type of coalitions, discussed above, and considered at every step of SCR in the approval setting (i.e., coalitions that refine the set by removing a candidate), arise when closely following the original definition of the rule by Aziz et al. [6] for weak orders over all candidates and applying it to the approval setting. However, such coalitions are not a natural object of interest in the standard approval-based framework, as voters are typically assumed to derive no satisfaction from candidates outside their approval ballots. Given that these coalitions are technical artifacts, and that they are naturally proportionally represented in any outcome when the feasibility constraints satisfy the prerequisites of Theorem 3, it is reasonable to avoid considering this step in the algorithm. For approval ballots, we call the resulting rule Greedy-PJR+, as it greedily optimizes an axiom called PJR+ [8]. We refer to Section 6 for a comparison of this rule with SCR.
As mentioned, SCR is polynomial-time computable for strict rankings, i.e., when each preference level contains a single candidate. We now show that SCR remains efficiently computable whenever the size of each preference level is bounded. We also extend this algorithm to handle truncated ballots, i.e., ballots where there are candidates that have not been explicitly ranked, and which are assumed to belong to the last preference level, with indifference classes of bounded size. This is, for example, the case in the large recently compiled dataset of Scottish local elections [27]; we use this in the empirical evaluation (§ 6).
Theorem 7. The outcome of the SCR rule can be computed in FPT time parameterized by the maximum number of tied candidates in a non-last level of a voter’s ranking.
Following the modification of the rule for approval ballots that led to the introduction of Greedy-PJR+, the same insight motivates a re-consideration of the implementation of SCR for truncated ballots. In this variant, we restrict attention to coalitions such that every member of includes all members of in a preference level above their last one. We evaluate this variant as well in § 6.
Once in the realm of parameterized algorithms, it is natural to ask what happens when we take the basic instance parameters as our focus. The size of indifference classes is bounded by the number of candidates, so the algorithm from Theorem 7 is also FPT with respect to . Parameterizing with respect to needs another approach, but again leads to FPT.
Theorem 8. The outcome of the SCR rule can be computed in FPT time parameterized by the number of voters.
We conclude by highlighting that the parameterized algorithms from Theorems 7 and 8 are highly relevant in practice, as their parameters are typically small. In particular, to establish this claim, we examined all 63 Preflib datasets with ranked ballots, covering a wide range of applications. In over 50%, at least one of the parameters for which we establish FPT was at most 10, and in over 70%, at most 15.
Limitations of SCR under Approval Voting
For ranked ballots with general feasibility constraints, our adaptation of SCR is the first rule known to provide fairness guarantees. Focusing on committee elections, under ranked ballots, SCR achieves a prominent guarantee that is among the strongest in the literature. Restricting the focus further, in this section we aim to understand how it compares with established proportional methods in the special case of approval ballots, which can serve as a natural benchmark. The result of Theorem 6 makes this setting a suitable domain for applying the rule, provided that its theoretical properties remain satisfactory. Unfortunately, in this section we show that this is not the case, as SCR may fall short both in terms of fairness and efficiency. This leads to the conclusion that when the flexibility and expressiveness gained from ranked ballots and, even more so, from general feasibility constraints is not necessary for the application at hand, existing approaches such as MES, PAV, and Phragmén appear to be better suited.
The simplicity of the approval setting allows us to perform a fine-grained analysis of fairness. By studying its proportionality degree [34], we show that the outcome of SCR can be particularly weak in that regard, even for committee elections. For comparison, note that the proportionality degree of PAV is , of Phragmén is and of MES is between and [21].
Definition 6. Let be a committee election under approval ballots. A group of voters is -cohesive in if and all voters in approve at least common candidates. Fix a function . A rule for committee elections under approval ballots has proportionality degree if, for every election and every -cohesive group of voters , the outcome satisfies .
We prove the negative result regarding the proportionality degree of SCR in two steps. The key idea is to start from an analytically tractable instance (Theorem 9) and then refine it via a linear program (LP) to obtain a strictly stronger bound (Theorem 10). This technique constitutes a methodology of independent interest for the creation of negative instances and may be useful beyond the specific rule and the considered elections domain. We first construct an intuitively clean instance that suffices to establish the weak performance of SCR with respect to the considered metric, for arbitrary .
Theorem 9. For each , there exists an and an approval committee election with an -cohesive group of voters such that , .
Now we set the question of whether the instance used in the proof of Theorem 9 to upper bound the proportionality degree of SCR can be further improved. We answer this in the affirmative using a computer-aided approach. We formulate an LP that takes a committee size as input and outputs an instance inspired by the construction in Theorem 9, with the goal of tightening the bound. This method allows us to derive improved bounds for small values. of . Since in many natural applications of committee elections the intended committee size is reasonably small, this result is informative in practice, even though it does not provide a closed-form expression valid for arbitrary as Theorem 9 does.

Figure 1. Average values of the evaluated metrics for the outcomes produced by the considered rules on strictly ordered truncated (§ 6.1) and approval ballots (§ 6.2). Bars indicate the 25–75th percentile range.
Theorem 10. For , there exists an and an approval committee election with an -cohesive group of voters such that , .
Empirical Analysis of the SCR Rule
In this section, we present the first experimental evaluation of SCR. We focus on two highly important scenarios where its outcome can be computed efficiently as shown in § 4:
(a) truncated ballots with strict rankings,
(b) approval ballots.
For each setting, we compare SCR against popular rules using suitable datasets. We conduct our comparison in the framework of committee elections: the most basic and well-studied feasibility constraint. This provides a clean experimental setting that allows for clear insights into the behavior of the rule, enabling direct comparison with the standard benchmarks studied in the relevant literature. Our main findings are presented in Figure 1; additional results are provided in Section A.3.
Strictly Ordered Truncated Ballots
We use the dataset of Scottish local elections [27], which consists of 1070 instances from local government elections held between 2007 and 2022. In these, voters were submitting strictly ordered truncated ballots.
We compare SCR against the following rules: -Borda, capturing efficiency-oriented approaches; and STV, one of the most established methods for ranked voting in real-life elections, including Scottish local elections; and EAR, a relatively recently introduced method with strong theoretical proportionality guarantees. We additionally consider a variant of SCR, denoted as truncated, where a voter can belong to a coalition only if all candidates in are ranked on their ballot, i.e. they are not placed in the last preference level. We use an analogous interpretation for the implementation of the other rules. We refer the reader to Section A.3 for the definitions of the considered rules. For the non-exhaustive rules (EAR and STV), we use the Add1 completion method [15]. Namely, when a rule returns an outcome of fewer than candidates, we repeat after having slightly increased the voting power of each voter. We also tested other completion methods and Add1 consistently achieved better results, providing a stronger benchmark against which to evaluate SCR. The rules are evaluated based on the following metrics:
Utilitarian score: We first assign Borda scores to ranked candidates of each voter, where the top-ranked candidate receives points, the second-ranked candidate receives points, and so on. Unranked candidates receive 0 points. The total score of the committee from all voters is then normalized by the value achieved by the -Borda rule.
Exclusion ratio: This is a standard measure in the proportionality literature that captures the fraction of voters whose ballots do not contain any elected candidate. The dataset includes highly truncated ballots (specifically, only 13% of ballots across all elections contain rankings over all candidates). Therefore, this metric captures the voters who did not rank any of the elected candidates.
PSC, Rank-EJR+ and Local stability Values: These metrics are defined by Bardal et al. [7], who introduce quantitative measures for several axioms in the ranked voting setting. They extend well-established binary metrics by asking for the smallest approximation factor of a group’s size for which the axiom remains satisfied. Lower values indicate that the axiom is satisfied for a larger fraction of voter groups, and therefore correspond to stronger fairness guarantees.
With respect to utilitarian performance, SCR performs slightly worse than its competitors but still achieves a remarkable 97% of the optimum on average. This modest utilitarian loss is traded for slightly stronger fairness guarantees. Across all fairness metrics and classes of instances considered, the truncated variant of SCR achieves comparable, sometimes even slightly better, performance to the state-of-the-art rules. It also offers marginal improvements against standard SCR. Although SCR bases its decisions on solid coalitions, which impose a rather strong requirement on groups of voters, the experiments demonstrate that this does not prevent the algorithm from making sound overall decisions.
Approval Ballots
Given the particularly large number of instances, the diversity of voter preferences and election sizes, and the widespread use of Pabulib [15] in the relevant literature, we use its datasets for the approval voting setting. However, as provided, they do not directly fit the setting for which our axiomatic guarantees for SCR hold, since Participatory Budgeting does not correspond to matroid constraints. We therefore transform each instance into a committee election. We do so by setting equal to the budget divided by the average project cost (rounded to the nearest integer). We then discard the project costs and treat each project as a candidate competing for one of the committee seats.
We compare SCR against Utilitarian Greedy Rule, MES, Greedy-PJR+, and Sequential PAV. We refer the reader to Section A.3 for the definitions of these rules.
Compared to the ranked setting (§ 6.1), the utilitarian performance of SCR deteriorates in the approval voting context. This is in line with the findings of § 5. The gap is particularly pronounced in larger instances, where both MES and seqPAV outperform SCR to a notable extent. On Exclusion Ratio and PJR+, SCR loses its dominant position but remains competitive with the other state-of-the-art proportional rules, maintaining consistent performance across all instance sizes. For EJR+, SCR underperforms relative to its fairness-oriented competitors, although it remains substantially closer to them than to the utilitarian method.
Conclusion
Our results show that SCR provides strong fairness guarantees with general feasibility constraints. It is polynomial-time computable in several practically relevant cases. Nevertheless the rule performs worse than other well-established rules for approval ballots. This formulates an interesting open question, which we elaborate on in Section A.1.
Acknowledgements The authors were supported by the European Union (ERC, PRO-DEMOCRATIC, 101076570). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.
Technical Appendix
The Modified Solid Coalition Refinement Rule
Both our theoretical results and empirical evaluation show that the Solid Coalition Refinement rule is weaker than the state-of-the-art proportional rules, in the case of approval ballots. A natural question is whether SCR can be modified to preserve its strong guarantees for ranked ballots while also satisfying stronger approval-based axioms.
One natural approach is to change the criterion used to select a refined solid coalition. For , let
Thus, contains the first positions in voter ’s ranking, including the entire indifference class at the boundary. Consequently, may exceed when the ranking contains ties. Instead of using , the rule could select, at each step, a refined solid coalition maximizing the following quantity:
This modification appears promising for two reasons: (i) For strict rankings, the modified rule coincides with the original SCR, so all our (axiomatic and algorithmic) results for strict rankings continue to apply. (ii) For approval committee elections, it coincides with the Greedy Justified Candidate Rule of [8], and therefore satisfies EJR+.
Unfortunately, the construction below shows that this modification loses its proportionality guarantees in the presence of weak orders. In particular, it fails generalized PSC, even for the Hare quota, in the committee election setting, hence it also fails Proportionality (Definition 3). Hence, while SCR performs sufficiently well for rankings, both strict and weak, but less well in the approval setting, the proposed modification performs well for both strict rankings and approval ballots, but not for weak rankings. Therefore, we view establishing a rule with strong guarantees across all three scenarios as the most important open question.
Let , and consider the committee elections setting with and 8 voters. Consider the following preferences, where candidates in the same colored box belong to the same indifference class; colors indicate successive rank positions:
| voters | preferences |
| 1, 3 | |
| 2 | |
| 4 | |
| 5 | |
| 6 | |
| 7 | |
| 8 |
Table 1.
Use a fixed tie-breaking order extending , where, for example, denotes the set .
A direct calculation gives the following refinement chains. At every arrow, the displayed pair indicates the set of voters in a solid coalition that maximizes and the corresponding value of :
Hence the final outcome is . Now consider , , and . Both voters rank uniquely first, so is a solid coalition that deserves one candidate according to both Droop and Hare quotas. Nevertheless, . Therefore the modified rule violates Proportionality.
Omitted Proofs
Proof of Theorem 1. Assume that satisfies generalized Droop-PSC and towards a contradiction say that violates Proportionality. Take the solid coalition that witnesses the violation. It holds that deserves candidates according to Definition 3 and . Then and we can pick with . Obviously, any with will give . Therefore, the first condition of Definition 3 does not hold for . As deserves candidates, it thus needs to hold that , which is equivalent to . With this, generalized Droop-PSC guarantees that . Taking in Definition 3 requires that , which completes the contradiction.
Assume that satisfies Proportionality and take a solid coalition such that . We will first show that deserves candidates. For this, consider any . If , then we pick any with towards satisfying Definition 3. Otherwise , which allows us to satisfy Definition 3 with the inequality . These two cases complete the proof that deserves candidates according to Definition 3. Therefore, Proportionality guarantees , as also required by generalized Droop-PSC.
Proof of Theorem 2. Assume that satisfies Proportionality and let be an arbitrary set of voters that deserve candidates according to PJR. Let . Then is a solid coalition. Moreover, the requirement of deserving candidates according to PJR coincides with that under Proportionality. Hence, the fact that satisfies Proportionality implies that . By the choice of , we have , and therefore, also satisfies PJR.
Proof of Theorem 3. Take an election such that for each inclusion-wise maximal . Let be an inclusion-wise maximal feasible outcome satisfying PJR. Towards showing that Proportionality is also satisfied, let be an arbitrary solid coalition deserving candidates in according to Definition 3. We consider two cases. First, if , then the group deserves candidates according to PJR, which guarantees . But , so Proportionality is also satisfied. Otherwise, if , then there exists a voter who has a non-approved candidate in , which inflates the to the whole set . As is imposed by taking in Definition 3, we now have , again satisfying Proportionality.
For the second part of the proof, assume that there exist two inclusion-wise maximal sets such that . Consider an election with voters, each approving a different candidate in . Let . We will show that satisfies PJR but not Proportionality.
According to PJR, a group of voters with does not deserve any candidate in , as taking would require them to find a feasible subset of candidates of at least 1 candidate in . A group consisting of a single voter who approves a candidate from also does not deserve any candidate, as when picking , by inclusion-wise maximality, there is no set that can be added to while preserving feasibility and also . Lastly, a group consisting of a single voter that approves a candidate from satisfies while doesn't deserve more than one as for we have and so one can't find a set of size 2 satisfying the corresponding requirement of PJR. Thus, satisfies PJR.
We now move to Proportionality. The solid coalition deserves candidates in . To show it, take an arbitrary . If , then the group can simply pick as the feasible set. Otherwise, we have . However, it also holds that , violating Proportionality.
Proof of Lemma 1.
We begin by assuming that each voter has an initial budget of 1 and that candidates are being bought using voters’ budget, each at a price of , under a payment scheme to be defined. In particular, for any , we will show the existence of a payment scheme that buys while satisfying the following:
(i.) no voter is ever left with a negative budget after a purchase, and
(ii.) for every voter and every solid coalition with and for which such that , then voter has spent money only on candidates in .
Before proving the existence of such a payment scheme, we first show that it is sufficient to establish the statement of the lemma. In particular, we assume, towards a contradiction, that a payment scheme satisfying conditions (i) and (ii) exists, and that after step of the rule there is a solid coalition such that and there exists with . This means that
In the payment scheme for the voters from had only paid for the candidates from (condition (ii)), which means that the voters from had to pay for the whole . Therefore they have to have paid at least which, by condition (i), contradicts Equation (1).
We now turn to proving the existence of a payment scheme satisfying conditions (i) and (ii). The proof proceeds by induction on . For we note that , no purchase is made and no voter spends anything. Therefore, condition (i) holds trivially, and condition (ii) holds vacuously since no voter has spent any money. Assuming that a valid payment scheme exists for , we show how to extend the payments to while still satisfying conditions (i) and (ii), by reasoning about how to pay for the inclusion of in , where is the -th candidate selected by the SCR rule.
At a step , we call a candidate electable as long as . Towards determining the payment scheme, consider first the case where there is no solid coalition with an electable candidate in and for which , i.e., the case where all solid coalitions are already represented in in proportion to their size. Then, we deduce the money for buying in an arbitrary way, while ensuring satisfaction of condition (i). This is possible since the voters’ total initial budget is sufficient to pay for candidates (and therefore also for candidates, as ), since . Moreover, it holds that , for each solid coalition with an electable candidate, so condition (ii) holds again vacuously.
Suppose now that there is a solid coalition with an electable candidate and for which , and let be the last such during the execution of the while loop of the rule (Step 4 in Algorithm 1). This is well defined, as one needs to be picked during the first refinement. By condition (ii) applied to , the voters from have only spent money on candidates from . Each such candidate costs , so the voters from have spent at most . Moreover, by definition, we have that and we have assumed that . By rearranging we get that . Therefore, the voters in have a remaining budget of at least , so they can pay for a candidate in a way that satisfies condition (i). In the payment scheme for we split the cost for buying arbitrarily between the voters from . At what follows we will show that this payment scheme for satisfies condition (ii) as well.
Towards a contradiction, let denote a solid coalition with for which such that and assume that some voter spent money on a candidate that does not belong to . Since , we infer from the induction hypothesis that voter has not spent money on candidates outside of during the first steps of SCR rule. Hence, voter spent money on candidate and . According to the defined payment scheme, only voters from spent money on the candidate , therefore for the solid coalition , meaning that weakly prefers each candidate in to any other candidate. Because it follows that . Note also that contains at least two electable candidates, namely and , so it was not the terminating coalition in the while loop. From the definition of , we know that the next solid coalition in the while loop, say had . But then the SCR rule would have selected the solid coalition instead, as , which contradicts the selection made by SCR, thereby proving the existence of the required payment scheme and concluding the proof.
Proof of Lemma 2.
We prove the result by induction on . Recall that, according to Definition 3, a solid coalition deserves candidates in if for every either there exists a set with such that or the following inequality holds:
For , we have . Consider the set . For this, the second condition becomes , which does not hold for any . Therefore, any solid coalition that deserves candidates in must satisfy the first condition: there exists with and . Setting immediately gives the desideratum, since and .
We now move to the case of and we assume that the statement holds for . Hence, there exists a set such that and . Based on this, we need to show that there exists a set such that and . Let be the candidate in . At what follows, we will make use of the following observation from Masarík et al. [25].
Lemma 3. For a matroid family , for all feasible sets , and () such that , there exists such that .
If then Lemma 3 says that there exists a candidate such that . This means we can take .
Now, say that . Then, if we can simply use . On the other hand, say that . Take and consider the answer of to . We have that . The function is increasing, so:
By the definition of , the denominator on the right satisfies , giving:
Since , the induction hypothesis , together with , implies that . Consequently, had an electable candidate. This means that we can apply Lemma 1 to get a contradiction with (2). In turn, it cannot be the case that . Thus, as deserves candidates, there needs to exist with such that . From Definition 5 we get that there exists the .
Proof of Theorem 5.
Given family of constraints , as it is not a matroid, there exist two sets such that and for all . Say that . Consider the instance where a set of voters ranks all candidates in tied and above the remaining candidates, while all other voters rank tied at the top and the rest below, also tied. This construction is identical to the one used in [25] for which that Phragmén doesn’t satisfy PJR for non-matroid families of constraints, in the approval setting. Instead, we apply SCR to the instance.
Let us first prove that, at every step of SCR, as long as there exists an electable candidate , that is, a candidate satisfying , we have . We prove this by induction on . For , we have , so the claim holds trivially. For , assume that there exists a candidate such that and . We note that for a fixed set , a solid coalition has strictly lower underrepresentation value than a solid coalition with . Moreover, there are two families of voter maximal solid coalitions:
a coalition for any ,
a coalition for any such that .
To determine how SCR operates on the proposed instance we compute underrepresentation values as follows:
Which means that during the first iteration of the while loop, the rule will pick a coalition for some , as Step 5 ensures that . Therefore, a candidate from will be elected in this round, which proves that . Consequently, the outcome of SCR contains no candidate from . Indeed, after all candidates from have been included in the committee , we have for every candidate , since for all , by construction.
We now show that the solid coalition deserves candidates in the outcome. Consider any . If , then we can take , and immediately obtain a set with such that . Otherwise, if , then we have the following:
Since was arbitrary, it proves that the coalition deserves candidates in any outcome. Nevertheless, we have , which shows that SCR fails Proportionality.
Proof of Theorem 6.
Assume that we have some fixed , and we want to find such that is a solid coalition that maximizes the underrepresentation value. We define as the set of voters who have no voter from ranked strictly above any candidate from , i.e. they have on top. We first note that, in the approval voting setting, for any solid coalition the corresponding periphery is independent of , namely either or . Therefore, each refinement step for a set needs to compute underrepresentation values for two types of candidate sets: (i) singleton sets, which lead to immediate election and thus termination of the refinement process, and (ii) sets that exclude exactly one candidate from the current set—yielding in total only polynomially many possibilities.
It remains to show that the corresponding maximization of the underrepresentation value (Step 6 of Algorithm 1) can also be carried out in polynomial time. We do so by reducing it to the problem of deciding whether there exists a solid coalition such that . Notice that there are only possible values of , since the underrepresentation value is determined by a fraction whose numerator can take values and whose denominator can take values. We define an auxiliary function as and we note that
Therefore, it holds that if and only if . Moreover, the function is submodular. To show this, consider , and , then
Overall, in each iteration of the rule, we determine either by setting or for every available candidate , and then aim to find a suitable set ; among the considered solid coalitions we pick the one maximizing the underrepresentation value. For this, we consider all possible values of , or apply a binary search over them. For each considered value of , we iterate over all candidate sets defined above and introduce a function to check whether there exists a set such that . We then fix the solid coalition corresponding to a set that satisfies this condition for the maximum possible value of .
Proof of Theorem 7.
Given an election , let denote the maximum number of tied candidates in any preference level of any voter. We first present an algorithm that is FPT with respect to , and then refine it to obtain an algorithm that is FPT with respect to the maximum number of tied candidates in all but the last preference levels.
To solve the problem of determining the solid coalition that maximizes the underrepresentation value (Step 6 of Algorithm 1), it is enough to consider the sets that are on top of the ranking of at least one voter; these can be at most . In line with the proof of Theorem 6, we will check whether or not there exists a solid coalition such that . Again, it is enough to iterate over the pre-computed list of possible sets . We define as the set of voters who have no voter from ranked strictly above any candidate from , i.e. they have on top, and then introduce the auxiliary function as . Again, if and only if and is submodular.
Now, let denote the maximum number of tied candidates in any non-last preference level of any voter. We can then solve the problem of determining the solid coalition that maximizes the underrepresentation value by considering two families of sets : (i) those appearing at the top of the ranking of at least one voter, without including the bottom preference level, and (ii) those containing at least one candidate from the bottom preference level of some voter. For the first case, we proceed exactly as in the parameterization with respect to . In the second case, we have , making it analogous to the case considered in the proof of Theorem 6, and introducing only an additional number of sets to consider.
Proof of Theorem 8.
We denote by the strict preference relation between alternatives in the order submitted by voter . For the first part of the theorem, we construct the family of all solid coalitions that need to be considered towards solving the maximization problem in Step 6 of Algorithm 1. To do so, we first iterate over all possible pairs such that ; the set serves as a possible (inclusion-wise) upper bound for the periphery. Having fixed the sets and , we compute a set of voters such that . Observe that is the maximal set of voters such that is a solid coalition satisfying , and, for the specified pair only a single solid coalition, namely , needs to be examined. In turn, the maximization function of the underrepresentation value needs to be employed over a family of size bounded by .
We now move to the second part of the theorem for which we will prove that the maximization problem in Algorithm 1 can be solved in time . We first observe that for a group of voters and such that and both and are solid coalitions, it holds that . This comes from the fact, that we can express the periphery solely in terms of and . In particular, , where is the -th candidate on voter ranking, breaking ties arbitrarily.
We will show that can solve the maximization problem by first iterating through all and then by all possible sizes of . For each such and a possible size we present a procedure to determine if there exists a set of candidates such that
(i) ,
(ii) is a solid coalition,
(iii) ,
(iv) .
Due to the previous observation, if multiple sets exist that satisfy these conditions, all of which will result in the same underrepresentation value. Therefore, it is sufficient to construct only one of them. If two candidates belong to the same indifference class for a voter we write . Towards constructing a suitable set , we define the following sets of candidates:
All candidates from the set will have to be included in the constructed set . To argue that this is the case, focus on some voter . If she is a part of a solid coalition with , then it needs to be the case that , as the set has to be on top of the ranking, and to guarantee that satisfies condition (ii), we need to check that the set is on top of the ranking of every voter from . Similarly, candidates from should not be included in . The condition (i) additionally requires that . Further, the condition (iii) requires that .
After determining that , we need to fill the remaining spots. We do that, by adding some candidates from the set . We prioritize electable candidates, towards satisfying condition (iv). At the end, we again verify if condition (iv) holds.
If any of the above checks fails, there cannot exist a set that satisfies all the introduced constraints. If the construction was successful, we add the solid coalition to a list of coalitions for consideration. This scheme allows us to construct necessary coalitions for the maximization problem arising at Algorithm 1. The complexity of the algorithm with this subprocedure is . This comes from the iterations in the outer loops, an additional cost for determining the sets and , and up to refinements for each of the candidates to be potentially elected. Overall, the running time is FPT with respect to the number of voters.
Proof of Theorem 9.
Let and . Consider an election with and . We introduce two groups of voters, with approval ballots defined as follows:
We denote the set of voters of the first group as and the set of voters of the second as .
We will show that the SCR rule elects as the winning committee. Let and assume that the candidates have already been elected. Taking ties into account, there are two candidates under consideration for election, and . We now consider two cases.
If , then the maximum underrepresentation value that can be achieved with respect to the candidate is , to be denoted for simplicity by . Note that this value is strictly greater than . For the underrepresentation value with respect to the candidate , to be denoted for simplicity by , consider the group of voters with of them approving some candidate that already have been elected. Then the underrepresentation value is , which is maximal for .
We want to show that . Equivalently, we want to show that .
We first claim that . This is true because , where the last inequality follows from .
Consider the function , for . It holds that , . Hence, has its maximum at . Moreover, . Therefore, .
For the second case of , every voter from already has a satisfaction with respect to one candidate, which leads to for any ; we denote it by . Regarding , we also compute the underrepresentation value, to be denoted by and for this we note that only voters from approve . The highest underrepresentation values for these candidates are achieved by groups and , respectively. Therefore, we need to show that
First, we claim that . This holds because and , so . We want to prove that , or, equivalently, that . Given that , we have .
Consequently, in both cases, the candidate will be elected. We also have to check the underrepresentation value arising from the case where a group of voters ranks a candidate at the bottom of their ranking, i.e., disapproves of , and may therefore contribute to refining the examined set of candidates to . In this case, is necessarily a subset of either or , and therefore the corresponding underrepresentation ratio is no larger than the ones already computed.
By induction, we get that the SCR rule will select the committee . To conclude the proof, observe that , and for each we have .
Proof of Theorem 10.
In the construction of Theorem 9, each voter in the group approves a different candidate , and . Moreover, each voter in obtains a satisfaction of 1 from the outcome of SCR, while deserving . Therefore, if the size of could be increased while keeping the satisfaction of its voters bounded by one, the resulting proportionality degree would decrease. To this end, let be partitioned into groups such that the -th group has size equal to and its members approve candidate , as well as enough candidates from the set so that the cohesiveness of can only be limited by its size. We fix the committee size and formulate the problem of maximizing the size of —which in turn yields an upper bound on the proportionality degree of SCR—as a linear program.
Here, the variables represent the fraction of voters in relative to the entire electorate, so that . We have to ensure that the candidate elected at step is , which is guaranteed by the last inequality. The left-hand side captures the underrepresentation value with respect to candidate , who is supported by all voters in as well as by some voters from which amount to an fraction of the voters of the electorate. The right-hand side captures the underrepresentation value with respect to candidate , who is supported by all voters in that have not yet received a representative, together with those groups whose representative has already been selected. The third constraint ensures that the candidates are selected in order of increasing index. In particular, the first selected candidate is the one supported by the largest fraction of voters from , the second selected candidate is the one supported by the second-largest fraction, and so on. Solving the program for small values of already suggests a substantially stronger upper bound that is less than , as the following plot demonstrates.

Figure 1 (PDF p. 19).
Additional Findings and Details
We start by noting that SCR might produce outcomes that are undesirable from a basic efficiency perspective, even in simple instances, specifically, outcomes that are not Pareto optimal [21].
Definition 7. Let be a committee election under approval ballots. An outcome is Pareto dominated by an outcome if for each voter it holds that while for at least one voter the inequality is strict. An outcome is Pareto optimal if it is not Pareto dominated by any feasible outcome.
This result is not surprising, especially in light of the recent result by Dong [11]. Since SCR is polynomial-time computable and satisfies PJR in approval committee elections, it cannot also satisfy Pareto optimality unless .
Our result, however, is unconditional. Moreover, the same instance illustrates the difference between the sequential decisions of seqPAV and SCR. While both iteratively select candidates based on the representation achieved by previous selections, seqPAV tracks individual voters’ satisfaction, whereas SCR evaluates solid coalitions through their collective periphery. Consequently, a voter may be considered represented through their coalition even if they do not individually enjoy the same satisfaction, and this explains how SCR can fail Pareto optimality.
Theorem 11. The outcome of the SCR rule is not always Pareto optimal, even for approval committee elections.
Proof. Consider an approval committee election with , , and the following 14 voters:
| Group | Number of voters | Approval set |
| 5 | ||
| 3 | ||
| 3 | ||
| 2 | ||
| 1 |
Table 1 (PDF p. 20).
We show that SCR returns which is Pareto dominated by . Recall that, under approval preferences, a voter solidly supports a nonempty set if and only if or . Moreover, if every voter in a solid coalition approves every candidate in , then . Otherwise, .
The following table gives the maximum value of over all nonempty solid coalitions , for each nonempty proper subset of , at the two partial outcomes that occur in the execution. A dash means that no nonempty group solidly supports .
| 8 | ||
| 5 | ||
| 7 | ||
| 7 | ||
| – | – | |
| 5 | ||
| 4 | ||
| 2 | 2 | |
| 4 | ||
| 1 | ||
| 7 | ||
| 7 | ||
| 9 | ||
| 6 |
Table 2.
Initially, and . Since , the unique maximizing refinement is . Therefore, SCR first replaces by . Notice that is not eligible, since a refinement must be a proper subset of the current set . The nonempty proper subsets of the new are . Thus, the unique maximizing refinement is , and SCR elects .
Consider now the second round, where and . As shown in the table, the unique maximizing refinement is . Therefore, SCR elects and returns .
We conclude by noting that, on the same instance, sequential PAV also uniquely elects first. After electing , the marginal scores are
Therefore, sequential PAV uniquely elects next and returns , rather than the SCR outcome . The difference is that sequential PAV adds the half-weight contributions of the three already represented voters in to the four unrepresented supporters of , whereas SCR evaluates these supporters through a common coalition-level denominator. Notice also that is Pareto optimal on this instance: any committee Pareto dominating it would have to give the voters in two approved winners, and hence would have to contain both and . ∎
The remaining of this section is devoted to empirical findings and details. In § 6 we analyzed the -Borda and the Utilitarian Greedy algorithms which select the outcome
where and respectively. For -Borda, we assumed that voters get a utility of 0 from their unranked candidates, i.e., those positioned last, and indicates the position of in the ranking of .
The Method of Equal Shares (MES) proceeds through a sequence of rounds. In approval-based committee elections, each voter is assigned a virtual budget , initialized to , and every candidate is assumed to have unit cost. In each round, we consider the candidates that have not yet been elected and whose approving voters collectively have enough remaining budget to cover the cost of the candidate. More formally, for a candidate and a parameter , we say that is -affordable if
Among all candidates that are -affordable for some value of , the one with the smallest such is selected and added to the committee. The virtual budgets of its supporters are then updated: . The process terminates when there is no -affordable candidate for any value of .
Sequential PAV (seqPAV) is a polynomial time computable variant of Proportional Approval Voting that constructs the committee sequentially. In each iteration, it selects the candidate that maximizes the marginal increase in voters’ total satisfaction, where a voter’s satisfaction from receiving multiple approved candidates follows a harmonic sequence. We also analyzed EAR and STV for the setting of ranked ballots. We present the corresponding pseudocodes as Algorithm 2 and Algorithm 3.
for do
while do
for do
return
Algorithm 2: The pseudocode of the Expanding Approvals Rule.
while do
if then
for do
else
return
Algorithm 3: The pseudocode of the Single Transferable Vote rule.
We note that both EAR and STV have nuances on the quota used and how the cost is divided between the voters. As we said in the main text, we use Add1 completion, meaning that we iteratively decrease the quota as long as the rule returns a feasible outcome, trying to find minimal quota for which the rule returns a feasible committee. More precisely, in iteration we use quota . We stop at the first iteration the rule returns a committee of size greater than and use the committee from the previous iteration. We also considered the completion method that slightly increases voters’ utilities for non-approved projects (the so-called Eps method by Faliszewski et al. [15]), but it resulted in inferior performance for these rules. In both of the rules, when a candidate is elected, the quota needs to be paid by its supporters. We follow the recommendation of Aziz and Lee [2] of using uniform fractional reweighting.
The instances from Pabulib are partitioned into four groups of approximately equal size. In particular, our analysis covers the 410 instances from the library that satisfy and after the transformation to committee elections described above. For the Scottish local elections dataset, we note that a value of is provided for each instance, and we use these values in our experiments.
In what follows, we present the CDFs of the analyzed metrics across the two datasets used, which give a more nuanced and complete picture of the relationship among the considered rules; see Figure 3 and Figure 5. We observed substantial similarities between the outcomes of the examined rules in the ranked-ballot setting (Scottish local elections dataset), likely due to the small size of the instances. In contrast, such similarities do not appear in the approval voting setting; see Figure 2. For this reason, for the ranked-ballot setting, we additionally report CDFs restricted to instances where the considered rules produce different outcomes Figure 4, allowing for a more informative comparison.

Figure 2. Similarity of outcomes between the considered rules, in the ranked and approval setting, respectively.

Figure 3. CDFs of the analyzed metrics for ranked ballots.

Figure 4. CDFs of the analyzed metrics for ranked ballots, restricted to instances where the considered rules return different committees.

Figure 5. CDFs of the analyzed metrics for approval ballots.
For the ranked-ballot setting, the Utilitarian score clearly differentiates the rules. EAR achieves the best performance, followed by STV, while both variants of SCR perform similarly and slightly worse. For Exclusion Ratio, STV performs best. EAR and SCR-Truncated achieve similar results, with slightly different characteristics: SCR-Truncated performs slightly better on average, but exhibits a heavier tail. SCR-Full performs worse than the other proportional rules, while -Borda is, as expected, the worst-performing rule. For Rank-EJR+, STV, SCR-Truncated and EAR achieve the best results, while SCR-Full performs worse. Again, -Borda is clearly the worst-performing rule. The PSC value is dominated by SCR-Truncated, followed by SCR. We note, however, that these rules are specifically designed to optimize this metric. STV performs next, followed by EAR, which in turn outperforms -Borda. Finally, Local Stability is again best achieved by STV and SCR-Truncated, followed by SCR and EAR, although the differences between the latter two rules are very small. -Borda is again significantly worse.
For the approval voting setting, the Utilitarian score is maximized by MES and SeqPAV. After a noticeable gap, Greedy-PJR+ follows, with SCR performing very closely behind. For Exclusion Ratio, all proportional rules achieve comparable performance, with the main difference being the substantially worse performance of the Utilitarian rule. For EJR+ value, MES, SeqPAV, and Greedy-PJR+ achieve the best results, followed by SCR, while the utilitarian rule performs the worst. Finally, as expected, Greedy-PJR+ achieves the best PJR+ performance, with the Utilitarian achieving the worst. The remaining rules perform similarly.
References
- [1]Academy of Motion Picture Arts and Sciences. Special rules for the best picture of the year award. https://www.oscars.org/sites/oscars/files/2026-05/99th%20Best%20Picture%20Rules.pdf, 2026. Accessed: 2026-07-23.
- [2]H. Aziz and B. E. Lee. The expanding approvals rule: Improving proportional representation and monotonicity. Social Choice and Welfare, 54(1):1–45, 2020.arxiv.org/abs/1708.07580
- [3]H. Aziz and B. E. Lee. Proportionally representative participatory budgeting with ordinal preferences. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 5110–5118, 2021.arxiv.org/abs/1911.00864
- [4]H. Aziz, M. Brill, V. Conitzer, E. Elkind, R. Freeman, and T. Walsh. Justified representation in approval-based committee voting. Social Choice and Welfare, 48(2):461–485, 2017.
- [5]H. Aziz, E. Elkind, P. Faliszewski, M. Lackner, and P. Skowron. The condorcet principle for multiwinner elections: From shortlisting to proportionality. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 84–90, 2017.arxiv.org/abs/1701.08023
- [6]H. Aziz, P. Lederer, D. Peters, J. Peters, and A. Ritossa. Committee monotonicity and proportional representation for ranked preferences. In Proceedings of the ACM Conference on Economics and Computation, pages 896–896, 2025.arxiv.org/abs/2406.19689
- [7]T. Bardal, M. Brill, D. McCune, and J. Peters. Proportional representation in practice: Quantifying proportionality in ordinal elections. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 13581–13588, 2025.
- [8]M. Brill and J. Peters. Robust and verifiable proportionality axioms for multiwinner voting. In Proceedings of the ACM Conference on Economics and Computation, pages 301–301, 2023.arxiv.org/abs/2302.01989
- [9]M. Brill, R. Freeman, S. Janson, and M. Lackner. Phragmén’s voting methods and justified representation. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 406–413, 2017.
- [10]Y. Cheng, Z. Jiang, K. Munagala, and K. Wang. Group fairness in committee selection. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 263–279, 2019.
- [11]C. Dong. Jointly satisfying pareto optimality and justified representation is np-hard in approval-based multi-winner voting, 2026. URL https://arxiv.org/abs/2609.08357.
- [12]H. R. Droop. On methods of electing representatives. Journal of the Statistical Society of London, 44(2):141–202, 1881.DOI
- [13]M. Dummett. Voting Procedures. Oxford University Press, 1984.
- [14]B. Fain, K. Munagala, and N. Shah. Fair allocation of indivisible public goods. In Proceedings of the ACM Conference on Economics and Computation, pages 575–592, 2018.arxiv.org/abs/1805.03164
- [15]P. Faliszewski, J. Flis, D. Peters, G. Pierczyński, P. Skowron, D. Stolicki, S. Szufa, and N. Talmon. Participatory budgeting: Data, tools and analysis. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 2667–2674, 2023.arxiv.org/abs/2305.11035
- [16]D. Halpern, G. Kehne, A. D. Procaccia, J. Tucker-Foltz, and M. Wüthrich. Representation with incomplete votes. Theory and Decision, pages 1–40, 2026.
- [17]S. Janson. Phragmén’s and thiele’s election methods. Technical report, 2016.arxiv.org/abs/1611.08826
- [18]Z. Jiang, K. Munagala, and K. Wang. Approximately stable committee selection. In Proceedings of the 52nd Symposium on Theory of Computing (STOC-2020), pages 463–472, 2020.arxiv.org/abs/1910.14008
- [19]L. Kellerhals and J. Peters. Proportional fairness in clustering: A social choice perspective. Advances in Neural Information Processing Systems, 37:11299–11317, 2024.arxiv.org/abs/2310.18162
- [20]S. Kraiczy, G. Papasotirოპულoulos, G. Pierczyński, and P. Skowron. Proportional committee elections with positive and negative votes. In Proceedings of the ACM Conference on Economics and Computation, 2026. Forthcoming.DOI
- [21]M. Lackner and P. Skowron. Multi-Winner Voting with Approval Preferences. Springer, 2023.
- [22]P. Lederer. Proportional representation in rank aggregation. arXiv preprint, 2025. arXiv:2508.16177.arxiv.org/abs/2508.16177
- [23]P. Lederer, D. Peters, and T. Wąs. The squared kemeny rule for averaging rankings. In Proceedings of the ACM Conference on Economics and Computation, page 755, 2024.
- [24]E. Lindahl. Just taxation–a positive solution. In Classics in the Theory of Public Finance, pages 168–176. Springer, 1958.DOI
- [25]T. Masarík, G. Pierczyński, and P. Skowron. A generalised theory of proportionality in collective decision making. In Proceedings of the ACM Conference on Economics and Computation, pages 734–754, 2024.
- [26]I.-A. Mavrov, K. Munagala, and Y. Shen. Fair multiwinner elections with allocation constraints. In Proceedings of the ACM Conference on Economics and Computation, pages 964–990, 2023.
- [27]D. McCune. Monotonicity anomalies in scottish local government elections. Social Choice and Welfare, pages 69–101, 2024.
- [28]G. Papasotirოპულoulos and Z. Pishbin. Fairness in the multi-secretary problem. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 17188–17196, 2026.
- [29]G. Papasotirოპულoulos, S. Z. Pishbin, O. Skibski, P. Skowron, and T. Wąs. Method of equal shares with bounded overspending. In Proceedings of the ACM Conference on Economics and Computation, 2025.
- [30]D. Peters and P. Skowron. Proportionality and the limits of welfarism. In Proceedings of the ACM Conference on Economics and Computation, pages 793–794, 2020.arxiv.org/abs/1911.11747
- [31]J. Peters. Candidate monotonicity and proportionality for lotteries and non-resolute rules. Social Choice and Welfare, pages 1–15, 2025.
- [32]G. Pierczynski and P. Skowron. Core-stable committees under restricted domains. In International Conference on Web and Internet Economics, pages 311–329, 2022.arxiv.org/abs/2108.01987
- [33]S. Rey, F. Schmidt, and J. Maly. The (computational) social choice take on indivisible participatory budgeting. arXiv preprint, 2023. arXiv:2303.00621.
- [34]P. Skowron. Proportionality degree of multiwinner rules. In Proceedings of the ACM Conference on Economics and Computation, pages 820–840, 2021.arxiv.org/abs/1810.08799
- [35]P. Skowron. A general theory of proportionality with additive utilities. arXiv preprint, 2026. arXiv:2602.08504.
- [36]L. Sánchez-Fernández, E. Elkind, M. Lackner, N. Fernández García, J. A. Fisteus, P. Basanta Val, and P. Skowron. Proportional justified representation. Artificial Intelligence, 353:104503, 2026.
- [37]N. Tideman. The single transferable vote. Journal of Economic Perspectives, 9(1):27–38, 1995.DOI
- [38]Wikipedia. List of participatory budgeting votes. https://en.wikipedia.org/wiki/List_of_participatory_budgeting_votes, 2026. Accessed: 2026-07-23.
- [39]Wikipedia. Ranked voting. https://en.wikipedia.org/wiki/Ranked_voting, 2026. Accessed: 2026-07-23.
- [40]D. Woodall. Properties of preferential election rules. Voting Matters, pages 8–15, 1994.
- [41]J. C. Yang, C. I. Hausladen, D. Peters, E. Pournaras, R. Hnggli Fricker, and D. Helbing. Designing digital voting systems for citizens: Achieving fairness and legitimacy in participatory budgeting. Digital Government: Research and Practice, 5(3):1–30, 2024.