Paper deep dive
Reverse Sequential Proportional Approval Voting Rule: Proportionality and Approximation Guarantees
Georgios Papasotiropoulos
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study the Reverse Sequential Proportional Approval Voting Rule (RevSeqPAV) in approval-based committee elections. Despite its historical prominence and practical use, its properties and guarantees are much less understood than those of Sequential PAV. We analyze it along two dimensions: proportional representation (measured by Extended Justified Representation, its approximations, and proportionality degree) and approximation of the maximum PAV score of instances. We first establish strong negative results for general, unrestricted election instances and then identify settings in which the rule provides meaningful fairness and optimization guarantees.
Tags
Links
- Source: https://arxiv.org/abs/2609.35331v1
- Canonical: https://arxiv.org/abs/2609.35331v1
Trouble viewing inline? Open PDF directly →
Full Text
53,516 characters extracted from source content.
Expand or collapse full text
Reverse Sequential Proportional Approval Voting Rule: Proportionality and Approximation Guarantees Georgios Papasotiropoulos University of Warsaw Abstract We study the Reverse Sequential Proportional Approval Voting Rule (RevSeqPAV) in approval-based committee elections. Despite its historical prominence and practical use, its properties and guarantees are much less understood than those of Sequential PAV. We analyze it along two dimensions: proportional representation (measured by Extended Justified Representation, its approximations, and proportionality degree) and approximation of the maximum PAV score of instances. We first establish strong negative results for general, unrestricted election instances and then identify settings in which the rule provides meaningful fairness and optimization guarantees. 1 Introduction More than a century before approval-based committee voting became a standard topic in computational social choice [14], Thorvald N. Thiele had already proposed some of its central rules [21]. His main method for electing k out of m candidates based on voters’ approval ballots assigns to each committee the sum, over all voters, of the harmonic score 1+12+⋯+1t1+ 12+·s+ 1t, where t is the number of committee members approved by the voter. This quantity is now known as the PAV score, and a committee maximizing it is selected. The resulting voting rule is Proportional Approval Voting (PAV). Having observed the combinatorial blow-up in the number of possible committees as the number of candidates grows, Thiele also proposed two greedy methods for approximating the PAV objective: one that builds the committee candidate by candidate, each time selecting the candidate with the largest marginal contribution to the PAV score of the current solution, and one that starts from all candidates and iteratively eliminates the candidate whose removal causes the smallest decrease in the current PAV score until reaching a committee of size k. In modern terminology, these are Sequential PAV (SeqPAV) and Reverse Sequential PAV (RevSeqPAV), respectively. The harmonic function that appears in PAV scores discourages repeatedly representing the same voters and leads to strong proportionality guarantees, most notably Extended Justified Representation (EJR) [1]. However, finding a PAV-optimal committee is NP-hard [2, 18], making its two simple polynomial-time greedy variants natural alternatives for optimizing the objective of PAV [14]. Despite their close connection, the two rules have received very different levels of attention in the computational social choice literature. SeqPAV has been studied extensively; see, indicatively, [7, 9, 10, 11, 12, 16, 17], whereas its reverse counterpart remains much less understood. This is somewhat surprising, given that, of the two methods, Thiele himself recommended the elimination-based one [13]. What is known about RevSeqPAV gives a mixed picture. It satisfies important axiomatic properties like committee monotonicity (in contrast to PAV), support monotonicity (in contrast to SeqPAV) and D’Hondt proportionality [14], and, while it fails even the mild fairness guarantee of Justified Representation (JR), it satisfies it whenever the number of candidates exceeds the desired committee size by at most two [3]. Lackner and Skowron [14] describe RevSeqPAV as a “non-standard” approval-based committee rule because, unlike most such rules, it need not satisfy the natural requirement of electing the most approved candidate when only one candidate is to be selected. In an extensive empirical comparison of approval-based committee rules, Lackner and Skowron [15] found PAV, SeqPAV, and RevSeqPAV among the strongest compromises between utilitarian welfare and representation, and remarked that the latter two are “virtually indistinguishable” in their experiments. Similar findings were reported by Skowron et al. [19], who studied RevSeqPAV, among others, in the context of producing a ranking over the candidates. Despite the limited theoretical attention it has received, RevSeqPAV has seen real-world use. LiquidFeedback, a platform for online democratic deliberation and collective decision making, uses RevSeqPAV (under the name “Harmonic Weighting”) for sorting participants’ proposals in a way that fairly reflects the electorate’s preferences [6, 4]. The formal fairness guarantees of this mechanism have generated some history: a stronger proportionality claim was initially made to justify its use in LiquidFeedback, but was later shown to be false by Aziz [3], leading to a relevant corrigendum [5]. Understanding and formalizing the rule’s potential and limitations is not only of theoretical interest but also practically relevant. 1.1 Contributions This work provides an analysis of RevSeqPAV along two dimensions: its guarantees for proportional representation of the electorate’s preferences and its ability to approximate the maximization objective of PAV. On the proportionality side, we resolve the open question from the textbook by Lackner and Skowron [14] concerning the proportionality degree of RevSeqPAV (see Q9 in Sec. 7.2 and note that RevSeqPAV is the only rule among those considered for which bounds on this fairness metric are missing from Table 4.1 of the book). The proportionality degree of a rule corresponds to a guarantee on the average satisfaction that its outcome provides to voters within a group that, according to the premise of EJR, deserves a satisfaction of ℓ [20]. We prove that RevSeqPAV has proportionality degree zero at every level ℓ : for each ℓ , there is an election containing an ℓ -cohesive group whose members obtain no approved winner. This is a strongly negative result for the rule’s worst-case fairness guarantees, standing in sharp contrast to those of PAV (=ℓ−1)(= -1) and SeqPAV (≈0.7ℓ−1CLOSE,(≈ 0.7 -1, for k≤200k≤ 200). Notably, the same construction also settles a question from the proportional-rankings literature explicitly left open by Skowron et al. [19]. For the measure of proportional representation introduced in that work, our construction shows that RevSeqPAV has a worst-case guarantee of zero. The picture changes sharply when only a very small number of candidates have to be eliminated; we denote this quantity by r:=m−kr:=m-k. This was already known to some extent from Aziz [3], which establishes JR when at most two candidates (r≤2r≤ 2) have to be eliminated. We strengthen this axiomatic guarantee from JR to EJR. We view this result primarily as an existential one, identifying a class of elections on which RevSeqPAV always satisfies EJR, whereas SeqPAV may fail even JR for both r=1r=1 and r=2r=2. Nevertheless, there are real-life scenarios in which the desired committee size is close to the number of candidates, for instance when selecting a board for a small organization, or when the candidates have already undergone a shortlisting process. Additionally, we show that the requirement of r≤2r≤ 2 is tight: for every r≥3r≥ 3 we provide an instance where the outcome of RevSeqPAV violates EJR. Despite the negative result for EJR, we show that RevSeqPAV always guarantees an approximation of this notion. In particular, the rule satisfies (1/r)(1/r)-EJR, which further formalizes the intuition that the rule performs well when k is close to m. In the course of proving this guarantee, we also identify a bound on the size of groups with common preferences that suffices to ensure their representation in every instance; thus, even when EJR fails, sufficiently large groups still receive the level of representation prescribed by the axiom. On the optimization side, we first answer another relevant question posed by Lackner and Skowron [14] (Q17 in Sec. 7.2), which asks whether RevSeqPAV can achieve an approximation factor for the optimal PAV score that is better than the 1−1e1- 1e that SeqPAV achieves. Our answer is firmly negative: RevSeqPAV may return a committee whose PAV score is an arbitrarily small fraction of the optimum. As in our proportionality analysis, we complement this worst-case result with two positive regimes. First, when the goal is to select a committee of size k that constitutes a large fraction of the m candidates, we show that RevSeqPAV remains close to the optimal PAV score. Our bound of km−1 km-1 converges to 11 as k tends to infinity for every fixed number of deletions r, providing a quantitative version of the intuition that this reverse elimination method is particularly attractive when k is close to m [3]. Second, under the assumption that every voter approves at most b candidates, we prove that RevSeqPAV admits an approximation guarantee of 1b 1b. We also show tightness of this bound. Taken together, our results provide a systematic account of the potential and limitations of this century-old elimination rule, identifying its worst-case shortcomings together with settings in which it provides strong guarantees. 2 Preliminaries An election is a tuple E=(N,C,A,k)E=(N,C,A,k), where N=1,…,nN=\1,…,n\ is a set of voters, C is a set of m candidates, A=(Ai)i∈NA=(A_i)_i∈ N is a profile of approval ballots with Ai⊆CA_i C denoting the set of candidates approved by voter i, and k is the desired committee size. We assume that 1≤k<m1≤ k<m and that Ai≠∅A_i≠ for at least one voter i. A (feasible) committee is a set W⊆CW C with |W|=k|W|=k. A voting rule ℛR is a function that given an election E returns a feasible committee ℛ(E)R(E). We denote by r the number of candidates that have to be eliminated from C in order to obtain a feasible committee, that is, r=m−kr=m-k. For a voter i and a candidate set S, we refer to |Ai∩S||A_i∩ S| as the satisfaction of voter i from S, denoted by sati(S)sat_i(S). For a non-empty group of voters V⊆NV N, its average satisfaction from W is avgV(W)=1|V|∑i∈Vsati(W)avg_V(W)= 1|V| _i∈ Vsat_i(W). We also use b=maxi∈N|Ai|b= _i∈ N|A_i| for the maximum ballot size. Definition 1. Given an election E=(N,C,A,k)E=(N,C,A,k), the PAV score of a set of candidates S is PAV(S)=∑i∈NH(sati(S))PAV(S)= _i∈ NH(sat_i(S)), where, for a nonnegative integer t, H(t)H(t) denotes the t-th harmonic number; H(0)=0H(0)=0 and H(t)=1+12+⋯+1tH(t)=1+ 12+·s+ 1t, for t≥1t≥ 1. PAV is the voting rule that returns a feasible committee maximizing PAV score; we denote the maximum PAV score under E by OPTkOPT_k. For a set S⊆CS C and a candidate c∈Sc∈ S, we denote the marginal loss from deleting c from S by ΔS(c)=PAV(S)−PAV(S∖c) _S(c)=PAV(S)-PAV(S \c\). This quantity has a simple voter-wise interpretation: if voter i currently approves t≥1t≥ 1 candidates in S, then this voter contributes 1t 1t to ΔS(c) _S(c) when c∈Aic∈ A_i and 00 otherwise. We use Δ(c) (c) when the set S is clear from the context. RevSeqPAV iteratively removes the candidate whose deletion causes the smallest immediate decrease in the PAV score, i.e., the one of smallest marginal PAV loss. We resolve ties using a fixed priority order on candidates. Definition 2. Let Cm=C_m=C. For every s=m,m−1,…,k+1s=m,m-1,…,k+1, RevSeqPAV identifies the candidate cs∈argminc∈CsΔCs(c)c_s∈ _c∈ C_s _C_s(c) and sets Cs−1=Cs∖csC_s-1=C_s \c_s\. The rule returns the committee W=CkW=C_k. Example 1. Consider an election with C=a,b,cC=\a,b,c\ and k=2k=2. Three voters approve a,b\a,b\, three other voters approve a,c\a,c\, while two voters approve only b\b\ and another two approve only c\c\. RevSeqPAV starts from C3=a,b,cC_3=\a,b,c\. The initial marginal losses are ΔC3(a)=3⋅12+3⋅12=3 _C_3(a)=3· 12+3· 12=3, ΔC3(b)=3⋅12+2=72=ΔC3(c) _C_3(b)=3· 12+2= 72= _C_3(c). Hence, RevSeqPAV deletes a and returns b,c\b,c\, which in this example coincides with the PAV-optimal committee, while SeqPAV would first select a and return either a,b\a,b\ or a,c\a,c\, depending on tie-breaking. We introduce below the two concepts of proportional representation on which Section 3 focuses. Both provide guarantees to sufficiently large groups of voters with common preferences, with the first (EJR) considering the maximum satisfaction attained by a voter within the group and the second (proportionality degree) their average satisfaction. We also define two relaxations of EJR which are due to Aziz et al. [1] and to Skowron [20] and Do et al. [8]. Definition 3. For an integer ℓ≥1 ≥ 1, a group of voters V⊆NV N is ℓ -cohesive if |V|≥ℓn/k|V|≥ n/k and |⋂i∈VAi|≥ℓ| _i∈ VA_i|≥ . A committee W satisfies Extended Justified Representation (EJR) if, for every ℓ≥1 ≥ 1 and every ℓ -cohesive group V, there exists a voter i∈Vi∈ V such that |Ai∩W|≥ℓ|A_i∩ W|≥ . If the guarantee is satisfied for ℓ=1, =1, then W satisfies Justified Representation (JR). If for every integer ℓ≥1 ≥ 1 and every group V⊆NV N such that |V|≥1αℓnk|V|≥ 1α nk and |⋂i∈VAi|≥ℓ| _i∈ VA_i|≥ , there exists a voter i∈Vi∈ V with |Ai∩W|≥ℓ|A_i∩ W|≥ then we say that W satisfies α-EJR, α∈(0,1]α∈(0,1]. A rule ℛR satisfies EJR (respectively, JR and α-EJR) if for every election E,E, it holds that ℛ(E)R(E) satisfies EJR (respectively, JR and α-EJR). Definition 4. A rule ℛR has proportionality degree at least d(ℓ)d( ) at level ℓ if, for every election E, and for every ℓ -cohesive group V, the following holds: avgV(ℛ(E))≥d(ℓ)avg_V(R(E))≥ d( ). We denote by dℛ(ℓ)d_R( ) the largest value for which this guarantee holds for ℛR. In order to evaluate how well RevSeqPAV approximates the objective underlying PAV, for α∈[0,1]α∈[0,1] we say that a rule ℛR has approximation factor α of the optimal PAV-score if PAV(ℛ(E))≥αOPTk,PAV(R(E))≥ _k, for every election E. The worst-case approximation ratio of a rule ℛR is infEPAV(ℛ(E))OPTk _E PAV(R(E))OPT_k. 3 Proportionality Guarantees of RevSeqPAV Recall that for r≤2r≤ 2, RevSeqPAV satisfies the (much weaker than EJR) proportionality axiom of JR [3]. Our first result strengthens this guarantee to EJR. Theorem 1. Let W be a committee returned by Reverse Sequential PAV. If at most two candidates are deleted, i.e., if r≤2r≤ 2, then W satisfies EJR. Proof. Suppose first that m=k+1m=k+1. Then W is a PAV-optimal committee of size k. Since PAV satisfies EJR, so does W. It remains to consider m=k+2m=k+2. Let a be the first deleted candidate and b the second one. Suppose, towards a contradiction, that W violates EJR. Then there exist some ℓ and an ℓ -cohesive group V such that every voter i∈Vi∈ V satisfies |Ai∩W|≤ℓ−1|A_i∩ W|≤ -1. Consider a set T of ℓ candidates that are approved by every voter in V. Since each voter in V obtains fewer than ℓ approved winners, at least one member of T must be deleted. We distinguish two cases. Case 1. Say that b∈Tb∈ T. Immediately before b is deleted, the current set consists of W∪bW∪\b\. Every voter in V approves b and at most ℓ−1 -1 members of W. Hence every such voter approves at most ℓ candidates from W∪bW∪\b\. Therefore their contribution to the marginal loss of b is at least 1/ℓ1/ , and thus ΔW∪b(b)≥|V|/ℓ≥n/k _W∪\b\(b)≥|V|/ ≥ n/k. Consider a candidate set C′C . If a voter i approves t>0t>0 members of C′C , then the removal of any such approved candidate c contributes 1/t1/t to ΔC′(c) _C (c). Since there are exactly t such candidates, voter i contributes in total t⋅(1/t)=1t·(1/t)=1 to ∑c∈C′ΔC′(c) _c∈ C _C (c). If voter i approves no member of C′C , then their contribution is 00. Therefore, ∑c∈C′ΔC′(c)=|i∈N:Ai∩C′≠∅|≤n _c∈ C _C (c)=|\i∈ N:A_i∩ C ≠ \|≤ n. Given that |W∪b|=k+1|W∪\b\|=k+1 and that ∑c∈W∪bΔW∪b(c)≤n _c∈ W∪\b\ _W∪\b\(c)≤ n, there exists a candidate c^∈W∪b c∈ W∪\b\ such that ΔW∪b(c^)≤n/(k+1) _W∪\b\( c)≤ n/(k+1); otherwise, if every candidate had marginal loss strictly greater than n/(k+1)n/(k+1) then their total marginal loss would exceed n. Since Reverse Sequential PAV deletes a candidate of minimum marginal loss, its choice of b implies ΔW∪b(b)≤ΔW∪b(c^)≤n/(k+1) _W∪\b\(b)≤ _W∪\b\( c)≤ n/(k+1). This contradicts ΔW∪b(b)≥n/k _W∪\b\(b)≥ n/k, since n/k>n/(k+1)n/k>n/(k+1). Case 2. Say now that b∉Tb∉ T. Since at least one candidate in T must be deleted and the only deleted candidates are a and b, we have a∈Ta∈ T. Hence all ℓ−1 -1 candidates in T∖aT \a\ belong to W. The group V witnesses a violation of EJR, so every voter i∈Vi∈ V satisfies |Ai∩W|≤ℓ−1|A_i∩ W|≤ -1. It follows that no voter in V can approve any winner outside T∖aT \a\; otherwise, that voter would approve at least ℓ members of W. Let x be the number of voters in V who approve b. Before the first deletion, every voter in V approves the ℓ candidates in T, and may additionally approve b, but approves no other candidate. More precisely, the |V|−x|V|-x voters who do not approve b have exactly ℓ approved candidates in the initial candidate set, namely the candidates in T, whereas the x voters who approve b have exactly ℓ+1 +1 approved candidates, namely the candidates in T∪bT∪\b\. Since every voter in V approves a, the contribution of the first group to the initial marginal loss of a is (|V|−x)/ℓ(|V|-x)/ , while the contribution of the second group is x/(ℓ+1)x/( +1). Hence the total contribution of voters in V to the marginal loss of a is (|V|−x)/ℓ+x/(ℓ+1)(|V|-x)/ +x/( +1). By contrast, only the x voters in the second group approve b, and each of them initially has ℓ+1 +1 approved candidates. Thus the total contribution of voters in V to the initial marginal loss of b is x/(ℓ+1)x/( +1). Let α and β denote the contributions of voters outside V to the initial marginal losses of a and b, respectively. Since Reverse Sequential PAV deletes a before b, we have (|V|−x)/ℓ+x/(ℓ+1)+α≤x/(ℓ+1)+β(|V|-x)/ +x/( +1)+α≤ x/( +1)+β. Hence β≥(|V|−x)/ℓ+α≥(|V|−x)/ℓβ≥(|V|-x)/ +α≥(|V|-x)/ . Observe that, as Reverse Sequential PAV proceeds, the contribution of any voter to the marginal loss of a fixed candidate c that she approves and that has not yet been deleted can only increase. Hence, after a is deleted, the contribution of voters outside V to the marginal loss of b is still at least (|V|−x)/ℓ(|V|-x)/ . Moreover, after a is deleted, each of the x voters in V who approves b has exactly ℓ approved remaining candidates: the ℓ−1 -1 members of T∖aT \a\ and b. Hence these voters contribute x/ℓx/ to the marginal loss of b. It follows that ΔW∪b(b)≥(|V|−x)/ℓ+x/ℓ=|V|/ℓ≥n/k _W∪\b\(b)≥(|V|-x)/ +x/ =|V|/ ≥ n/k. Therefore, again, some candidate among the k+1k+1 remaining candidates must have marginal loss at most n/(k+1)n/(k+1). Thus, b cannot be the candidate selected for deletion. Since both cases lead to a contradiction the proof is complete. ∎ While this positive guarantee applies to the rather specific case of m−k≤2m-k≤ 2, as noted in Section 1, there are reasonable real-world scenarios in which k can be this close to m. Unfortunately, the guarantee cannot be extended further, as established by the tightness result below. Theorem 2. For every r≥3r≥ 3 there exists an election with m−k=rm-k=r in which the committee returned by Reverse Sequential PAV violates EJR. Proof. Consider an election with k=12k=12, m=15m=15, n=600n=600 and let C=c1,c2,x1,x2,y1,…,y11C=\c_1,c_2,x_1,x_2,y_1,…,y_11\. The approval profile is as follows. Number of voters Approved candidates 5050 c1,c2,x1c_1,c_2,x_1 5050 c1,c2,x2c_1,c_2,x_2 1717 x1x_1 1717 x2x_2 11 c1c_1 465465 y1,…,y11y_1,…,y_11 Let V consist of the first 100100 voters. Since |V|=100=2n/k|V|=100=2n/k and all voters in V commonly approve c1c_1 and c2c_2, the group V is 22-cohesive. We first present at a high level how RevSeqPAV works in this instance. When the temporary committee consists of the whole set of candidates C, the presence of x1x_1 and x2x_2 in the committee makes c2c_2 look redundant. Initially, each half of the aforementioned cohesive group has three approved candidates, so their common candidates have a small marginal loss causing RevSeqPAV to delete c2c_2. But then it subsequently deletes x1x_1 and x2x_2 as well. In other words, the alternatives that made c2c_2 look dispensable do not survive themselves and this leads to a violation of EJR witnessed by V. We now follow in detail the Reverse Sequential PAV deletions. Initially, Δ(c2)=100/3 (c_2)=100/3, Δ(x1)=Δ(x2)=50/3+17=101/3 (x_1)= (x_2)=50/3+17=101/3, Δ(c1)=100/3+1=103/3 (c_1)=100/3+1=103/3, and Δ(yj)=465/11 (y_j)=465/11 for every j. Thus c2c_2 is deleted first. After deleting c2c_2, Δ(x1)=Δ(x2)=50/2+17=42 (x_1)= (x_2)=50/2+17=42, Δ(c1)=100/2+1=51 (c_1)=100/2+1=51, and Δ(yj)=465/11>42 (y_j)=465/11>42. Hence one of x1x_1 and x2x_2 is deleted next. Suppose it is x1x_1 using some fixed tie-breaking rule. After deleting x1x_1, we still have Δ(x2)=42 (x_2)=42, while Δ(yj)=465/11>42 (y_j)=465/11>42. Moreover, the marginal loss of c1c_1 has increased to 50+25+1=7650+25+1=76. Therefore x2x_2 is deleted third. The resulting committee is W=c1,y1,…,y11W=\c_1,y_1,…,y_11\. Every voter in the 22-cohesive group V approves exactly one member of W, namely c1c_1, hence EJR is violated. This proves the claim for r=3r=3. For any r>3r>3, add r−3r-3 candidates approved by no voter. Each such candidate has marginal loss 00, so all of them are deleted before any candidate in the construction above. Afterwards the same three deletions occur and the same EJR violation results. Hence EJR can fail for every r≥3r≥ 3.∎ On the positive side, while EJR cannot be guaranteed for arbitrary instances, an approximation of it is possible—refer to Definition 3 for the relevant definition. Our result provides a first bound, from which an easier-to-interpret guarantee (Corollary 4) follows directly. Theorem 3. Let r≥3r≥ 3 and set α=k+rkrα= k+rkr. For every ε>0 >0 such that 0<α−ε≤10<α- ≤ 1, the committee returned by Reverse Sequential PAV satisfies (α−ε)(α- )-EJR. Proof. Suppose, towards a contradiction, that there exist an integer ℓ≥1 ≥ 1 and a group V such that |V|≥ℓn(α−ε)k|V|≥ n(α- )k, the voters in V commonly approve at least ℓ candidates, and every voter i∈Vi∈ V satisfies |Ai∩W|≤ℓ−1|A_i∩ W|≤ -1, where W is the outcome of RevSeqPAV. Let T be a set of ℓ candidates commonly approved by all voters in V. Since no voter in V obtains ℓ approved winners, at least one candidate from T must be deleted. Consider one such commonly approved candidate c at the moment when it is deleted, and let t be the number of deletions that still remain at that moment, counting the deletion of c itself. Thus, the current candidate set has size k+tk+t, where 1≤t≤r1≤ t≤ r. Each voter in V approves at most ℓ−1 -1 final winners. In addition, at most the t candidates that will still be deleted can currently be approved by that voter. Hence every voter in V currently approves at most ℓ−1+t -1+t candidates. Since every voter in V approves c, their total contribution to the marginal loss of c is at least |V|ℓ−1+t |V| -1+t. Using |V|≥ℓn(α−ε)k|V|≥ n(α- )k, we obtain Δ(c)≥ℓn(α−ε)k(ℓ−1+t) (c)≥ n(α- )k( -1+t). On the other hand, there are currently k+tk+t candidates, and the sum of their marginal losses is at most n. Since Reverse Sequential PAV deletes a candidate of minimum marginal loss, Δ(c)≤nk+t (c)≤ nk+t. Combining the two inequalities gives ℓn(α−ε)k(ℓ−1+t)≤nk+t n(α- )k( -1+t)≤ nk+t, and hence 1α−ε≤k(ℓ−1+t)ℓ(k+t) 1α- ≤ k( -1+t) (k+t). We note here that for an ℓ -cohesive group we would have 1≤k(ℓ−1+t)ℓ(k+t)⇔ℓt≤kt−k⇔ℓ≤k(1−1t)1≤ k( -1+t) (k+t) t≤ kt-k ≤ k(1- 1t). It holds that k(ℓ−1+t)ℓ(k+t)≤ktk+t k( -1+t) (k+t)≤ ktk+t, because ℓ−1+tℓ≤t -1+t ≤ t is equivalent to (ℓ−1)(t−1)≥0( -1)(t-1)≥ 0. Finally, since t≤rt≤ r and the function t↦kt/(k+t)t kt/(k+t) is increasing, 1α−ε≤ktk+t≤krk+r=1α 1α- ≤ ktk+t≤ krk+r= 1α. This contradicts ε>0 >0. ∎ Corollary 4. Let W be a committee returned by Reverse Sequential PAV. The committee W satisfies 1r 1r-EJR. Moreover, even when W fails EJR, it holds that for every integer ℓ≥1 ≥ 1 satisfying ℓ>k(1−1r) >k (1- 1r ), every ℓ -cohesive group satisfies the EJR requirement. Proof. If r≤2r≤ 2, both claims follow from Theorem 1. Suppose therefore that r≥3r≥ 3. Applying Theorem 3 with ε=1/k =1/k gives (1/r)(1/r)-EJR, since k+rkr−1k=1r k+rkr- 1k= 1r. For the second claim, recall from the proof of Theorem 3 that if an ℓ -cohesive group violates the EJR requirement and t≤rt≤ r deletions remain when one of its commonly approved candidates is deleted, then ℓ≤k(1−1t) ≤ k (1- 1t ). Since t≤rt≤ r, ℓ≤k(1−1t)≤k(1−1r) ≤ k (1- 1t )≤ k (1- 1r ). Hence no ℓ -cohesive group with ℓ>k(1−1r) >k (1- 1r ) can violate the EJR requirement. ∎ We now turn to proportionality degree, for which the performance of RevSeqPAV was previously unknown [14]. While this metric yields substantial guarantees for PAV and SeqPAV, our result shows that the same is not true for RevSeqPAV, at least on unrestricted instances. This is consistent with our earlier negative finding for EJR in the unrestricted setting (Theorem 2). Theorem 5. For every integer ℓ≥1 ≥ 1, the proportionality degree of Reverse Sequential PAV at ℓ is exactly 00. Proof. First we note that dRevSeqPAV(ℓ)≥0d_RevSeqPAV( )≥ 0 so it suffices to show that dRevSeqPAV(ℓ)≤0d_RevSeqPAV( )≤ 0. To this end, fix ℓ≥1 ≥ 1 and let d=4ℓd=4 . We construct an election containing an ℓ -cohesive group whose members obtain no approved winner. Let C⋆=c1,…,cℓC =\c_1,…,c_ \ be a set of ℓ common candidates. Create d pairwise disjoint blocks X1,…,XdX_1,…,X_d, each containing exactly d candidates. Finally, create a set Y=y1,…,ykY=\y_1,…,y_k\ of k=d(d+1)k=d(d+1) candidates. The voters are as follows where R=d(3d2+7d+3)R=d(3d^2+7d+3). Voter type Number of voters Approved candidates VjV_j, for each j∈1,…,dj∈\1,…,d\ d+1d+1 C⋆∪XjC ∪ X_j UxU_x, for each x∈⋃jXjx∈ _jX_j d xx Z R Y Let V=⋃j=1dVjV= _j=1^dV_j. Then |V|=d(d+1)|V|=d(d+1). There are d2d^2 candidates in the sets XjX_j, so the second type of voters corresponds to d3d^3 voters. Therefore the total number of voters is n=d(d+1)+d3+R=4d(d+1)2n=d(d+1)+d^3+R=4d(d+1)^2. Since d=4ℓd=4 and k=d(d+1)k=d(d+1), we have ℓn/k=(d/4)⋅4d(d+1)2/[d(d+1)]=d(d+1)=|V| n/k=(d/4)· 4d(d+1)^2/[d(d+1)]=d(d+1)=|V|. Moreover, every voter in V approves all ℓ candidates in C⋆C . Hence V is ℓ -cohesive. We will show that Reverse Sequential PAV deletes first all candidates in C⋆C , then all candidates in the sets XjX_j, leaving precisely Y as the final committee. Suppose that q≥1q≥ 1 candidates from C⋆C remain and no candidate from any XjX_j or from Y has yet been deleted. A remaining common candidate c∈C⋆c∈ C has marginal loss Δ(c)=d(d+1)/(q+d) (c)=d(d+1)/(q+d). For any x∈Xjx∈ X_j, its d+1d+1 voters of type VjV_j each currently approve q+dq+d candidates, while its d singleton voters contribute one each. Hence Δ(x)=(d+1)/(q+d)+d (x)=(d+1)/(q+d)+d. The difference is Δ(x)−Δ(c)=(dq+1)/(q+d)>0 (x)- (c)=(dq+1)/(q+d)>0. Thus every remaining common candidate has strictly smaller marginal loss than every candidate in the sets XjX_j. For every y∈Yy∈ Y, Δ(y)=R/k=(3d2+7d+3)/(d+1)>d (y)=R/k=(3d^2+7d+3)/(d+1)>d, while Δ(c)≤d (c)≤ d. Thus every common candidate also has strictly smaller marginal loss than every candidate in Y. Consequently, Reverse Sequential PAV deletes all candidates in C⋆C before deleting anything else. Now suppose all common candidates have been deleted. Consider a block XjX_j with s≥1s≥ 1 candidates still remaining. For every remaining x∈Xjx∈ X_j, Δ(x)=d+(d+1)/s≤2d+1 (x)=d+(d+1)/s≤ 2d+1. On the other hand, every y∈Yy∈ Y still has Δ(y)=(3d2+7d+3)/(d+1)>2d+1 (y)=(3d^2+7d+3)/(d+1)>2d+1. Therefore, as long as any candidate from some XjX_j remains, Reverse Sequential PAV deletes an X-candidate rather than a Y-candidate. It follows that all candidates in C⋆∪X1∪⋯∪XdC ∪ X_1∪·s∪ X_d are deleted before any candidate in Y. Since |Y|=k|Y|=k, the final committee is exactly W=YW=Y. ∎ We note that RevSeqPAV can equivalently be viewed as a ranking rule. Starting from the full candidate set, the candidate deleted first is placed last in the ranking, the candidate deleted second is placed second-to-last, and so on. Consequently, for every k, the top-k prefix of the resulting ranking is exactly the committee returned by RevSeqPAV when the target committee size is k. We now recall a proportionality notion for rankings introduced by Skowron et al. [19]. The setting examined in that paper is as follows: each voter submits an approval ballot, yet the outcome of an election is a ranking over all candidates. For some k we use R≤kR_≤ k to denote the first k candidates in the output ranking. Using the same construction as in Theorem 5, we resolve a question left open in that work. For a group V and a prefix of length k, recall that its justifiable demand is jd(V,k)=min⌊|V|k/n⌋,λ(V)jd(V,k)= \ |V|k/n ,λ(V)\, where λ(V)=|⋂i∈VAi|λ(V)=| _i∈ VA_i| is the number of candidates commonly approved by the group. Its average satisfaction in the prefix R≤kR_≤ k is avgV(R≤k)=1|V|∑i∈V|Ai∩R≤k|avg_V(R_≤ k)= 1|V| _i∈ V|A_i∩ R_≤ k|. The proportionality quality of a ranking is the minimum ratio between the average satisfaction of a group V in R≤kR_≤ k and the justifiable demand of V over all values of k and sets of voters V such that jd(V,k)>0jd(V,k)>0. Corollary 6. The worst-case proportionality quality of rankings returned by Reverse Sequential PAV is 00. Proof. Since proportionality quality is nonnegative, it suffices to construct a Reverse Sequential PAV ranking containing a prefix for which some group has average satisfaction 00 while having positive justifiable demand. Consider the construction used in Theorem 5 for some ℓ≥1 ≥ 1. There, the final committee W has size k, and there exists a group V such that |V|=ℓn/k|V|= n/k, λ(V)≥ℓλ(V)≥ , and |Ai∩W|=0|A_i∩ W|=0 for every voter i∈Vi∈ V. Let R be the complete ranking produced by Reverse Sequential PAV. Since its top-k prefix is precisely the set W, we have avgV(R≤k)=0avg_V(R_≤ k)=0. On the other hand, jd(V,k)=min⌊|V|k/n⌋,λ(V)=minℓ,λ(V)=ℓjd(V,k)= \ |V|k/n ,λ(V)\= \ ,λ(V)\= . Hence the worst-case proportionality quality of Reverse Sequential PAV is 00. ∎ 4 Approximation Guarantees of RevSeqPAV In this section, we study how well RevSeqPAV approximates the maximum PAV score, i.e., how close the PAV score it achieves is to the optimum. SeqPAV guarantees a constant fraction of the optimal PAV score. As our first result shows, the same is far from true for RevSeqPAV on general instances. Our proof leverages the observation by Lackner and Skowron [14] that for k=1k=1 the rule’s outcome can be counterintuitive. Theorem 7. The worst-case approximation ratio of Reverse Sequential PAV with respect to the PAV score is 00. Proof. Fix an integer d≥2d≥ 2 and say that k=1k=1. Consider one candidate a and d pairwise disjoint sets X1,…,XdX_1,…,X_d, each containing exactly d candidates. Thus there are 1+d21+d^2 candidates in total. The approval profile is as follows. Voter type Number of voters Approved candidates VjV_j, for each j∈1,…,dj∈\1,…,d\ d+1d+1 a∪Xj\a\∪ X_j UxU_x, for each x∈⋃jXjx∈ _jX_j d xx Initially, candidate a is approved by all d(d+1)d(d+1) voters of the first type. Each such voter currently approves exactly d+1d+1 candidates. Hence ΔC(a)=d(d+1)/(d+1)=d _C(a)=d(d+1)/(d+1)=d. Consider instead some candidate x∈Xjx∈ X_j. It is approved by the d+1d+1 voters in VjV_j, each of whom contributes 1/(d+1)1/(d+1), and by its d singleton voters, each of whom contributes 11. Therefore ΔC(x)=(d+1)/(d+1)+d=d+1 _C(x)=(d+1)/(d+1)+d=d+1. Thus ΔC(a)=d<d+1=ΔC(x) _C(a)=d<d+1= _C(x) for every x∈⋃jXjx∈ _jX_j, and Reverse Sequential PAV deletes a first. Since the target committee size is 11, the candidate eventually returned by Reverse Sequential PAV must therefore be some candidate x∈⋃jXjx∈ _jX_j. Such a candidate is approved by exactly (d+1)+d=2d+1(d+1)+d=2d+1 voters. Hence PAV(WRev)=2d+1PAV(W_Rev)=2d+1. By contrast, the singleton committee a\a\ has PAV score equal to the approval score of a, namely PAV(a)=d(d+1)PAV(\a\)=d(d+1). For d≥2d≥ 2, this is larger than 2d+12d+1, so a\a\ is a PAV-optimal singleton committee. Consequently, PAV(WRev)OPT1=2d+1d(d+1) PAV(W_Rev)OPT_1= 2d+1d(d+1). As d tends to infinity, this ratio tends to 00. Hence the worst-case approximation ratio of Reverse Sequential PAV with respect to the PAV score is 00, even when the committee size is fixed to k=1k=1. ∎ Theorem 7 concerns the unrestricted worst-case. In the remainder of the paper, we identify restrictions under which RevSeqPAV admits positive approximation guarantees. Hence, as was the case with proportionality guarantees, there are realms where the rule performs well. First, we identify r as a crucial parameter again, as in Section 3. We show that when only a small number of candidates are to be deleted, Reverse Sequential PAV achieves a strong approximation guarantee. In particular, this guarantee is strong when k constitutes a large fraction of m, and for every fixed number of deletions r it converges to 11 as k tends to infinity. Moreover, this result implies the existence of a regime, when r−1<ke−1≈0.582kr-1< ke-1≈ 0.582k, in which our lower bound for RevSeqPAV exceeds the standard 1−1/e1-1/e approximation guarantee known for SeqPAV. Theorem 8. Let W be a commitee returned by Reverse Sequential PAV. Then PAV(W)≥km−1OPTk=k+r−1OPTkPAV(W)≥ km-1OPT_k= kk+r-1OPT_k. Proof. For every s∈k,…,ms∈\k,…,m\, let CsC_s denote the set of s candidates remaining after m−sm-s deletions of Reverse Sequential PAV. Thus Cm=C_m=C is the full candidate set and Ck=WC_k=W is the final committee. We first consider the first deletion. Recall that the first deletion produces a PAV-optimal set among all sets of size m−1m-1. Now let W⋆W be a PAV-optimal committee of size k, so that PAV(W⋆)=OPTkPAV(W )=OPT_k. Since m−1≥km-1≥ k, we can extend W⋆W to some set S of size m−1m-1 by adding arbitrary candidates. The PAV score is monotone with respect to set inclusion: adding candidates cannot decrease the number of approved selected candidates of any voter, and hence cannot decrease their harmonic utility. Therefore, PAV(S)≥PAV(W⋆)=OPTkPAV(S) (W )=OPT_k. Since Cm−1C_m-1 maximizes the PAV score over all sets of size m−1m-1, we conclude that PAV(Cm−1)≥PAV(S)≥OPTkPAV(C_m-1) (S) _k. We next bound the loss caused by each subsequent deletion. Consider a step at which the current candidate set is CsC_s, where k+1≤s≤m−1k+1≤ s≤ m-1. Recall that ΔCs(c)=PAV(Cs)−PAV(Cs∖c) _C_s(c)=PAV(C_s)-PAV(C_s \c\) is the marginal PAV loss caused by deleting c. For a voter i, let ti=|Ai∩Cs|t_i=|A_i∩ C_s|. If ti=0t_i=0, then voter i contributes 00 to the marginal loss of every candidate. If ti>0t_i>0, then deleting any one of the tit_i candidates in Ai∩CsA_i∩ C_s contributes H(ti)−H(ti−1)=1/tiH(t_i)-H(t_i-1)=1/t_i to the marginal loss of that candidate. Since there are tit_i such candidates, voter i contributes in total ti⋅(1/ti)=1t_i·(1/t_i)=1 to the sum of the marginal losses of all candidates in CsC_s. Consequently, ∑c∈CsΔCs(c)=|i∈N:Ai∩Cs≠∅| _c∈ C_s _C_s(c)=|\i∈ N:A_i∩ C_s≠ \|. On the other hand, every voter in i∈N:Ai∩Cs≠∅\i∈ N:A_i∩ C_s≠ \ contributes at least 11 to PAV(Cs)PAV(C_s). Therefore, ∑c∈CsΔCs(c)≤PAV(Cs) _c∈ C_s _C_s(c) (C_s). There are s candidates in CsC_s. Therefore, there exists some candidate c∈Csc∈ C_s satisfying ΔCs(c)≤PAV(Cs)/s _C_s(c) (C_s)/s. Therefore, if csc_s denotes the candidate deleted at this step, then ΔCs(cs)≤PAV(Cs)/s _C_s(c_s) (C_s)/s. It follows that PAV(Cs−1)=PAV(Cs)−ΔCs(cs)≥PAV(Cs)−PAV(Cs)s=s−1sPAV(Cs)PAV(C_s-1)=PAV(C_s)- _C_s(c_s) (C_s)- PAV(C_s)s= s-1sPAV(C_s). Thus, when s candidates remain, Reverse Sequential PAV preserves at least an (s−1)/s(s-1)/s fraction of the current PAV score. We now apply this inequality successively, starting from Cm−1C_m-1 and following the sequence of deletions down to Ck=WC_k=W. For the first step, PAV(Cm−2)≥m−2m−1PAV(Cm−1)PAV(C_m-2)≥ m-2m-1PAV(C_m-1). For the next step, PAV(Cm−3)≥m−3m−2PAV(Cm−2)PAV(C_m-3)≥ m-3m-2PAV(C_m-2). Substituting the first inequality into the second gives PAV(Cm−3)≥m−3m−2m−2m−1PAV(Cm−1)PAV(C_m-3)≥ m-3m-2 m-2m-1PAV(C_m-1). Continuing in the same way, each subsequent deletion contributes an additional factor (s−1)/s(s-1)/s. Since the final set is Ck=WC_k=W, we obtain PAV(W)≥k+1⋅k+1k+2⋯m−3m−2⋅m−2m−1PAV(Cm−1)PAV(W)≥ kk+1· k+1k+2·s m-3m-2· m-2m-1PAV(C_m-1). Equivalently, PAV(W)≥(∏s=k+1m−1s−1s)PAV(Cm−1)≥km−1PAV(Cm−1)≥km−1OPTkPAV(W)≥ ( _s=k+1^m-1 s-1s )PAV(C_m-1)≥ km-1PAV(C_m-1)≥ km-1OPT_k. ∎ We now present a second positive result, which applies to instances with a bounded number of approvals per voter and shows that RevSeqPAV can perform well even independently of the value of r. Theorem 9. Let W be a committee returned by Reverse Sequential PAV. Then PAV(W)≥1bOPTkPAV(W)≥ 1bOPT_k. Proof. Let W⋆W be a PAV-optimal committee of size k. Also, let I=W∩W⋆I=W∩ W , D=W⋆∖WD=W W, and R=W∖W⋆R=W W . Thus D contains the candidates that belong to the optimal committee but were deleted by Reverse Sequential PAV, while R contains the candidates that survive in W but do not belong to the optimal committee. Since |W|=|W⋆||W|=|W |, we have |D|=|R||D|=|R|. Therefore we can pair every candidate c∈Dc∈ D with a distinct candidate ϕ(c)∈Rφ(c)∈ R through a bijection ϕ:D→Rφ:D→ R. We first compare the marginal loss of a deleted optimal candidate c with the marginal loss of its paired surviving candidate ϕ(c)φ(c). Fix some c∈Dc∈ D, and let ScS_c be the set of candidates that are still present immediately before Reverse Sequential PAV deletes c. Define δc=ΔSc(c) _c= _S_c(c). Since ϕ(c)∈Wφ(c)∈ W, candidate ϕ(c)φ(c) survives until the end and is therefore still present in ScS_c. Reverse Sequential PAV deletes a candidate of minimum marginal loss, so δc=ΔSc(c)≤ΔSc(ϕ(c)) _c= _S_c(c)≤ _S_c(φ(c)). Moreover, the marginal loss of a fixed surviving candidate can only increase as other candidates are deleted. Indeed, if a voter approves ϕ(c)φ(c), their contribution to its marginal loss is the reciprocal of the number of their currently remaining approved candidates. As candidates are deleted, this denominator can only decrease. Hence ΔSc(ϕ(c))≤ΔW(ϕ(c)) _S_c(φ(c))≤ _W(φ(c)). Combining these inequalities gives δc≤ΔW(ϕ(c)) _c≤ _W(φ(c)). We next relate δc _c to the benefit that the optimal committee obtains from candidate c. Consider adding c to the common part I. Let voter i approve c, and suppose that immediately before c was deleted she approved tit_i candidates that were still present. Their contribution to δc _c was therefore 1/ti1/t_i. Since every ballot contains at most b candidates, we have ti≤bt_i≤ b. Hence 1≤b/ti1≤ b/t_i. When we add c to I, voter i gains at most 11: if she currently approves qiq_i candidates in I, their gain is 1/(qi+1)≤11/(q_i+1)≤ 1. Therefore 1/(qi+1)≤b/ti1/(q_i+1)≤ b/t_i. Thus, voter by voter, the contribution to the marginal gain of adding c to I is at most b times the contribution to the marginal loss of c when Reverse Sequential PAV deleted it. Summing over all voters who approve c, we obtain PAV(I∪c)−PAV(I)≤bδcPAV(I∪\c\)-PAV(I)≤ b _c. Note that the PAV score is monotone and submodular. Indeed, if a voter currently approves q selected candidates, the marginal contribution of an additional approved candidate is 1/(q+1)1/(q+1), which can only decrease as the selected set grows. Now consider adding all candidates in D to I. Since the PAV score is submodular, the total gain from adding all of them is at most the sum of their individual gains when each is added directly to I. Hence PAV(W⋆)−PAV(I)≤∑c∈D(PAV(I∪c)−PAV(I))≤b∑c∈DδcPAV(W )-PAV(I)≤ _c∈ D (PAV(I∪\c\)-PAV(I) )≤ b _c∈ D _c. Using the pairing between D and R, together with δc≤ΔW(ϕ(c)) _c≤ _W(φ(c)), we get ∑c∈Dδc≤∑w∈RΔW(w) _c∈ D _c≤ _w∈ R _W(w). It remains to bound the latter quantity. Starting from W, delete the candidates in R one by one until only I remains. The marginal loss of a candidate can only increase as other candidates are deleted. Therefore, for every w∈Rw∈ R, its marginal loss measured initially at W is no larger than its marginal loss at the moment when it is actually removed in this sequence. Consequently, ∑w∈RΔW(w)≤PAV(W)−PAV(I) _w∈ R _W(w) (W)-PAV(I). Hence, PAV(W⋆)−PAV(I)≤b(PAV(W)−PAV(I))⇔PAV(W⋆)≤bPAV(W)−(b−1)PAV(I)≤bPAV(W)PAV(W )-PAV(I)≤ b (PAV(W)-PAV(I) ) (W )≤ bPAV(W)-(b-1)PAV(I)≤ bPAV(W). ∎ We conclude by establishing tightness for the result of Theorem 9. Theorem 10. For every integer b≥2b≥ 2 and every ε>0 >0, there exists an election for which PAV(W)<(1b+ε)OPT1PAV(W)<( 1b+ )OPT_1, where W is the committee returned by Reverse Sequential PAV. Proof. Fix b≥2b≥ 2 and an integer t>0t>0. Consider an instance where k=1k=1 and there is one candidate a and t pairwise disjoint sets X1,…,XtX_1,…,X_t, each containing exactly b−1b-1 candidates. Consider a set of voters VjV_j, for each j∈1,…,tj∈\1,…,t\ that contains b voters each approving a∪Xj\a\∪ X_j. Also say that there are t voters in each set UxU_x, for each x∈⋃jXj,x∈ _jX_j, each one approving x. Note that the maximum ballot size is b. We first consider candidate a. It is approved by all tbtb voters in the groups V1,…,VtV_1,…,V_t. Each of these voters currently approves exactly b candidates, and therefore contributes 1/b1/b to the marginal loss of a. Thus ΔC(a)=tb⋅1b=t _C(a)=tb· 1b=t. Now consider any candidate x∈Xjx∈ X_j. Candidate x is approved by the b voters in VjV_j, who together contribute b⋅1b=1b· 1b=1, and by its t supporters, who contribute t in total. Hence ΔC(x)=t+1 _C(x)=t+1. Therefore, ΔC(a)=t<t+1=ΔC(x) _C(a)=t<t+1= _C(x) for every x∈⋃jXjx∈ _jX_j. Consequently, Reverse Sequential PAV deletes a in its first step. The candidate eventually returned by the rule must be some candidate x∈⋃jXjx∈ _jX_j. Every such candidate has b+tb+t approvals: b from the voters in its group VjV_j and t from its singleton supporters. Therefore, PAV(W)=b+tPAV(W)=b+t. By contrast, candidate a has tbtb approvals. For all sufficiently large t, we have tb>b+ttb>b+t, and hence a\a\ is a PAV-optimal singleton committee. Thus OPT1=tbOPT_1=tb. It follows that PAV(W)OPT1=t+btb=1b+1t PAV(W)OPT_1= t+btb= 1b+ 1t. As t tends to infinity, this ratio converges to 1/b1/b. Hence, for every ε>0 >0, choosing t>1/εt>1/ and t>b−1t> bb-1 gives PAV(W)OPT1<1b+ε PAV(W)OPT_1< 1b+ . ∎ 5 Conclusions Our results reveal a sharp contrast between the behavior of RevSeqPAV in adversarial and in restricted instances. In the worst case, it may fail EJR and produce a ranking of proportionality quality 00, has proportionality degree 00, and provides no positive constant approximation of the optimal PAV score. On the positive side, it satisfies EJR for r≤2r≤ 2 (and this is tight), provides a 1r 1r-approximation of EJR and offers the representation guarantee of EJR to sufficiently large cohesive groups of voters; it also achieves good approximations of the optimal PAV-score when k is close to m (specifically km−1 km-1) or voters approve a few candidates (specifically 1b 1b—and this is tight). An interesting question is whether bounded ballot size also improves proportionality guarantees. It is also important to understand which other restrictions can yield a positive proportionality degree. More broadly, understanding the domains on which SeqPAV and RevSeqPAV coincide, or even return a PAV-optimal committee, is an important direction. Finally, further empirical comparisons, e.g. complementing those already conducted for SeqPAV, could clarify when the two rules behave similarly in practice, when their differences emerge, and how their performance compares across different families of elections and various metrics. Acknowledgements. G. Papasotiropoulos was supported by the European Union (ERC, PRO-DEMOCRATIC, 101076570). Views and opinions expressed are however those of the author 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. ChatGPT-5.6 Sol assisted with developing counterexamples, refining proofs, and editing the manuscript; it also identified the connection to the proportional rankings literature and provided the argument establishing Corollary 6. References [1] H. Aziz, M. Brill, V. Conitzer, E. Elkind, R. Freeman, and T. Walsh (2017) Justified representation in approval-based committee voting. Social Choice and Welfare 48 (2), p. 461–485. Cited by: §1, §2. [2] H. Aziz, S. Gaspers, J. Gudmundsson, S. Mackenzie, N. Mattei, and T. Walsh (2015) Computational aspects of multi-winner approval voting. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, Cited by: §1. [3] H. Aziz (2017) A note on justified representation under the reverse sequential PAV rule. Note: Unpublished manuscript. (Accessed: 2026-09-26)https://cgi.cse.unsw.edu.au/~haziz/invseqpav.pdf Cited by: §1.1, §1.1, §1, §1, §3. [4] J. Behrens, A. Kistner, A. Nitsche, and B. Swierczek (2014) The principles of liquidfeedback. Interaktive Demokratie e. V.. Cited by: §1. [5] J. Behrens, A. Kistner, A. Nitsche, and B. Swierczek (2018) Corrigendum. The Liquid Democracy Journal 6, p. 4–5. Cited by: §1. [6] J. Behrens (2014) The evolution of proportional representation in LiquidFeedback. The Liquid Democracy Journal 1, p. 32–41. Cited by: §1. [7] N. Boehmer, M. Brill, A. Cevallos, J. Gehrlein, L. Sánchez-Fernández, and U. Schmidt-Kraepelin (2024) Approval-based committee voting in practice: A case study of (over-)representation in the Polkadot blockchain. In Proceedings of the AAAI Conference on Artificial Intelligence, Cited by: §1. [8] V. Do, M. Hervouin, J. Lang, and P. Skowron (2022) Online approval committee elections. In Proceedings of the International Joint Conference on Artificial Intelligence, Cited by: §2. [9] P. Faliszewski, G. Gawron, and B. Kusek (2022) Robustness of greedy approval rules. In Proceedings of the European Conference on Multi-Agent Systems, Cited by: §1. [10] P. Faliszewski, M. Lackner, K. Sornat, and S. Szufa (2023) An experimental comparison of multiwinner voting rules on approval elections. In Proceedings of the International Joint Conference on Artificial Intelligence, Cited by: §1. [11] J. Israel and M. Brill (2025) Dynamic proportional rankings. Social Choice and Welfare 64 (1–2), p. 221–261. Cited by: §1. [12] Ł. Janeczko and P. Faliszewski (2023) Ties in multiwinner approval voting. In Proceedings of the International Joint Conference on Artificial Intelligence, Cited by: §1. [13] S. Janson (2016) Phragmén’s and Thiele’s election methods. arXiv:1611.08826. Cited by: §1. [14] M. Lackner and P. Skowron (2023) Multi-winner voting with approval preferences. Springer. Cited by: §1.1, §1.1, §1, §1, §1, §3, §4. [15] M. Lackner and P. Skowron (2020) Utilitarian welfare and representation guarantees of approval-based multiwinner rules. Artificial Intelligence 288, p. 103366. Cited by: §1. [16] J. Maly, O. Nardi, and Z. Terzopoulou (2025) Sociotropic behavior in voting. Note: Unpublished manuscript, presented at the International Workshop on Computational Social Choice. (Accessed: 2026-09-26)https://ac.tuwien.ac.at/comsoc2025/comsoc2025-papers/13.pdf Cited by: §1. [17] L. Sánchez-Fernández, N. Fernández-García, J. A. Fisteus, and M. Brill (2024) The maximin support method: An extension of the D’Hondt method to approval-based multiwinner elections. Mathematical Programming 203 (1–2), p. 107–134. Cited by: §1. [18] P. Skowron, P. Faliszewski, and J. Lang (2016) Finding a collective set of items: from proportional multirepresentation to group recommendation. Artificial Intelligence 241, p. 191–216. External Links: Document Cited by: §1. [19] P. Skowron, M. Lackner, M. Brill, D. Peters, and E. Elkind (2017) Proportional rankings. In Proceedings of the International Joint Conference on Artificial Intelligence, Cited by: §1.1, §1, §3. [20] P. Skowron (2021) Proportionality degree of multiwinner rules. In Proceedings of the ACM Conference on Economics and Computation, Cited by: §1.1, §2. [21] T. N. Thiele (1895) Om flerfoldsvalg. In Oversigt over Det Kongelige Danske Videnskabernes Selskabs forhandlinger, Cited by: §1.