betaFeedback

WorksComputer 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 α\alpha-fraction of the electorate has sufficiently cohesive preferences, it should influence approximately an α\alpha-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 xx is a superset of its outcome for a committee size yy for any x>yx > y, 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 {ci,ci′:i∈[m]}\{c_i,c_i' : i \in[m]\}, subject to the constraint that exactly one candidate from each pair {ci,ci′}\{c_i,c_i'\} must be selected. Suppose that 51% of the voters rank c1≻c2≻⋯≻cm≻c1′≻c2′≻⋯≻cm′c_1 \succ c_2 \succ\cdots\succ c_m \succ c_1' \succ c_2' \succ\cdots\succ c_m', whereas the remaining 49% rank c1′≻c2′≻⋯≻cm′≻c1≻c2≻⋯≻cmc_1' \succ c_2' \succ\cdots\succ c_m' \succ c_1 \succ c_2 \succ\cdots\succ c_m. 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 c1≻c1′≻c2≻c2′≻⋯≻cm≻cm′c_1 \succ c_1' \succ c_2 \succ c_2' \succ\cdots\succ c_m \succ c_m'. 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 {ci}i∈[m]\{c_i\}_{i\in[m]}, because, once cic_i is selected, its counterpart ci′c_i' 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 kk 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 E=(C,N,F,R)E = (C, N, \mathcal{F}, \mathcal{R}), where C={c1,c2,…,cm}C = \{c_1, c_2, \ldots, c_m\} is a set of mm candidates, N={1,2,…,n}N = \{1, 2, \ldots, n\} is a set of nn voters, F⊆2C\mathcal{F} \subseteq2^C is a nonempty family of feasible outcomes, and R=(⪰1,⪰2,…,⪰n)\mathcal{R} = (\succeq_1, \succeq_2, \ldots, \succeq_n) is a profile of weak orders over CC, representing voters’ preferences. If the feasible outcomes consist of exactly sets of size at most kk, for some integer kk, 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 AiA_i the upper tier of voter ii. A selection rule, or simply a rule SS is a function mapping an election E=(C,N,F,R)E = (C, N, \mathcal{F}, \mathcal{R}) to an outcome S(E)=W∈FS(E) = W \in\mathcal{F}.

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 E=(C,N,F,R)E = (C, N, \mathcal{F}, \mathcal{R}), a solid coalition of EE is a pair (S,X)(S, X), where S⊆NS \subseteq N and X⊆CX \subseteq C, such that every voter in SS weakly prefers each candidate in XX to each candidate in C∖XC \setminus X.

Towards a proportionality axiom, we require that any solid coalition (S,X)(S, X) is represented in the outcome by candidates that the voters in SS find acceptable as substitutes for those in XX. Specifically, a candidate c∉Xc \notin X is an acceptable substitute if at least one voter in SS ranks cc no worse than some candidate in XX. Following the terminology of Aziz and Lee [2], we capture this via the periphery of XX with respect to SS: the set of all candidates that some voter in SS considers at least as good as some candidate in XX. This relaxation of the set satisfaction of voters in SS is necessary for ensuring satisfiability of the corresponding axiom [2].

Definition 2. Given an election E=(C,N,F,R)E = (C, N, \mathcal{F}, \mathcal{R}), and a solid coalition (S,X)(S, X) we define periph⁡(S,X)={c∈C:∃i∈S,c′∈X such that c⪰ic′}\operatorname{periph}(S, X) = \{c \in C : \exists i \in S, c' \in X \text{ such that } c \succeq_i c'\}.

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 (S,X)(S, X) is ℓ\ell-represented in the outcome if at least ℓ\ell members of periph⁡(S,X)\operatorname{periph}(S, X) appear in WW, capturing the idea that acceptable substitutes count toward the coalition’s share. The subtle challenge is deciding when SS has a legitimate claim to ℓ\ell 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 ℓ\ell representatives to SS could block other voters from candidates they care about, due to feasibility constraints. Take any T⊆WT \subseteq W. Although arbitrary, it intuitively represents the candidates over which the voters in N∖SN \setminus S can exercise their influence. If TT and ℓ\ell candidates from XX can coexist in a feasible outcome, there is no conflict and the claim of SS can be guaranteed. If they cannot coexist, the claim remains legitimate as long as SS is proportionally large enough to outweigh the rest—formally, that the claim of SS to ℓ\ell candidates is stronger, relative to its size, than the remaining voters’ claim to TT. This is captured by ∣S∣n>ℓ∣T∣+ℓ\frac{|S|}{n} > \frac{\ell}{|T|+\ell}, which is equivalent to ∣S∣ℓ>n−∣S∣∣T∣\frac{|S|}{\ell} > \frac{n-|S|}{|T|}, whenever ∣S∣<n|S| < n and T≠∅T \ne\varnothing. A solid coalition deserves ℓ\ell candidates when no set TT 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 E=(C,N,F,R)E = (C, N, \mathcal{F}, \mathcal{R}), we say that a solid coalition (S,X)(S, X) deserves ℓ\ell candidates in WW if for every T⊆WT \subseteq W either there exists a set X′⊆XX' \subseteq X with ∣X′∣≥ℓ|X'| \ge\ell such that X′∪T∈FX' \cup T \in\mathcal{F} or ∣S∣n>ℓ∣T∣+ℓ\frac{|S|}{n} > \frac{\ell}{|T|+\ell}. We say that an outcome W∈FW \in\mathcal{F} satisfies Proportionality if for every positive integer ℓ\ell and every solid coalition (S,X)(S, X) that deserves ℓ\ell candidates in WW we have ∣periph⁡(S,X)∩W∣≥ℓ|\operatorname{periph}(S, X) \cap W| \ge\ell.

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 WW as long as for every natural number ℓ\ell and for every solid coalition (S,X)(S, X) with ∣S∣>ℓnk+1|S| > \frac{\ell n}{k+1}, it holds that WW contains at least min⁡(ℓ,∣X∣)\min(\ell, |X|) candidates from periph⁡(S,X)\operatorname{periph}(S, X).

Theorem 1. Given a committee election under ranked voting E=(C,N,{W′⊆C:∣W′∣≤k},R)E = (C, N, \{W' \subseteq C : |W'| \le k\}, \mathcal{R}), an outcome W⊆CW \subseteq C with ∣W∣=k|W| = k satisfies generalized Droop-PSC if and only if WW satisfies proportionality in EE.

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 E=(C,N,F,A)E = (C, N, \mathcal{F}, \mathcal{A}) and an outcome W∈FW \in\mathcal{F}, we say that a group of voters S⊆NS \subseteq N deserves ℓ\ell candidates in WW if for each set T⊆WT \subseteq W either there exists a set X′⊆⋃i∈SAiX' \subseteq\bigcup_{i \in S} A_i with ∣X′∣≥ℓ|X'| \ge\ell such that T∪X′∈FT \cup X' \in\mathcal{F} or the following inequality holds: ∣S∣n>ℓ∣T∣+ℓ\frac{|S|}{n} > \frac{\ell}{|T|+\ell}. We say that an outcome W∈FW \in\mathcal{F} of an election E=(C,N,F,A)E = (C, N, \mathcal{F}, \mathcal{A}) satisfies Proportional Justified Representation if for every group of voters S⊆NS \subseteq N that deserves ℓ\ell candidates we have ∣(⋃i∈SAi)∩W∣≥ℓ\left|\left(\bigcup_{i \in S} A_i\right) \cap W\right| \ge\ell.

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 E=(C,N,F,A)E = (C, N, \mathcal{F}, \mathcal{A}), if an outcome W∈FW \in\mathcal{F} satisfies Proportionality then WW satisfies PJR in EE.

Theorem 3. Given a family of feasible outcomes F\mathcal{F}, if each inclusion-wise maximal set W∈FW \in\mathcal{F} is the same size, then for each election E=(C,N,F,A)E = (C, N, \mathcal{F}, \mathcal{A}) and an inclusion-wise maximal outcome WW satisfying PJR, WW also satisfies Proportionality. If there exist two inclusion-wise maximal outcomes with different sizes, then there exists an election E=(C,N,F,A)E = (C, N, \mathcal{F}, \mathcal{A}) and an inclusion-wise maximal outcome WW 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 (S,X)(S, X) under the current committee WW quantifies how far SS is from being proportionally represented: the higher the value, the stronger the claim of SS to the next seat. This value is defined as ρ(W,S,X):=∣S∣∣W∩periph⁡(S,X)∣+1\rho(W, S, X) := \frac{|S|}{|W \cap\operatorname{periph}(S,X)|+1}. When the most underrepresented coalition is (S,X)(S, X), the rule adds a candidate from X∖WX \setminus W. 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 XX, narrowing the set down until it contains only one candidate not in WW, which is then added to the committee. We denote the committee formed after a number kk of selections of candidates by WkW_k.

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 arg max⁡\operatorname{arg\,max} 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 F\mathcal{F}, we define F′\mathcal{F}' to consist of all sets that can be extended to some set in F\mathcal{F}. By construction, F′\mathcal{F}' is downward closed and can then be used within the SCR rule. Then, any outcome returned by SCR is already feasible under F\mathcal{F} since SCR returns an inclusion-wise maximal set.

W←∅, C′←{c∈C:{c}∈F}while C′≠∅ doD←Cwhile ∣D∩C′∣>1 doΦ(R,W,D)←{(S,X):(S,X) is a solid coalition, X⊊D, ∣X∩C′∣≥1}(S∗,X∗)←arg max⁡(S,X)∈Φ(R,W,D) ∣S∣∣W∩periph⁡(S,X)∣+1D←X∗W←W∪(D∩C′)C′←{c∈C∖W:W∪{c}∈F}return W\begin{aligned} W &\leftarrow\varnothing,\ C' \leftarrow\{c \in C : \{c\} \in\mathcal{F}\}\\ \textbf{while } C' &\ne\varnothing\ \textbf{do}\\ &\quad D \leftarrow C\\ &\quad\textbf{while } |D \cap C'| > 1\ \textbf{do}\\ &\qquad\Phi(\mathcal{R},W,D) \leftarrow\{(S,X) : (S,X)\text{ is a solid coalition},\ X \subsetneq D,\ |X \cap C'| \ge1\}\\ &\qquad(S^*,X^*) \leftarrow\underset{(S,X)\in\Phi(\mathcal{R},W,D)}{\operatorname{arg\,max}}\ \frac{|S|}{|W\cap\operatorname{periph}(S,X)|+1}\\ &\qquad D \leftarrow X^*\\ &\qquad W \leftarrow W \cup(D \cap C')\\ &\quad C' \leftarrow\{c \in C \setminus W : W \cup\{c\} \in\mathcal{F}\}\\ \textbf{return }&W \end{aligned}

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 F\mathcal{F} is a matroid if for each X,Y∈FX,Y \in\mathcal{F} such that ∣X∣<∣Y∣|X| < |Y|, there exists c∈Y∖Xc \in Y \setminus X such that X∪{c}∈FX \cup\{c\} \in\mathcal{F}.

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 E=(C,N,F,R)E=(C,N,\mathcal{F},\mathcal{R}) where F\mathcal{F} is a matroid, SCR(E)SCR(E) 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 E=(C,N,F,R)E=(C,N,\mathcal{F},\mathcal{R}), where F\mathcal{F} is a matroid, after each step kk of the SCR rule, for every solid coalition (S,X)(S,X), if there exists c∈X∖Wk−1c \in X \setminus W_{k-1} such that {c}∪Wk−1∈F\{c\} \cup W_{k-1} \in\mathcal{F} then ρ(Wk,S,X)≤nk+1\rho(W_k,S,X) \le\frac{n}{k+1}.

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 E=(C,N,F,R)E=(C,N,\mathcal{F},\mathcal{R}), where F\mathcal{F} is a matroid, let WW be the outcome of SCR in EE. After each step kk of the SCR rule, for every solid coalition (S,X)(S,X) that deserves ℓ\ell candidates in WW, there exists a set Xk⊆X∖WkX_k \subseteq X \setminus W_k such that ∣Xk∣+∣Wk∩periph⁡(S,X)∣≥ℓ|X_k| + |W_k \cap\operatorname{periph}(S,X)| \ge\ell and Xk∪Wk∈FX_k \cup W_k \in\mathcal{F}.

Lemma 2 guarantees that at every step kk, for each solid coalition (S,X)(S,X) deserving ℓ\ell candidates in the outcome of the rule (in the sense of Definition 3), there exists a set XkX_k that can still be elected and electing it will result in (S,X)(S, X) being ℓ\ell-represented. From this, Theorem 4 follows directly, because, when the rule terminates, no further feasible candidate can be added, meaning that (S,X)(S, X) is already ℓ\ell-represented. □\square

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 F\mathcal{F}, there is an election E=(C,N,F,R)E = (C, N, \mathcal{F}, \mathcal{R}), where SCR(E)SCR(E) 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 nn. 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 (S,X)(S, X), we distinguish two cases. In the first, X⊆⋂i∈SAiX \subseteq\bigcap_{i\in S} A_i. For this, we show that the periphery of XX with respect to SS is not affected by the size or the members of XX, so the rule only needs to consider singleton sets XX, since their supersets would yield the same underrepresentation value. This makes the refinement step unnecessary, as any refinement sequence resulting in electing a candidate cc can skip the intermediate refinements. The second case is when there exists some voter i∈Si \in S such that X⊈AiX \nsubseteq A_i. Then we have periph⁡(S,X)=C\operatorname{periph}(S, X) = C, so again this does not depend on the set XX. 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 (S,X)(S, X) such that every member of SS includes all members of XX 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 mm. Parameterizing with respect to nn 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 ℓ−1\ell- 1, of Phragmén is ℓ−1/2\ell- 1/2 and of MES is between ℓ−1/2\ell- 1/2 and ℓ+1/2\ell+ 1/2 [21].

Definition 6. Let EE be a committee election under approval ballots. A group of voters VV is ℓ\ell-cohesive in EE if ∣V∣≥ℓn/k|V| \ge\ell n/k and all voters in VV approve at least ℓ\ell common candidates. Fix a function f:N→Rf : \mathbb{N} \to\mathbb{R}. A rule S\mathcal{S} for committee elections under approval ballots has proportionality degree ff if, for every election EE and every ℓ\ell-cohesive group of voters VV, the outcome W=S(E)W = \mathcal{S}(E) satisfies 1∣V∣∑i∈V∣Ai∩W∣≥f(ℓ)\frac{1}{|V|}\sum_{i \in V}|A_i \cap W| \ge f(\ell).

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 kk.

Theorem 9. For each k∈N≥4k \in\mathbb{N}_{\ge4}, there exists an ℓ∈N+\ell\in\mathbb{N}_+ and an approval committee election E=(C,N,{W′⊆C:∣W′∣≤k},A)E = (C, N, \{W' \subseteq C : |W'| \le k\}, \mathcal{A}) with an ℓ\ell-cohesive group of voters S⊆NS \subseteq N such that ∣Ai∩SCR(E)∣≤ℓ⋅1k−1|A_i \cap SCR(E)| \le\ell\cdot\frac{1}{\sqrt{k}-1}, ∀i∈S\forall i \in S.

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 kk 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 kk. 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 kk as Theorem 9 does.

Average values of the evaluated metrics for the outcomes produced by the considered rules

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 k≤400k \le400, there exists an ℓ∈N+\ell\in\mathbb{N}_{+} and an approval committee election E=(C,N,{W′⊆C:∣W′∣≤k},A)E = (C, N, \{W^\prime\subseteq C : \lvert W^\prime\rvert\le k\}, \mathcal{A}) with an ℓ\ell-cohesive group of voters S⊆NS \subseteq N such that ∣Ai∩SCR(E)∣≤ℓ⋅3k0.72\lvert A_i \cap SCR(E)\rvert\le\ell\cdot\frac{3}{k^{0.72}}, ∀i∈S\forall i \in S.

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: kk-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 (S,X)(S, X) only if all candidates in XX 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 kk 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 m−1m-1 points, the second-ranked candidate receives m−2m-2 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 kk-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 kk 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 kk 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 r∈{1,…,m}r \in\{1,\ldots,m\}, let

top⁡i(r)={c∈C:∣{c′∈C:c′≻ic}∣<r}.\operatorname{top}_{i}(r)=\{c\in C:|\{c^{\prime}\in C:c^{\prime}\succ_{i}c\}|<r\}.

Thus, top⁡i(r)\operatorname{top}_{i}(r) contains the first rr positions in voter ii’s ranking, including the entire indifference class at the boundary. Consequently, ∣top⁡i(r)∣|\operatorname{top}_{i}(r)| may exceed rr when the ranking contains ties. Instead of using ρ(W,S,X)\rho(W,S,X), the rule could select, at each step, a refined solid coalition maximizing the following quantity:

ρ^(W,S,X)=∣S∣1+max⁡i∈S∣W∩top⁡i(∣X∣)∣.\widehat{\rho}(W,S,X)=\frac{|S|}{1+\max_{i\in S}|W\cap\operatorname{top}_{i}(|X|)|}.

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 C={a,b,c,d,e}C=\{a,b,c,d,e\}, and consider the committee elections setting with k=4k=4 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:

voterspreferences
1, 3a∼b≻c≻d≻ea\sim b\succ c\succ d\succ e
2e≻b≻a∼c∼de\succ b\succ a\sim c\sim d
4d≻c∼e≻a∼bd\succ c\sim e\succ a\sim b
5c≻b≻a∼d∼ec\succ b\succ a\sim d\sim e
6a∼c≻b≻d∼ea\sim c\succ b\succ d\sim e
7a∼e≻b≻c∼da\sim e\succ b\succ c\sim d
8d≻c≻e≻b≻ad\succ c\succ e\succ b\succ a

Table 1.

Use a fixed tie-breaking order extending bcde≻tbabce≻tbabcd≻tbabc≻tbbce≻tbcde≻tbcd≻tbb≻tbc≻tbe≻tba≻tbdbcde\succ_{\mathrm{tb}}abce\succ_{\mathrm{tb}}abcd\succ_{\mathrm{tb}}abc\succ_{\mathrm{tb}}bce\succ_{\mathrm{tb}}cde\succ_{\mathrm{tb}}cd\succ_{\mathrm{tb}}b\succ_{\mathrm{tb}}c\succ_{\mathrm{tb}}e\succ_{\mathrm{tb}}a\succ_{\mathrm{tb}}d, where, for example, bcdebcde denotes the set {b,c,d,e}\{b,c,d,e\}.

A direct calculation gives the following refinement chains. At every arrow, the displayed pair indicates the set of voters SS in a solid coalition that maximizes ρ^\widehat{\rho} and the corresponding value of ρ^\widehat{\rho}:

W0=∅:C→ρ^=4S∗={2,4,5,8}bcde→ρ^=2S∗={2,5}bce→ρ^=2S∗={1,3}{b}.W_{0}=\varnothing:\quad C\xrightarrow[\widehat{\rho}=4]{S^{*}=\{2,4,5,8\}}bcde\xrightarrow[\widehat{\rho}=2]{S^{*}=\{2,5\}}bce\xrightarrow[\widehat{\rho}=2]{S^{*}=\{1,3\}}\{b\}.
W1={b}:C→ρ^=2S∗={2,4,5,8}bcde→ρ^=2S∗={4,8}cde→ρ^=2S∗={4,8}cd→ρ^=2S∗={5,6}{c}.W_{1}=\{b\}:\quad C\xrightarrow[\widehat{\rho}=2]{S^{*}=\{2,4,5,8\}}bcde\xrightarrow[\widehat{\rho}=2]{S^{*}=\{4,8\}}cde\xrightarrow[\widehat{\rho}=2]{S^{*}=\{4,8\}}cd\xrightarrow[\widehat{\rho}=2]{S^{*}=\{5,6\}}\{c\}.
W2={b,c}:C→ρ^=2S∗={2,7}{e}.W_{2}=\{b,c\}:\quad C\xrightarrow[\widehat{\rho}=2]{S^{*}=\{2,7\}}\{e\}.
W3={b,c,e}:C→ρ^=2S∗={1,3,6,7}{a}.W_{3}=\{b,c,e\}:\quad C\xrightarrow[\widehat{\rho}=2]{S^{*}=\{1,3,6,7\}}\{a\}.

Hence the final outcome is W={a,b,c,e}W = \{a,b,c,e\}. Now consider S={4,8}S = \{4,8\}, X={d}X = \{d\}, and ℓ=1\ell= 1. Both voters rank dd uniquely first, so (S,X)(S,X) is a solid coalition that deserves one candidate according to both Droop and Hare quotas. Nevertheless, ∣W∩periph⁡S(X)∣=∣{a,b,c,e}∩{d}∣=0<ℓ|W \cap\operatorname{periph}_{S}(X)| = |\{a,b,c,e\} \cap\{d\}| = 0 < \ell. Therefore the modified rule violates Proportionality.

Omitted Proofs

Proof of Theorem 1. Assume that WW satisfies generalized Droop-PSC and towards a contradiction say that WW violates Proportionality. Take the solid coalition (S,X)(S,X) that witnesses the violation. It holds that (S,X)(S,X) deserves ℓ\ell candidates according to Definition 3 and ∣W∩periph⁡(S,X)∣≤ℓ−1|W \cap\operatorname{periph}(S,X)| \le\ell-1. Then ∣W∖periph⁡(S,X)∣≥k−ℓ+1|W \setminus\operatorname{periph}(S,X)| \ge k-\ell+1 and we can pick T⊆W∖periph⁡(S,X)T \subseteq W \setminus\operatorname{periph}(S,X) with ∣T∣=k−ℓ+1|T| = k-\ell+1. Obviously, any X′⊆XX' \subseteq X with ∣X′∣≥ℓ|X'| \ge\ell will give ∣X′∪T∣≥ℓ+∣T∣=k+1|X' \cup T| \ge\ell+|T| = k+1. Therefore, the first condition of Definition 3 does not hold for TT. As (S,X)(S,X) deserves ℓ\ell candidates, it thus needs to hold that ∣S∣n>ℓ∣T∣+ℓ=ℓk+1\frac{|S|}{n} > \frac{\ell}{|T|+\ell} = \frac{\ell}{k+1}, which is equivalent to ∣S∣>ℓ⋅nk+1|S| > \ell\cdot\frac{n}{k+1}. With this, generalized Droop-PSC guarantees that ∣W∩periph⁡(S,X)∣≥min⁡(ℓ,∣X∣)|W \cap\operatorname{periph}(S,X)| \ge\min(\ell,|X|). Taking T=∅T = \varnothing in Definition 3 requires that ∣X∣≥ℓ|X| \ge\ell, which completes the contradiction.

Assume that WW satisfies Proportionality and take a solid coalition (S,X)(S,X) such that ∣S∣>ℓ⋅nk+1|S| > \ell\cdot\frac{n}{k+1}. We will first show that (S,X)(S,X) deserves ℓ′:=min⁡(ℓ,∣X∣)\ell' := \min(\ell,|X|) candidates. For this, consider any T⊆WT \subseteq W. If ∣T∣+ℓ′≤k|T|+\ell' \le k, then we pick any X′⊆XX' \subseteq X with ∣X′∣=ℓ′|X'| = \ell' towards satisfying Definition 3. Otherwise ∣T∣+ℓ′≥k+1|T|+\ell' \ge k+1, which allows us to satisfy Definition 3 with the inequality ∣S∣n>ℓ′k+1≥ℓ′∣T∣+ℓ′\frac{|S|}{n} > \frac{\ell'}{k+1} \ge\frac{\ell'}{|T|+\ell'}. These two cases complete the proof that (S,X)(S,X) deserves ℓ′\ell' candidates according to Definition 3. Therefore, Proportionality guarantees ∣W∩periph⁡(S,X)∣≥ℓ′|W \cap\operatorname{periph}(S,X)| \ge\ell', as also required by generalized Droop-PSC.

Proof of Theorem 2. Assume that WW satisfies Proportionality and let SS be an arbitrary set of voters that deserve ℓ\ell candidates according to PJR. Let X=⋂i∈SAiX = \bigcap_{i\in S} A_i. Then (S,X)(S,X) is a solid coalition. Moreover, the requirement of deserving ℓ\ell candidates according to PJR coincides with that under Proportionality. Hence, the fact that WW satisfies Proportionality implies that ∣periph⁡(S,X)∩W∣≥ℓ|\operatorname{periph}(S,X) \cap W| \ge\ell. By the choice of XX, we have periph⁡(S,X)=⋃i∈SAi\operatorname{periph}(S,X) = \bigcup_{i\in S} A_i, and therefore, WW also satisfies PJR.

Proof of Theorem 3. Take an election E=(C,N,F,A)E = (C,N,\mathcal{F},\mathcal{A}) such that ∣W∣=k|W| = k for each inclusion-wise maximal W∈FW \in\mathcal{F}. Let WW be an inclusion-wise maximal feasible outcome satisfying PJR. Towards showing that Proportionality is also satisfied, let (S,X)(S,X) be an arbitrary solid coalition deserving ℓ\ell candidates in WW according to Definition 3. We consider two cases. First, if X⊆⋂i∈SAiX \subseteq\bigcap_{i\in S} A_i, then the group SS deserves ℓ\ell candidates according to PJR, which guarantees ∣W∩⋃i∈SAi∣≥ℓ|W \cap\bigcup_{i\in S} A_i| \ge\ell. But periph⁡(S,X)=⋃i∈SAi\operatorname{periph}(S,X) = \bigcup_{i\in S} A_i, so Proportionality is also satisfied. Otherwise, if X⊈⋂i∈SAiX \not\subseteq\bigcap_{i\in S} A_i, then there exists a voter who has a non-approved candidate in XX, which inflates the periph⁡(S,X)\operatorname{periph}(S,X) to the whole set CC. As ℓ≤k\ell\le k is imposed by taking T=∅T = \varnothing in Definition 3, we now have ∣W∩periph⁡(S,X)∣=∣W∩C∣=∣W∣=k≥ℓ|W \cap\operatorname{periph}(S,X)| = |W \cap C| = |W| = k \ge\ell, again satisfying Proportionality.

For the second part of the proof, assume that there exist two inclusion-wise maximal sets A,B∈FA,B \in\mathcal{F} such that ∣A∣>∣B∣|A| > |B|. Consider an election with ∣A∣|A| voters, each approving a different candidate in AA. Let W=BW = B. We will show that WW satisfies PJR but not Proportionality.

According to PJR, a group of voters SS with ∣S∣>1|S| > 1 does not deserve any candidate in WW, as taking T=∅T = \varnothing would require them to find a feasible subset of candidates of at least 1 candidate in ⋂i∈SAi=∅\bigcap_{i\in S} A_i = \varnothing. A group SS consisting of a single voter who approves a candidate from A∖BA \setminus B also does not deserve any candidate, as when picking T=BT = B, by inclusion-wise maximality, there is no set that can be added to TT while preserving feasibility and also ∣S∣n=1∣A∣≤1∣T∣+1\frac{|S|}{n} = \frac{1}{|A|} \le\frac{1}{|T|+1}. Lastly, a group SS consisting of a single voter that approves a candidate from A∩BA \cap B satisfies ∣⋃i∈SAi∩W∣=1|\bigcup_{i\in S} A_i \cap W| = 1 while SS doesn't deserve more than one as for T=∅T = \varnothing we have 1n≤1\frac{1}{n} \le1 and ∣⋂i∈SAi∣=1|\bigcap_{i\in S} A_i| = 1 so one can't find a set X′X' of size 2 satisfying the corresponding requirement of PJR. Thus, WW satisfies PJR.

We now move to Proportionality. The solid coalition (N,X)(N,X) deserves ∣X∣|X| candidates in WW. To show it, take an arbitrary T⊆WT \subseteq W. If T=∅T = \varnothing, then the group can simply pick XX as the feasible set. Otherwise, we have ∣S∣n=1>∣X∣∣T∣+∣X∣\frac{|S|}{n} = 1 > \frac{|X|}{|T|+|X|}. However, it also holds that ∣W∩periph⁡(S,X)∣=∣W∩C∣=∣W∣=∣Y∣<∣X∣|W \cap\operatorname{periph}(S,X)| = |W \cap C| = |W| = |Y| < |X|, 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 nk+1\frac{n}{k+1}, under a payment scheme to be defined. In particular, for any t=1,…,kt=1,\ldots,k, we will show the existence of a payment scheme that buys WtW_t while satisfying the following:

(i.) no voter is ever left with a negative budget after a purchase, and

(ii.) for every voter ii and every solid coalition (S,X)(S,X) with i∈Si\in S and c∈X∖Wt−1c\in X\setminus W_{t-1} for which {c}∪Wt−1∈F\{c\}\cup W_{t-1}\in\mathcal{F} such that ρ(Wt,S,X)>nk+1\rho(W_t,S,X)>\frac{n}{k+1}, then voter ii has spent money only on candidates in periph⁡(S,X)\operatorname{periph}(S,X).

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 kk of the rule there is a solid coalition (S,X)(S,X) such that ρ(Wk,S,X)>nk+1\rho(W_k,S,X)>\frac{n}{k+1} and there exists c∈X∖Wk−1c\in X\setminus W_{k-1} with c∪Wk−1∈Fc\cup W_{k-1}\in\mathcal{F}. This means that

nk+1<∣S∣∣Wk∩periph⁡(S,X)∣+1n⋅(∣Wk∩periph⁡(S,X)∣+1)<∣S∣⋅(k+1)n⋅(k+1)+n⋅∣Wk∩periph⁡(S,X)∣<nk+∣S∣⋅(k+1)(n−∣S∣)(k+1)<n⋅(k−∣Wk∩periph⁡(S,X)∣)(n−∣S∣)(k+1)<n⋅∣Wk∖periph⁡(S,X)∣n−∣S∣<nk+1⋅∣Wk∖periph⁡(S,X)∣.(1)\begin{aligned} \frac{n}{k+1} &< \frac{|S|}{|W_k\cap\operatorname{periph}(S,X)|+1}\\ n\cdot\left(|W_k\cap\operatorname{periph}(S,X)|+1\right) &< |S|\cdot(k+1)\\ n\cdot(k+1)+n\cdot|W_k\cap\operatorname{periph}(S,X)| &< nk+|S|\cdot(k+1)\\ (n-|S|)(k+1) &< n\cdot\left(k-|W_k\cap\operatorname{periph}(S,X)|\right)\\ (n-|S|)(k+1) &< n\cdot|W_k\setminus\operatorname{periph}(S,X)|\\ n-|S| &< \frac{n}{k+1}\cdot|W_k\setminus\operatorname{periph}(S,X)|. \tag*{(1)} \end{aligned}

In the payment scheme for WkW_k the voters from SS had only paid for the candidates from periph⁡(S,X)\operatorname{periph}(S,X) (condition (ii)), which means that the voters from N∖SN\setminus S had to pay for the whole Wk∖periph⁡(S,X)W_k\setminus\operatorname{periph}(S,X). Therefore they have to have paid at least nk+1⋅∣Wk∖periph⁡(S,X)∣\frac{n}{k+1}\cdot|W_k\setminus\operatorname{periph}(S,X)| 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 tt. For t=1t=1 we note that W0=∅W_0=\varnothing, 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 Wt−1W_{t-1}, we show how to extend the payments to WtW_t while still satisfying conditions (i) and (ii), by reasoning about how to pay for the inclusion of ctc_t in WtW_t, where ctc_t is the tt-th candidate selected by the SCR rule.

At a step tt, we call a candidate cc electable as long as {c}∪Wt−1∈F\{c\}\cup W_{t-1}\in\mathcal{F}. Towards determining the payment scheme, consider first the case where there is no solid coalition (S,X)(S,X) with an electable candidate in XX and for which ρ(Wt−1,S,X)>nk+1\rho(W_{t-1},S,X)>\frac{n}{k+1}, i.e., the case where all solid coalitions are already represented in Wt−1W_{t-1} in proportion to their size. Then, we deduce the money for buying ctc_t in an arbitrary way, while ensuring satisfaction of condition (i). This is possible since the voters’ total initial budget is sufficient to pay for kk candidates (and therefore also for tt candidates, as t≤kt\leq k), since n>k⋅nk+1n>k\cdot\frac{n}{k+1}. Moreover, it holds that ρ(Wt,S,X)≤ρ(Wt−1,S,X)≤nk+1\rho(W_t,S,X)\leq\rho(W_{t-1},S,X)\leq\frac{n}{k+1}, for each solid coalition (S,X)(S,X) with an electable candidate, so condition (ii) holds again vacuously.

Suppose now that there is a solid coalition (S,X)(S,X) with an electable candidate c∈Xc\in X and for which ρ(Wt−1,S,X)>nk+1\rho(W_{t-1},S,X)>\frac{n}{k+1}, and let (S∗,X∗)(S^*,X^*) 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 Wt−1W_{t-1}, the voters from S∗S^* have only spent money on candidates from periph⁡(S∗,X∗)\operatorname{periph}(S^*,X^*). Each such candidate costs nk+1\frac{n}{k+1}, so the voters from S∗S^* have spent at most ∣Wt−1∩periph⁡(S∗,X∗)∣⋅nk+1|W_{t-1}\cap\operatorname{periph}(S^*,X^*)|\cdot\frac{n}{k+1}. Moreover, by definition, we have that ∣S∗∣∣Wt−1∩periph⁡(S∗,X∗)∣+1=ρ(Wt−1,S∗,X∗)\frac{|S^*|}{|W_{t-1}\cap\operatorname{periph}(S^*,X^*)|+1}=\rho(W_{t-1},S^*,X^*) and we have assumed that ρ(Wt−1,S∗,X∗)>nk+1\rho(W_{t-1},S^*,X^*)>\frac{n}{k+1}. By rearranging we get that ∣S∗∣>(∣Wt−1∩periph⁡(S∗,X∗)∣+1)⋅nk+1|S^*|>(|W_{t-1}\cap\operatorname{periph}(S^*,X^*)|+1)\cdot\frac{n}{k+1}. Therefore, the voters in S∗S^* have a remaining budget of at least nk+1\frac{n}{k+1}, so they can pay for a candidate cc in a way that satisfies condition (i). In the payment scheme for WtW_t we split the cost nk+1\frac{n}{k+1} for buying cc arbitrarily between the voters from S∗S^*. At what follows we will show that this payment scheme for WtW_t satisfies condition (ii) as well.

Towards a contradiction, let (S′,X′)(S',X') denote a solid coalition with c′∈X′∖Wt−1c'\in X'\setminus W_{t-1} for which {c′}∪Wt−1∈F\{c'\}\cup W_{t-1}\in\mathcal{F} such that ρ(Wt,S′,X′)>nk+1\rho(W_t,S',X')>\frac{n}{k+1} and assume that some voter i∈S′i\in S' spent money on a candidate that does not belong to periph⁡(S′,X′)\operatorname{periph}(S',X'). Since ρ(Wt−1,S′,X′)≥ρ(Wt,S′,X′)>nk+1\rho(W_{t-1},S',X')\geq\rho(W_t,S',X')>\frac{n}{k+1}, we infer from the induction hypothesis that voter ii has not spent money on candidates outside of periph⁡(S′,X′)\operatorname{periph}(S',X') during the first t−1t-1 steps of SCR rule. Hence, voter ii spent money on candidate ctc_t and ct∉periph⁡(S′,X′)c_t\notin\operatorname{periph}(S',X'). According to the defined payment scheme, only voters from S∗S^* spent money on the candidate ctc_t, therefore i∈S∗i\in S^* for the solid coalition (S∗,X∗)(S^*,X^*), meaning that ii weakly prefers each candidate in X∗X^* to any other candidate. Because ct∉periph⁡(S′,X′)c_t\notin\operatorname{periph}(S',X') it follows that X′⊆X∗X'\subseteq X^*. Note also that X∗X^* contains at least two electable candidates, namely c′c' and ctc_t, so it was not the terminating coalition in the while loop. From the definition of (S⋆,X⋆)(S^\star, X^\star), we know that the next solid coalition in the while loop, say (S⋄,X⋄)(S^\diamond, X^\diamond) had ρ(Wt−1,S⋄,X⋄)≤nk+1\rho(W_{t-1}, S^\diamond, X^\diamond) \le\frac{n}{k+1}. But then the SCR rule would have selected the solid coalition (S′,X′)(S^\prime, X^\prime) instead, as ρ(Wt−1,S′,X′)>nk+1≥ρ(Wt−1,S⋄,X⋄)\rho(W_{t-1}, S^\prime, X^\prime) > \frac{n}{k+1} \ge\rho(W_{t-1}, S^\diamond, X^\diamond), 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 kk. Recall that, according to Definition 3, a solid coalition (S,X)(S, X) deserves ℓ\ell candidates in WW if for every T⊆WT \subseteq W either there exists a set X′⊆XX^\prime\subseteq X with ∣X′∣≥ℓ|X^\prime| \ge\ell such that X′∪T∈FX^\prime\cup T \in\mathcal{F} or the following inequality holds:

∣S∣n>ℓ∣T∣+ℓ\frac{|S|}{n} > \frac{\ell}{|T|+\ell}

For k=0k=0, we have W0=∅W_0 = \varnothing. Consider the set T=∅⊆W0T = \varnothing\subseteq W_0. For this, the second condition becomes ∣S∣n>1\frac{|S|}{n} > 1, which does not hold for any S⊆NS \subseteq N. Therefore, any solid coalition (S,X)(S, X) that deserves ℓ\ell candidates in WW must satisfy the first condition: there exists X′⊆XX^\prime\subseteq X with ∣X′∣≥ℓ|X^\prime| \ge\ell and X′∈FX^\prime\in\mathcal{F}. Setting X0=X′X_0 = X^\prime immediately gives the desideratum, since X0⊆X∖W0X_0 \subseteq X \setminus W_0 and ∣W0∩periph⁡(S,X)∣=0|W_0 \cap\operatorname{periph}(S, X)| = 0.

We now move to the case of k≥1k \ge1 and we assume that the statement holds for k−1k-1. Hence, there exists a set Xk−1⊆X∖Wk−1X_{k-1} \subseteq X \setminus W_{k-1} such that ∣Xk−1∣+∣Wk−1∩periph⁡(S,X)∣≥ℓ|X_{k-1}| + |W_{k-1} \cap\operatorname{periph}(S, X)| \ge\ell and Xk−1∪Wk−1∈FX_{k-1} \cup W_{k-1} \in\mathcal{F}. Based on this, we need to show that there exists a set Xk⊆X∖WkX_k \subseteq X \setminus W_k such that ∣Xk∣+∣Wk∩periph⁡(S,X)∣≥ℓ|X_k| + |W_k \cap\operatorname{periph}(S, X)| \ge\ell and Xk∪Wk∈FX_k \cup W_k \in\mathcal{F}. Let ckc_k be the candidate in Wk∖Wk−1W_k \setminus W_{k-1}. At what follows, we will make use of the following observation from Masarík et al. [25].

Lemma 3. For a matroid family F\mathcal{F}, for all feasible sets W∈FW \in\mathcal{F}, c∉Wc \notin W and W′⊆WW^\prime\subseteq W (W′≠∅W^\prime\ne\varnothing) such that W∖W′∪{c}∈FW \setminus W^\prime\cup\{c\} \in\mathcal{F}, there exists c′∈W′c^\prime\in W^\prime such that W∖{c′}∪{c}∈FW \setminus\{c^\prime\} \cup\{c\} \in\mathcal{F}.

If ck∈periph⁡(S,X)c_k \in\operatorname{periph}(S, X) then Lemma 3 says that there exists a candidate c∈Xk−1c \in X_{k-1} such that Xk−1∖{c}∪Wk∈FX_{k-1} \setminus\{c\} \cup W_k \in\mathcal{F}. This means we can take Xk=Xk−1∖{c}X_k = X_{k-1} \setminus\{c\}.

Now, say that ck∉periph⁡(S,X)c_k \notin\operatorname{periph}(S, X). Then, if ∣Wk∩periph⁡(S,X)∣≥ℓ|W_k \cap\operatorname{periph}(S, X)| \ge\ell we can simply use Xk=∅X_k = \varnothing. On the other hand, say that ∣Wk∩periph⁡(S,X)∣+1≤ℓ|W_k \cap\operatorname{periph}(S, X)| + 1 \le\ell. Take T=Wk∖periph⁡(S,X)T = W_k \setminus\operatorname{periph}(S, X) and consider the answer of SS to TT. We have that ∣S∣∣Wk∩periph⁡(S,X)∣+1≥∣S∣ℓ\frac{|S|}{|W_k \cap\operatorname{periph}(S, X)|+1} \ge\frac{|S|}{\ell}. The function t↦t∣T∣+tt \mapsto\frac{t}{|T|+t} is increasing, so:

ℓ∣T∣+ℓ≥∣Wk∩periph⁡(S,X)∣+1∣T∣+∣Wk∩periph⁡(S,X)∣+1.\frac{\ell}{|T|+\ell} \ge\frac{|W_k \cap\operatorname{periph}(S, X)|+1}{|T|+|W_k \cap\operatorname{periph}(S, X)|+1}.

By the definition of TT, the denominator on the right satisfies ∣T∣+∣Wk∩periph⁡(S,X)∣+1=∣Wk∣+1=k+1|T| + |W_k \cap\operatorname{periph}(S, X)| + 1 = |W_k| + 1 = k+1, giving:

∣S∣n>∣Wk∩periph⁡(S,X)∣+1k+1⟺ρ(Wk,S,X)=∣S∣∣Wk∩periph⁡(S,X)∣+1>nk+1.(2)\frac{|S|}{n} > \frac{|W_k \cap\operatorname{periph}(S, X)|+1}{k+1} \Longleftrightarrow\rho(W_k,S,X) = \frac{|S|}{|W_k \cap\operatorname{periph}(S, X)|+1} > \frac{n}{k+1}. \tag*{(2)}

Since ∣Wk∩periph⁡(S,X)∣+1≤ℓ|W_k \cap\operatorname{periph}(S, X)| + 1 \le\ell, the induction hypothesis ∣Wk−1∩periph⁡(S,X)∣+∣Xk−1∣≥ℓ|W_{k-1} \cap\operatorname{periph}(S, X)| + |X_{k-1}| \ge\ell, together with ck∉periph⁡(S,X)c_k \notin\operatorname{periph}(S, X), implies that ∣Xk−1∣≥1|X_{k-1}| \ge1. Consequently, (S,X)(S, X) 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 ∣S∣ℓ>n−∣S∣∣T∣\frac{|S|}{\ell} > \frac{n-|S|}{|T|}. Thus, as SS deserves ℓ\ell candidates, there needs to exist X′⊆XX^\prime\subseteq X with ∣X′∣≥ℓ|X^\prime| \ge\ell such that X′∪Wt∖periph⁡(S,X)∈FX^\prime\cup W_t \setminus\operatorname{periph}(S, X) \in\mathcal{F}. From Definition 5 we get that there exists the XkX_k.

Proof of Theorem 5.

Given family of constraints F\mathcal{F}, as it is not a matroid, there exist two sets X,Y∈FX,Y \in\mathcal{F} such that ∣X∣<∣Y∣|X| < |Y| and X∪{c}∉FX \cup\{c\} \notin\mathcal{F} for all c∈Y∖Xc \in Y \setminus X. Say that ∣Y∣=ℓ|Y| = \ell. Consider the instance where a set SS of ℓℓ+1n+1\frac{\ell}{\ell+1}n+1 voters ranks all candidates in X∪YX \cup Y tied and above the remaining candidates, while all other voters rank XX 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 kk of SCR, as long as there exists an electable candidate c∈Xc \in X, that is, a candidate satisfying {c}∪Wk−1∈F\{c\} \cup W_{k-1} \in\mathcal{F}, we have Wk⊆XW_k \subseteq X. We prove this by induction on kk. For k=0k=0, we have Wk=∅W_k = \varnothing, so the claim holds trivially. For k≥1k \ge1, assume that there exists a candidate c∈Xc \in X such that {c}∪Wk−1∈F\{c\} \cup W_{k-1} \in\mathcal{F} and Wk−1⊆XW_{k-1} \subseteq X. We note that for a fixed set C′⊆CC^\prime\subseteq C, a solid coalition (S′,C′)(S^\prime, C^\prime) has strictly lower underrepresentation value than a solid coalition (S′′,C′)(S^{\prime\prime}, C^\prime) with S′′⊃S′S^{\prime\prime} \supset S^\prime. Moreover, there are two families of voter maximal solid coalitions:

  • a coalition (N,X′)(N, X') for any X′⊆XX' \subseteq X,

  • a coalition (S,Z)(S, Z) for any Z⊆X∪YZ \subseteq X \cup Y such that Z∩Y≠∅Z \cap Y \ne\emptyset.

To determine how SCR operates on the proposed instance we compute underrepresentation values as follows:

ρ(Wk−1,N,X′)=n∣Wk−1∩periph⁡(N,X′)∣+1=nk≥∣S∣∣Wk−1∩periph⁡(S,Z)∣+1=ρ(Wk−1,S,Z)\rho(W_{k-1},N,X')=\frac{n}{|W_{k-1}\cap\operatorname{periph}(N,X')|+1}=\frac{n}{k} \ge\frac{|S|}{|W_{k-1}\cap\operatorname{periph}(S,Z)|+1}=\rho(W_{k-1},S,Z)

Which means that during the first iteration of the while loop, the rule will pick a coalition (N,X′)(N, X') for some X′⊆XX' \subseteq X, as Step 5 ensures that X⊆CX \subseteq C. Therefore, a candidate from XX will be elected in this round, which proves that Wk⊆XW_k \subseteq X. Consequently, the outcome of SCR contains no candidate from YY. Indeed, after all candidates from XX have been included in the committee WW, we have W∪{c}∉FW \cup\{c\} \notin\mathcal{F} for every candidate c∈Yc \in Y, since X∪{c}∉FX \cup\{c\} \notin\mathcal{F} for all c∈Y∖Xc \in Y \setminus X, by construction.

We now show that the solid coalition (S,X∪Y)(S, X \cup Y) deserves ℓ\ell candidates in the outcome. Consider any T⊆WT \subseteq W. If T=∅T = \emptyset, then we can take X′=YX' = Y, and immediately obtain a set X′⊆X∪YX' \subseteq X \cup Y with ∣X′∣≥ℓ|X'| \ge\ell such that X′∪T∈FX' \cup T \in\mathcal{F}. Otherwise, if ∣T∣≥1|T| \ge1, then we have the following:

∣S∣n=ℓℓ+1+1n>ℓℓ+1≥ℓℓ+∣T∣.\frac{|S|}{n}=\frac{\ell}{\ell+1}+\frac{1}{n}>\frac{\ell}{\ell+1}\ge\frac{\ell}{\ell+|T|}.

Since T⊆CT \subseteq C was arbitrary, it proves that the coalition (S,X∪Y)(S, X \cup Y) deserves ℓ\ell candidates in any outcome. Nevertheless, we have ∣W∩periph⁡(S,X∪Y)∣=∣W∩(X∪Y)∣=∣X∣<∣Y∣=ℓ|W \cap\operatorname{periph}(S, X \cup Y)|=|W \cap(X \cup Y)|=|X|<|Y|=\ell, which shows that SCR fails Proportionality.

Proof of Theorem 6.

Assume that we have some fixed X⊆CX \subseteq C, and we want to find S⊆NS \subseteq N such that (S,X)(S, X) is a solid coalition that maximizes the underrepresentation value. We define NXN_X as the set of voters who have no voter from C∖XC \setminus X ranked strictly above any candidate from XX, i.e. they have XX on top. We first note that, in the approval voting setting, for any solid coalition (S,X)(S, X) the corresponding periphery is independent of XX, namely either periph⁡(S,X)=⋃i∈SAi\operatorname{periph}(S, X)=\bigcup_{i\in S} A_i or periph⁡(S,X)=C\operatorname{periph}(S, X)=C. Therefore, each refinement step for a set DD 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 (S,X)(S, X) such that ρ(W,S,X)≥y\rho(W,S,X)\ge y. Notice that there are only O(nm)O(nm) possible values of yy, since the underrepresentation value is determined by a fraction whose numerator can take O(n)O(n) values and whose denominator can take O(m)O(m) values. We define an auxiliary function f:2N→Qf:2^N\to\mathbb{Q} as f(S)=∣W∩periph⁡(S,X)∣−∣S∣yf(S)=|W\cap\operatorname{periph}(S,X)|-\frac{|S|}{y} and we note that

f(S)≤−1⇔y∣W∩periph⁡(S,X)∣−∣S∣≤−y⇔f(S)\le-1\Leftrightarrow y|W\cap\operatorname{periph}(S,X)|-|S|\le-y\Leftrightarrow
y(∣W∩periph⁡(S,X)∣+1)≤∣S∣⇔y≤∣S∣∣W∩periph⁡(S,X)∣+1=ρ(W,S,{c}).y(|W\cap\operatorname{periph}(S,X)|+1)\le|S|\Leftrightarrow y\le\frac{|S|}{|W\cap\operatorname{periph}(S,X)|+1}=\rho(W,S,\{c\}).

Therefore, it holds that ρ(W,S,X)≥y\rho(W,S,X)\ge y if and only if f(S)≤−1f(S)\le-1. Moreover, the function ff is submodular. To show this, consider S′⊆S⊆NS' \subseteq S \subseteq N, and i∈N∖Si\in N\setminus S, then

f(S′∪{i})−f(S′)=∣W∩periph⁡(S′∪{i},X)∣−∣W∩periph⁡(S′,X)∣−1/y=∣(W∩(periph⁡(S′,X)∪periph⁡(i,X)))∣−∣W∩periph⁡(S′,X)∣−1/y=∣(W∩(periph⁡(i,X)∖periph⁡(S′,X)))∣−1/y≥∣(W∩(periph⁡(i,X)∖periph⁡(S,X)))∣−1/y=f(S∪{i})−f(S).\begin{aligned} f(S'\cup\{i\})-f(S')&=|W\cap\operatorname{periph}(S'\cup\{i\},X)|-|W\cap\operatorname{periph}(S',X)|-1/y\\ &=|(W\cap(\operatorname{periph}(S',X)\cup\operatorname{periph}(i,X)))|-|W\cap\operatorname{periph}(S',X)|-1/y\\ &=|(W\cap(\operatorname{periph}(i,X)\setminus\operatorname{periph}(S',X)))|-1/y\\ &\ge|(W\cap(\operatorname{periph}(i,X)\setminus\operatorname{periph}(S,X)))|-1/y\\ &=f(S\cup\{i\})-f(S). \end{aligned}

Overall, in each iteration of the rule, we determine XX either by setting X={c}X=\{c\} or X=D∖{c}X=D\setminus\{c\} for every available candidate cc, and then aim to find a suitable set SS; among the considered solid coalitions we pick the one maximizing the underrepresentation value. For this, we consider all possible values of yy, or apply a binary search over them. For each considered value of yy, we iterate over all candidate sets XX defined above and introduce a function ff to check whether there exists a set SS such that f(S)≤−1f(S)\le-1. We then fix the solid coalition (S,X)(S,X) corresponding to a set SS that satisfies this condition for the maximum possible value of yy.

Proof of Theorem 7.

Given an election EE, let ww 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 ww, 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 (S,X)(S, X) that maximizes the underrepresentation value (Step 6 of Algorithm 1), it is enough to consider the sets X⊆CX \subseteq C that are on top of the ranking of at least one voter; these can be at most nm2wnm2^w. In line with the proof of Theorem 6, we will check whether or not there exists a solid coalition (S,X)(S, X) such that ρ(W,S,X)≥y\rho(W,S,X) \ge y. Again, it is enough to iterate over the pre-computed list of possible sets X⊆CX \subseteq C. We define NXN_X as the set of voters who have no voter from C∖XC \setminus X ranked strictly above any candidate from XX, i.e. they have XX on top, and then introduce the auxiliary function f:2NX→Qf : 2^{N_X} \to\mathbb{Q} as f(S)=∣W∩periph⁡(S,X)∣−∣S∣yf(S) = |W \cap\operatorname{periph}(S,X)| - \frac{|S|}{y}. Again, ρ(W,S,X)≥y\rho(W,S,X) \ge y if and only if f(S)≤−1f(S) \le-1 and ff is submodular.

Now, let w′w' 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 (S,X)(S, X) that maximizes the underrepresentation value by considering two families of sets X⊆CX \subseteq C: (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 ww. In the second case, we have periph⁡(S,X)=C\operatorname{periph}(S,X) = C, making it analogous to the case considered in the proof of Theorem 6, and introducing only an additional number of mm sets to consider.

Proof of Theorem 8.

We denote by ≻i\succ_i the strict preference relation between alternatives in the order submitted by voter ii. 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 (X,X′)(X,X') such that X⊆X′⊆CX \subseteq X' \subseteq C; the set X′X' serves as a possible (inclusion-wise) upper bound for the periphery. Having fixed the sets XX and X′X', we compute a set of voters SS such that S={i∈N:X⪰iC∖X∧X′≻iC∖X′}S = \{i \in N : X \succeq_i C \setminus X \land X' \succ_i C \setminus X'\}. Observe that SS is the maximal set of voters such that (S,X)(S,X) is a solid coalition satisfying periph⁡(S,X)⊆X′\operatorname{periph}(S,X) \subseteq X', and, for the specified pair (X,X′)(X,X') only a single solid coalition, namely (S,X)(S,X), needs to be examined. In turn, the maximization function of the underrepresentation value needs to be employed over a family of size bounded by 3m3^m.

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 O(2n⋅nm2)O(2^n \cdot nm^2). We first observe that for a group of voters S⊆NS \subseteq N and X,X′⊆CX,X' \subseteq C such that ∣X∣=∣X′∣|X| = |X'| and both (S,X)(S,X) and (S,X′)(S,X') are solid coalitions, it holds that periph⁡(S,X)=periph⁡(S,X′)\operatorname{periph}(S,X) = \operatorname{periph}(S,X'). This comes from the fact, that we can express the periphery solely in terms of SS and r=∣X∣r = |X|. In particular, periph⁡(S,X)=⋃i∈S{c∈C:c⪰ici,r}\operatorname{periph}(S,X) = \bigcup_{i \in S}\{c \in C : c \succeq_i c^{i,r}\}, where ci,rc^{i,r} is the rr-th candidate on voter ii ranking, breaking ties arbitrarily.

We will show that can solve the maximization problem by first iterating through all S⊆NS \subseteq N and then by all possible sizes of XX. For each such SS and a possible size rr we present a procedure to determine if there exists a set of candidates XX such that

(i) ∣X∣=r|X| = r,

(ii) (S,X)(S,X) is a solid coalition,

(iii) X⊆DX \subseteq D,

(iv) X∩C′≠∅X \cap C' \ne\varnothing.

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 c,c′c,c' belong to the same indifference class for a voter ii we write c∼ic′c \sim_i c'. Towards constructing a suitable set XX, we define the following sets of candidates:

Xalways=⋃i∈S{c∈C:c≻ici,r},Xmaybe=⋂i∈S{c∈C:c∼ici,r}.X_{always} = \bigcup_{i \in S}\{c \in C : c \succ_i c^{i,r}\}, \qquad X_{maybe} = \bigcap_{i \in S}\{c \in C : c \sim_i c^{i,r}\}.

All candidates from the set XalwaysX_{always} will have to be included in the constructed set XX. To argue that this is the case, focus on some voter i∈Si \in S. If she is a part of a solid coalition (S,X)(S,X) with ∣X∣=r|X| = r, then it needs to be the case that {c∈C:c≻ici,r}⊆X\{c \in C : c \succ_i c^{i,r}\} \subseteq X, as the set XX has to be on top of the ranking, and to guarantee that XX satisfies condition (ii), we need to check that the set XalwaysX_{always} is on top of the ranking of every voter from SS. Similarly, candidates from C∖(Xalways∪Xmaybe)C \setminus(X_{always} \cup X_{maybe}) should not be included in XX. The condition (i) additionally requires that ∣Xalways∣≤r|X_{always}| \le r. Further, the condition (iii) requires that Xalways⊆DX_{always} \subseteq D.

After determining that Xalways⊆XX_{always} \subseteq X, we need to fill the remaining r−∣Xalways∣r - |X_{always}| spots. We do that, by adding some candidates from the set Xmaybe∩DX_{maybe} \cap D. 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 XX that satisfies all the introduced constraints. If the construction was successful, we add the solid coalition (S,X)(S, X) 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 O(2n⋅nm4)O(2^n \cdot nm^4). This comes from the O(2n⋅m)O(2^n \cdot m) iterations in the outer loops, an additional O(nm)O(nm) cost for determining the sets XalwaysX_{always} and XmaybeX_{maybe}, and up to O(m)O(m) refinements for each of the O(m)O(m) candidates to be potentially elected. Overall, the running time is FPT with respect to the number of voters.

Proof of Theorem 9.

Let t=⌊k⌋t = \lfloor\sqrt{k}\rfloor and ℓ=t−1\ell= t - 1. Consider an election with C={c1,…,ck,d1,…,dℓ}C = \{c_1, \ldots, c_k, d_1, \ldots, d_\ell\} and N={1,…,k}N = \{1, \ldots, k\}. We introduce two groups of voters, with approval ballots defined as follows:

Ai={{ci,d1,…,dℓ}if i≤ℓ{c1,…,ck}if i>ℓA_i = \begin{cases} \{c_i, d_1, \ldots, d_\ell\} & \text{if } i \le\ell\\ \{c_1, \ldots, c_k\} & \text{if } i > \ell \end{cases}

We denote the set of voters of the first group as S1S_1 and the set of voters of the second as S2S_2.

We will show that the SCR rule elects c1,…,ckc_1, \ldots, c_k as the winning committee. Let i≥0i \ge0 and assume that the candidates c1,…,cic_1, \ldots, c_i have already been elected. Taking ties into account, there are two candidates under consideration for election, ci+1c_{i+1} and d1d_1. We now consider two cases.

If i<ℓi < \ell, then the maximum underrepresentation value that can be achieved with respect to the candidate ci+1c_{i+1} is ρ(Wi,S2∪{i+1},{ci+1})=k−ℓ+1i+1\rho(W_i, S_2 \cup\{i + 1\}, \{c_{i+1}\}) = \frac{k-\ell+1}{i+1}, to be denoted for simplicity by ρ(ci+1)\rho(c_{i+1}). Note that this value is strictly greater than ρ(Wi,{i+1},{ci+1})=1\rho(W_i, \{i + 1\}, \{c_{i+1}\}) = 1. For the underrepresentation value with respect to the candidate d1d_1, to be denoted for simplicity by ρ(d1)\rho(d_1), consider the group of voters with j≤ij \le i of them approving some candidate that already have been elected. Then the underrepresentation value is ρ(d1)=ρ(Wi,{1,2,…,j,i+1,i+2,…,ℓ},{d1})=ℓ−i+jj+1\rho(d_1) = \rho(W_i, \{1, 2, \ldots, j, i + 1, i + 2, \ldots, \ell\}, \{d_1\}) = \frac{\ell-i+j}{j+1}, which is maximal for j=0j = 0.

We want to show that ρ(d1)=ℓ−i<k−ℓ+1i+1=ρ(ci+1)\rho(d_1) = \ell- i < \frac{k-\ell+1}{i+1} = \rho(c_{i+1}). Equivalently, we want to show that −i2+(ℓ−1)i+ℓ<k−ℓ+1-i^2 + (\ell- 1)i + \ell< k - \ell+ 1.

We first claim that (ℓ+1)24<k−ℓ+1⇔t2<4(k−t+2)\frac{(\ell+1)^2}{4} < k - \ell+ 1 \Leftrightarrow t^2 < 4(k - t + 2). This is true because 3t2−4t+8=3(t−2/3)2+20/3>0⇔t2+4m−8<4t2≤4k3t^2 - 4t + 8 = 3(t - 2/3)^2 + 20/3 > 0 \Leftrightarrow t^2 + 4m - 8 < 4t^2 \le4k, where the last inequality follows from k≥t2k \ge t^2.

Consider the function f(i)=−i2+(ℓ−1)i+ℓf(i) = -i^2 + (\ell- 1)i + \ell, for i∈[0,ℓ)i \in[0,\ell). It holds that f′(i)=−2i+ℓ−1f'(i) = -2i + \ell- 1, f′′(i)<0f''(i) < 0. Hence, ff has its maximum at i∗=(ℓ−1)/2i^* = (\ell- 1)/2. Moreover, f(i∗)=(ℓ+1)2/4f(i^*) = (\ell+1)^2/4. Therefore, −i2+(ℓ−1)i+ℓ≤(ℓ+1)2/4<k−ℓ+1-i^2 + (\ell- 1)i + \ell\le(\ell+1)^2/4 < k - \ell+ 1.

For the second case of i≥ℓi \ge\ell, every voter from S1S_1 already has a satisfaction with respect to one candidate, which leads to ρ(Wi,S,d1)=∣S∣∣S∣+1\rho(W_i, S, d_1) = \frac{|S|}{|S|+1} for any S⊆S1S \subseteq S_1; we denote it by ρ(d1)\rho(d_1). Regarding ci+1c_{i+1}, we also compute the underrepresentation value, to be denoted by ρ(ci+1)\rho(c_{i+1}) and for this we note that only voters from S2S_2 approve ci+1c_{i+1}. The highest underrepresentation values for these candidates are achieved by groups S1S_1 and S2S_2, respectively. Therefore, we need to show that

ρ(d1)=ℓℓ+1<k−ℓi+1=ρ(ci+1).\rho(d_1) = \frac{\ell}{\ell+1} < \frac{k-\ell}{i+1} = \rho(c_{i+1}).

First, we claim that k−ℓ>ℓk-\ell> \ell. This holds because t2≤kt^2 \le k and t2>2t−2t^2 > 2t - 2, so k≥2t−2⇔k−t+1>t−1k \ge2t - 2 \Leftrightarrow k - t + 1 > t - 1. We want to prove that ℓℓ+1<k−ℓk\frac{\ell}{\ell+1} < \frac{k-\ell}{k}, or, equivalently, that 2ℓ2+ℓ<kℓ+k2\ell^2 + \ell< k\ell+ k. Given that k−ℓ>ℓk-\ell> \ell, we have k(ℓ+1)>2ℓ(ℓ+1)>2ℓ2+ℓk(\ell+1) > 2\ell(\ell+1) > 2\ell^2+\ell.

Consequently, in both cases, the candidate ci+1c_{i+1} will be elected. We also have to check the underrepresentation value arising from the case where a group of voters SS ranks a candidate c∈Cc \in C at the bottom of their ranking, i.e., disapproves of cc, and may therefore contribute to refining the examined set of candidates DD to D∖{c}D \setminus\{c\}. In this case, SS is necessarily a subset of either S1S_1 or S2S_2, 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 {c1,…,ck}\{c_1, \ldots, c_k\}. To conclude the proof, observe that ⋂i∈S1Ai={d1,…,dℓ}=ℓ\bigcap_{i \in S_1} A_i = \{d_1, \ldots, d_\ell\} = \ell, ∣S1∣=ℓ=ℓ⋅nk|S_1| = \ell= \ell\cdot\frac{n}{k} and for each i∈S1i \in S_1 we have ∣Ai∩SCR(E)∣=1=ℓ⋅1⌊k⌋−1|A_i \cap SCR(E)| = 1 = \ell\cdot\frac{1}{\lfloor\sqrt{k}\rfloor- 1}.

Proof of Theorem 10.

In the construction of Theorem 9, each voter in the group S1S_1 approves a different candidate cic_i, and ∣S1∣=ℓ|S_1| = \ell. Moreover, each voter in S1S_1 obtains a satisfaction of 1 from the outcome of SCR, while deserving ℓ\ell. Therefore, if the size of S1S_1 could be increased while keeping the satisfaction of its voters bounded by one, the resulting proportionality degree would decrease. To this end, let S1S_1 be partitioned into kk groups such that the ii-th group has size equal to xi⋅nx_i \cdot n and its members approve candidate cic_i, as well as enough candidates from the set {d1,d2,…}\{d_1,d_2,\ldots\} so that the cohesiveness of S1S_1 can only be limited by its size. We fix the committee size kk and formulate the problem of maximizing the size of S1S_1—which in turn yields an upper bound on the proportionality degree of SCR—as a linear program.

maximize:∑i=1kxiwith respect to:∑i=1kxi≤1xi≥0∀i∈{1,…,k}xi+1≤xi∀i∈{1,…,k−1}(1−∑i=1kxi)+xtt≥∑j=1rxi+∑i=tkxir+1∀t∈{1,…,k}, ∀r∈{0,…,t}\begin{aligned} \text{maximize:}\quad& \sum_{i=1}^{k} x_i \\ \text{with respect to:}\quad& \sum_{i=1}^{k} x_i \le1 \\ & x_i \ge0 && \forall i \in\{1,\ldots,k\} \\ & x_{i+1} \le x_i && \forall i \in\{1,\ldots,k-1\} \\ & \frac{\left(1-\sum_{i=1}^{k}x_i\right)+x_t}{t} \ge \frac{\sum_{j=1}^{r}x_i+\sum_{i=t}^{k}x_i}{r+1} && \forall t \in\{1,\ldots,k\},\ \forall r \in\{0,\ldots,t\} \end{aligned}

Here, the variables represent the fraction of voters in S1S_1 relative to the entire electorate, so that ∑i=1kxi=∣S1∣n\sum_{i=1}^{k}x_i=\frac{|S_1|}{n}. We have to ensure that the candidate elected at step tt is ctc_t, which is guaranteed by the last inequality. The left-hand side captures the underrepresentation value with respect to candidate ctc_t, who is supported by all voters in S2S_2 as well as by some voters from S1S_1 which amount to an xtx_t fraction of the voters of the electorate. The right-hand side captures the underrepresentation value with respect to candidate d1d_1, who is supported by all voters in S1S_1 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 S1S_1, the second selected candidate is the one supported by the second-largest fraction, and so on. Solving the program for small values of kk already suggests a substantially stronger upper bound that is less than 3k0.72\frac{3}{k^{0.72}}, as the following plot demonstrates.

Plot of proportionality degree against committee size

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 E=(C,N,{W′⊆C:∣W′∣≤k},A)E=(C,N,\{W' \subseteq C : |W'| \le k\},\mathcal{A}) be a committee election under approval ballots. An outcome WW is Pareto dominated by an outcome W′W' if for each voter i∈Ni \in N it holds that ∣Ai∩W∣≤∣Ai∩W′∣|A_i \cap W| \le|A_i \cap W'| while for at least one voter the inequality is strict. An outcome WW 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 P=NPP=NP.

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 C={a,b,c,d}C = \{a, b, c, d\}, k=2k = 2, and the following 14 voters:

GroupNumber of votersApproval set
G1G_15{a,c}\{a,c\}
G2G_23{a,d}\{a,d\}
G3G_33{b,d}\{b,d\}
G4G_42{b,c}\{b,c\}
G5G_51{d}\{d\}

Table 1 (PDF p. 20).

We show that SCR returns W={a,b}W = \{a,b\} which is Pareto dominated by W′={c,d}W' = \{c,d\}. Recall that, under approval preferences, a voter ii solidly supports a nonempty set XX if and only if X⊆AiX \subseteq A_i or Ai⊆XA_i \subseteq X. Moreover, if every voter in a solid coalition (S,X)(S, X) approves every candidate in XX, then periph⁡S(X)=⋃i∈SAi\operatorname{periph}_S(X) = \bigcup_{i \in S} A_i. Otherwise, periph⁡S(X)=C\operatorname{periph}_S(X) = C.

The following table gives the maximum value of ρ(W,S,X)\rho(W, S, X) over all nonempty solid coalitions (S,X)(S, X), for each nonempty proper subset XX of CC, at the two partial outcomes that occur in the execution. A dash means that no nonempty group solidly supports XX.

XXmax⁡Sρ(∅,S,X)\max_S \rho(\varnothing, S, X)max⁡Sρ({a},S,X)\max_S \rho(\{a\}, S, X)
{a}\{a\}8(5+3)/2=4(5 + 3)/2 = 4
{b}\{b\}53+2=53 + 2 = 5
{c}\{c\}7max⁡{2,(5+2)/2}=7/2\max\{2,(5 + 2)/2\} = 7/2
{d}\{d\}7max⁡{3+1,(3+3+1)/2}=4\max\{3 + 1,(3 + 3 + 1)/2\} = 4
{a,b}\{a,b\}––
{a,c}\{a,c\}55/25/2
{a,d}\{a,d\}4(3+1)/2=2(3 + 1)/2 = 2
{b,c}\{b,c\}22
{b,d}\{b,d\}4max⁡{3,(3+1)/2}=3\max\{3,(3 + 1)/2\} = 3
{c,d}\{c,d\}11/21/2
{a,b,c}\{a,b,c\}7(5+2)/2=7/2(5 + 2)/2 = 7/2
{a,b,d}\{a,b,d\}7(3+3+1)/2=7/2(3 + 3 + 1)/2 = 7/2
{a,c,d}\{a,c,d\}9(5+3+1)/2=9/2(5 + 3 + 1)/2 = 9/2
{b,c,d}\{b,c,d\}6(3+2+1)/2=3(3 + 2 + 1)/2 = 3

Table 2.

Initially, W0=∅W_0 = \varnothing and D=CD = C. Since ρ(∅,S,X)=∣S∣\rho(\varnothing, S, X) = |S|, the unique maximizing refinement is (S,X)=(G1∪G2∪G5,{a,c,d})(S, X) = (G_1 \cup G_2 \cup G_5, \{a,c,d\}). Therefore, SCR first replaces DD by {a,c,d}\{a,c,d\}. Notice that (N,C)(N, C) is not eligible, since a refinement must be a proper subset of the current set DD. The nonempty proper subsets of the new DD are {a},{c},{d},{a,c},{a,d},{c,d}\{a\}, \{c\}, \{d\}, \{a,c\}, \{a,d\}, \{c,d\}. Thus, the unique maximizing refinement is (G1∪G2,{a})(G_1 \cup G_2, \{a\}), and SCR elects aa.

Consider now the second round, where W1={a}W_1 = \{a\} and D=CD = C. As shown in the table, the unique maximizing refinement is (G3∪G4,{b})(G_3 \cup G_4, \{b\}). Therefore, SCR elects bb and returns W={a,b}W = \{a,b\}.

We conclude by noting that, on the same instance, sequential PAV also uniquely elects aa first. After electing aa, the marginal scores are

Δ(b∣{a})=3+2=5,Δ(c∣{a})=52+2=92,Δ(d∣{a})=32+3+1=112.\Delta(b \mid\{a\}) = 3 + 2 = 5,\qquad\Delta(c \mid\{a\}) = \frac{5}{2} + 2 = \frac{9}{2},\qquad\Delta(d \mid\{a\}) = \frac{3}{2} + 3 + 1 = \frac{11}{2}.

Therefore, sequential PAV uniquely elects dd next and returns {a,d}\{a,d\}, rather than the SCR outcome {a,b}\{a,b\}. The difference is that sequential PAV adds the half-weight contributions of the three already represented voters in G2G_2 to the four unrepresented supporters of dd, whereas SCR evaluates these supporters through a common coalition-level denominator. Notice also that {a,d}\{a,d\} is Pareto optimal on this instance: any committee Pareto dominating it would have to give the voters in G2G_2 two approved winners, and hence would have to contain both aa and dd. ∎

The remaining of this section is devoted to empirical findings and details. In § 6 we analyzed the kk-Borda and the Utilitarian Greedy algorithms which select the outcome

W=arg⁡max⁡W∈W∑i∈Nui(W),W = \arg\max_{W \in\mathcal{W}} \sum_{i \in N} u_i(W),

where ui(W)=∑c∈W(m−rank⁡i(c))u_i(W) = \sum_{c \in W} (m-\operatorname{rank}_i(c)) and ui(W)=∣W∩Ai∣u_i(W) = |W \cap A_i| respectively. For kk-Borda, we assumed that voters get a utility of 0 from their unranked candidates, i.e., those positioned last, and rank⁡i(c)\operatorname{rank}_i(c) indicates the position of cc in the ranking of ii.

The Method of Equal Shares (MES) proceeds through a sequence of rounds. In approval-based committee elections, each voter ii is assigned a virtual budget bib_i, initialized to k/nk/n, 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 cc and a parameter ρ∈R+\rho\in\mathbb{R}_{+}, we say that cc is ρ\rho-affordable if

∑i∈Acmin⁡(bi,ρ)=1.\sum_{i \in A_c} \min(b_i,\rho) = 1.

Among all candidates that are ρ\rho-affordable for some value of ρ\rho, the one with the smallest such ρ\rho is selected and added to the committee. The virtual budgets of its supporters are then updated: bi:=bi−min⁡(bi,ρ)b_i := b_i - \min(b_i,\rho). The process terminates when there is no ρ\rho-affordable candidate for any value of ρ\rho.

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.

  1. W←∅W \leftarrow\varnothing

  2. {wi←1}i∈N\{w_i \leftarrow1\}_{i \in N}

  3. for r=1,…,mr = 1,\ldots,m do

  4. {Nc←{i∈N:rank⁡i(c)≤r}}c∈C′\{N_c \leftarrow\{i \in N : \operatorname{rank}_i(c) \le r\}\}_{c \in C'}

  5. {rc←∑i∈Ncwi}c∈C′\{r_c \leftarrow\sum_{i \in N_c} w_i\}_{c \in C'}

  6. while max⁡c∈C∖Wrc≥q\max_{c \in C \setminus W} r_c \ge q do

  7. c′←arg⁡max⁡c∈C′rcc' \leftarrow\arg\max_{c \in C'} r_c

  8. for i∈Nc′i \in N_{c'} do

  9. wi←wi⋅(1−q/rc′)w_i \leftarrow w_i \cdot(1-q/r_{c'})

  10. W←W∪{c′}W \leftarrow W \cup\{c'\}

  11. return WW

Algorithm 2: The pseudocode of the Expanding Approvals Rule.

  1. W←∅W \leftarrow\varnothing

  2. C′←CC' \leftarrow C

  3. {wi←1}i∈N\{w_i \leftarrow1\}_{i \in N}

  4. while C′≠∅C' \ne\varnothing do

  5. {Nc←{i∈N:c≻C′∖{c}}}c∈C′\{N_c \leftarrow\{i \in N : c \succ C' \setminus\{c\}\}\}_{c \in C'}

  6. {rc←∑i∈Ncwi}c∈C′\{r_c \leftarrow\sum_{i \in N_c} w_i\}_{c \in C'}

  7. if max⁡c∈C′rc≥q\max_{c \in C'} r_c \ge q then

  8. c′←arg⁡max⁡c∈C′rcc' \leftarrow\arg\max_{c \in C'} r_c

  9. for i∈Nc′i \in N_{c'} do

  10. wi←wi⋅(1−1/rc′)w_i \leftarrow w_i \cdot(1-1/r_{c'})

  11. W←W∪{c′}W \leftarrow W \cup\{c'\}

  12. C′←C′∖{c′}C' \leftarrow C' \setminus\{c'\}

  13. else

  14. c′←arg⁡min⁡c∈C′rcc' \leftarrow\arg\min_{c \in C'} r_c

  15. C′←C′∖{c′}C' \leftarrow C' \setminus\{c'\}

  16. return WW

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 ii we use quota qi=nk+0.01iq_i = \frac{n}{k+0.01i}. We stop at the first iteration the rule returns a committee of size greater than kk 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 m>km > k and k>1k > 1 after the transformation to committee elections described above. For the Scottish local elections dataset, we note that a value of kk 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.

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

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

CDFs of the analyzed metrics for ranked ballots

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

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.

CDF plots of the analyzed metrics for approval ballots

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 kk-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, kk-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 kk-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. kk-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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [12]H. R. Droop. On methods of electing representatives. Journal of the Statistical Society of London, 44(2):141–202, 1881.DOI
  13. [13]M. Dummett. Voting Procedures. Oxford University Press, 1984.
  14. [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. [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. [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. [17]S. Janson. Phragmén’s and thiele’s election methods. Technical report, 2016.arxiv.org/abs/1611.08826
  18. [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. [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. [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. [21]M. Lackner and P. Skowron. Multi-Winner Voting with Approval Preferences. Springer, 2023.
  22. [22]P. Lederer. Proportional representation in rank aggregation. arXiv preprint, 2025. arXiv:2508.16177.arxiv.org/abs/2508.16177
  23. [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. [24]E. Lindahl. Just taxation–a positive solution. In Classics in the Theory of Public Finance, pages 168–176. Springer, 1958.DOI
  25. [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. [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. [27]D. McCune. Monotonicity anomalies in scottish local government elections. Social Choice and Welfare, pages 69–101, 2024.
  28. [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. [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. [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. [31]J. Peters. Candidate monotonicity and proportionality for lotteries and non-resolute rules. Social Choice and Welfare, pages 1–15, 2025.
  32. [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. [33]S. Rey, F. Schmidt, and J. Maly. The (computational) social choice take on indivisible participatory budgeting. arXiv preprint, 2023. arXiv:2303.00621.
  34. [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. [35]P. Skowron. A general theory of proportionality with additive utilities. arXiv preprint, 2026. arXiv:2602.08504.
  36. [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. [37]N. Tideman. The single transferable vote. Journal of Economic Perspectives, 9(1):27–38, 1995.DOI
  38. [38]Wikipedia. List of participatory budgeting votes. https://en.wikipedia.org/wiki/List_of_participatory_budgeting_votes, 2026. Accessed: 2026-07-23.
  39. [39]Wikipedia. Ranked voting. https://en.wikipedia.org/wiki/Ranked_voting, 2026. Accessed: 2026-07-23.
  40. [40]D. Woodall. Properties of preferential election rules. Voting Matters, pages 8–15, 1994.
  41. [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.

Paper details

vlnc:W_azepzjza
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents