Difference between revisions of "Proportionality for Solid Coalitions"
Psephomancy (talk  contribs) (formatting) 

Line 7:  Line 7:  
== Examples == 
== Examples == 

5winner example, Hare quota 50 (example done using scored ballots): 
5winner example, Hare quota 50 (example done using scored ballots): 

+  
{ class="wikitable" 
{ class="wikitable" 

!Number 
!Number 

Line 41:  Line 42:  
A1:0 A2:0 A3:0 A4:0 A5:0 B1:0 C1:0 D1:0 E1:0 F1:10 
A1:0 A2:0 A3:0 A4:0 A5:0 B1:0 C1:0 D1:0 E1:0 F1:10 

} 
} 

+  
Looking at the top 5 lines, 50 voters, a Hare quota, mutually most prefer the set of candidates (A15) over all other candidates, so HarePSC requires at least one of (A15) must win. (Note that Sequential Monroe voting fails HarePSC in this example. However, one could forcibly make SMV do so by declaring that the candidate with the highest Monroe score within the set (A15) must win the first seat, for example.) <ref>https://forum.electionscience.org/t/anexampleofmaximaldivergencebetweensmvandharepsc/586</ref> 
Looking at the top 5 lines, 50 voters, a Hare quota, mutually most prefer the set of candidates (A15) over all other candidates, so HarePSC requires at least one of (A15) must win. (Note that Sequential Monroe voting fails HarePSC in this example. However, one could forcibly make SMV do so by declaring that the candidate with the highest Monroe score within the set (A15) must win the first seat, for example.) <ref>https://forum.electionscience.org/t/anexampleofmaximaldivergencebetweensmvandharepsc/586</ref> 

Generally, DroopPSC makes it more likely that a majority will win at least half the seats than only HarePSC. The reason for this is that majority solid coalitions always constitute enough Drool quotas to always win at least half the seats, while with Hare quotas they can only guarantee they will win just under half the seats and have over half a Hare quota to win the additional seat required to get at least half the seats. 5winner example using STV with Hare quotas: 
Generally, DroopPSC makes it more likely that a majority will win at least half the seats than only HarePSC. The reason for this is that majority solid coalitions always constitute enough Drool quotas to always win at least half the seats, while with Hare quotas they can only guarantee they will win just under half the seats and have over half a Hare quota to win the additional seat required to get at least half the seats. 5winner example using STV with Hare quotas: 

−  <br /> 

{ class="wikitable" 
{ class="wikitable" 

!Number 
!Number 

Line 65:  Line 66:  
B3>B2>B1>A1>A3>A2 
B3>B2>B1>A1>A3>A2 

} 
} 

+  
Note that 51 voters, a majority, prefer (A13) over all other candidates, and thus electing all 3 of them would mean 3 out of 5 seats, a majority, would belong to the majority. Also, the Droop quota here is 17, and thus by DroopPSC the majority has 51/17=3 PR guarantees, which would give them a majority of seats. However, by HarePSC, they only have 51/20 rounded down = 2 PR guarantees, and thus by HareSTV: 
Note that 51 voters, a majority, prefer (A13) over all other candidates, and thus electing all 3 of them would mean 3 out of 5 seats, a majority, would belong to the majority. Also, the Droop quota here is 17, and thus by DroopPSC the majority has 51/17=3 PR guarantees, which would give them a majority of seats. However, by HarePSC, they only have 51/20 rounded down = 2 PR guarantees, and thus by HareSTV: 

+  <blockquote>So, the Hare quota here is 20. A1 and A2 are immediately elected, but posttransfer A3 only has 11 votes, and is thus eliminated first. B1, B2, B3 take the remaining 3 seats.<ref>https://www.reddit.com/r/EndFPTP/comments/ermb1s/comment/ff7a7f8</ref></blockquote> 

−  
−  
−  <br /><blockquote>So, the Hare quota here is 20. A1 and A2 are immediately elected, but posttransfer A3 only has 11 votes, and is thus eliminated first. B1, B2, B3 take the remaining 3 seats.<ref>https://www.reddit.com/r/EndFPTP/comments/ermb1s/comment/ff7a7f8</ref></blockquote> 

−  
−  
There can be quota overlaps when assigning PSC claims; suppose a group constituting 80% of a quota of voters vote A>B>C>D, another group of 80% of a quota vote B>A>C>D, and another group of 50% of a quota vote C>A=B=D. Then, 2 candidates must be elected from the set (A, B, C, D), since in total 2.1 quotas mutually most prefer that set, but a further constraint is that 1 candidate must win from within (A, B), since 1.6 quotas mutually most prefer them. It would not satisfy PSC if the final winner set had neither A or B in it in other words, even if it had C and D. 
There can be quota overlaps when assigning PSC claims; suppose a group constituting 80% of a quota of voters vote A>B>C>D, another group of 80% of a quota vote B>A>C>D, and another group of 50% of a quota vote C>A=B=D. Then, 2 candidates must be elected from the set (A, B, C, D), since in total 2.1 quotas mutually most prefer that set, but a further constraint is that 1 candidate must win from within (A, B), since 1.6 quotas mutually most prefer them. It would not satisfy PSC if the final winner set had neither A or B in it in other words, even if it had C and D. 

== Generalised solid coalitions == 
== Generalised solid coalitions == 

+  The Expanding Approvals Rule passes a stricter PR axiom than PSC: 

−  The Expanding Approvals Rule passes a stricter PR axiom than PSC:<blockquote>Definition 5 (Generalised solid coalition) A set of voters N′ is a generalised solid coalition for a set of candidates C′ if every voter in N′ weakly prefers every candidate in C′ at least as high as every candidate in C\C′. That is, for all i ∈ N′ and for any c′ ∈ C′ 

+  <blockquote>'''Definition 5 (Generalised solid coalition)''' A set of voters ''N''′ is a ''generalised solid coalition'' for a set of candidates ''C''′ if every voter in ''N''′ weakly prefers every candidate in ''C''′ at least as high as every candidate in C\C′. That is, for all i ∈ N′ and for any c′ ∈ C′ 

−  ∀c ∈ C\C′ c′ i c. We note that under strict preferences, a generalised solid coalition is equivalent 

+  : ∀c ∈ C\C′ c′ i c. 

−  to solid coalition. Let c(i, j) denotes voter i’s jth most preferred candidate. In case the voter’s preference has indifferences, we use lexicographic tiebreaking to identify the candidate in the jth position. 

+  We note that under strict preferences, a generalised solid coalition is equivalent to solid coalition. Let c(i, j) denotes voter i’s jth most preferred candidate. In case the voter’s preference has indifferences, we use lexicographic tiebreaking to identify the candidate in the jth position. 

−  Definition 6 (Generalised qPSC) Let q ∈ (n/(k + 1), n/k]. A committee W satisfies generalised qPSC if for all generalised solid coalitions N′ supporting candidate subset C′ with size N′ ≥ ℓq, there exists a set C′′ ⊆ W with size at least min{ℓ, C′} such that for all c′′ ∈ C′′ 

+  '''Definition 6 (Generalised qPSC)''' Let q ∈ (n/(k + 1), n/k]. A committee W satisfies generalised qPSC if for all generalised solid coalitions N′ supporting candidate subset C′ with size N′ ≥ ℓq, there exists a set C′′ ⊆ W with size at least min{ℓ, C′} such that for all c′′ ∈ C′′ 

−  ∃i ∈ N′ : c′′ i c(i,C′ ). The idea behind generalised qPSC is identical to that of qPSC and in fact generalised qPSC is equivalent to qPSC under linear preferences. Note that in the definition above, a voter i in the solid coalition of voters N′ does not demand membership of candidates from the solidly supported subset C′ but of any candidate that is at least as preferred as a least preferred candidate in C′. Generalised weak qPSC is a natural weakening of generalised qPSC in which we require that C′ is of size at most ℓ. 

+  : ∃i ∈ N′ : c′′ i c(i,C′ ). 

−  Definition 7 (Generalised weak qPSC) Let q ∈ (n/(k + 1), n/k]. A committee W satisfies weak generalised qPSC if for every positive integer ℓ, and every generalised solid coalition N′ supporting a candidate subset C′ 

+  
+  The idea behind generalised qPSC is identical to that of qPSC and in fact generalised qPSC is equivalent to qPSC under linear preferences. Note that in the definition above, a voter i in the solid coalition of voters N′ does not demand membership of candidates from the solidly supported subset C′ but of any candidate that is at least as preferred as a least preferred candidate in C′. Generalised weak qPSC is a natural weakening of generalised qPSC in which we require that C′ is of size at most ℓ. 

+  
+  '''Definition 7 (Generalised weak qPSC)''' Let q ∈ (n/(k + 1), n/k]. A committee W satisfies weak generalised qPSC if for every positive integer ℓ, and every generalised solid coalition N′ supporting a candidate subset C′ 

: C′ ≤ ℓ with size N′ ≥ ℓq, there 
: C′ ≤ ℓ with size N′ ≥ ℓq, there 

−  exists a set C′′ ⊆ W with size at least min{ℓ, C′} such that for all c′′ ∈ C′′ 
+  exists a set C′′ ⊆ W with size at least min{ℓ, C′} such that for all c′′ ∈ C′′ 
−  : c′′ i c(i,C′ ).<ref>https://arxiv.org/abs/1708.07580 p. 8</ref></blockquote 
+  : ∃i ∈ N′ : c′′ i c(i,C′ ).<ref>https://arxiv.org/abs/1708.07580 p. 8</ref></blockquote> 
== Notes == 
== Notes == 

DroopPSC implies HarePSC, since a Hare quota is simply a large Droop quota, but the same doesn't hold the other way around. HarePSC is equivalent to the unanimity criterion and DroopPSC to the mutual majority criterion in the singlewinner case. Note that this means cardinal PR methods can only pass HarePSC and not DroopPSC in order to reduce to cardinal methods that fail the mutual majority criterion in the singlewinner case, which is most of them. 
DroopPSC implies HarePSC, since a Hare quota is simply a large Droop quota, but the same doesn't hold the other way around. HarePSC is equivalent to the unanimity criterion and DroopPSC to the mutual majority criterion in the singlewinner case. Note that this means cardinal PR methods can only pass HarePSC and not DroopPSC in order to reduce to cardinal methods that fail the mutual majority criterion in the singlewinner case, which is most of them. 

−  Note that PSC doesn't hold if some voters in a coalition back outofcoalition candidates i.e. 1winner example with Droop quota of 51: 
+  Note that PSC doesn't hold if some voters in a coalition back outofcoalition candidates i.e. 1winner example with Droop quota of 51: 
+  
+  <blockquote>26 A>B 

25 B 
25 B 

+  49 C</blockquote> 

−  49 C</blockquote>STV would elect C here. Yet if A hadn't run, then B would've been 51 voter's 1st choice, so a Droop solid coalition would've been backing them, and since STV passes DroopPSC, B would've guaranteeably won. 

+  
+  STV would elect C here. Yet if A hadn't run, then B would've been 51 voter's 1st choice, so a Droop solid coalition would've been backing them, and since STV passes DroopPSC, B would've guaranteeably won. 

One could also consider various extensions of the solid coalition idea, in part to address examples like the above one; 5winner example: 
One could also consider various extensions of the solid coalition idea, in part to address examples like the above one; 5winner example: 

−  +  <blockquote>9 A>F>G>H>I>J 

9 B>F>G>H>I>J 
9 B>F>G>H>I>J 

Line 117:  Line 123:  
8 K 
8 K 

+  7 L</blockquote> 

−  7 L</blockquote>Arguably there is some kind of coalition of 45 voters backing candidates A through J here, and since the largest opposing coalition is 8 voters, D'Hondt would say that the 45voter coalition ought to win all 5 seats. At that point, one could eliminate all candidates outside the 45voter coalition (K and L) at which point A through E all are a Hare quota's 1st choice and must all win. This sort of thinking is generally what Condorcet PR methods such as Schulze STV do. 

+  Arguably there is some kind of coalition of 45 voters backing candidates A through J here, and since the largest opposing coalition is 8 voters, D'Hondt would say that the 45voter coalition ought to win all 5 seats. At that point, one could eliminate all candidates outside the 45voter coalition (K and L) at which point A through E all are a Hare quota's 1st choice and must all win. This sort of thinking is generally what Condorcet PR methods such as Schulze STV do. 

−  <br /> 
Revision as of 16:35, 18 February 2020
Proportionality for Solid Coalitions (PSC) is a criterion for proportional methods requiring that sufficientlysized groups of voters (solid coalitions) always elect a proportional number of candidates from their set of mutually mostpreferred candidates. In general, any time any group of voters prefers any set of candidates over all others, a certain minimum number of candidates from that set must win to pass the criterion, and the same must hold if the preferred set of candidates for a group can be shrunk or enlargened. It is the main conceptualization of Proportional Representation generally used throughout the world (Party List and STV pass versions of it.) The two main types of PSC are kPSC (aka. HarePSC, a condition requiring a solid coalition comprising k Hare quotas to be always elect at least k mostpreferred candidates) and k+1PSC (aka. DroopPSC, which is the same as HarePSC but holding for Droop quotas instead).
Any voting method that collects enough information to distinguish solid coalitions (generally scored or ranked methods, since preferences can be inferred from their ballots) can be forced to be PSCcompliant by first electing the proportionally correct number of candidates from each solid coalition before doing anything else.
Cardinal PR methods generally don't pass PSC, though they pass weaker, related versions relating to Hare quotas of voters being able to force the proportionally correct number of their mostpreferred candidates to win through strategic voting. In general, any method that passes such weaker versions of PSC is considered to be at least semiproportional.
Examples
5winner example, Hare quota 50 (example done using scored ballots):
Number  Ballots 

10  A1:10 A2:7 A3:7 A4:7 A5:7 B1:1 C1:0 D1:0 E1:0 F1:0 
10  A1:7 A2:10 A3:7 A4:7 A5:7 B1:0 C1:1 D1:0 E1:0 F1:0 
10  A1:7 A2:7 A3:10 A4:7 A5:7 B1:0 C1:0 D1:1 E1:0 F1:0 
10  A1:7 A2:7 A3:7 A4:10 A5:7 B1:0 C1:0 D1:0 E1:1 F1:0 
10  A1:7 A2:7 A3:7 A4:7 A5:10 B1:0 C1:0 D1:0 E1:0 F1:0 
40  A1:2 A2:0 A3:0 A4:0 A5:1 B1:10 C1:0 D1:0 E1:0 F1:0 
40  A1:0 A2:2 A3:0 A4:0 A5:1 B1:0 C1:10 D1:0 E1:0 F1:0 
40  A1:0 A2:0 A3:2 A4:0 A5:1 B1:0 C1:0 D1:10 E1:0 F1:0 
40  A1:0 A2:0 A3:0 A4:2 A5:1 B1:0 C1:0 D1:0 E1:10 F1:0 
40  A1:0 A2:0 A3:0 A4:0 A5:0 B1:0 C1:0 D1:0 E1:0 F1:10 
Looking at the top 5 lines, 50 voters, a Hare quota, mutually most prefer the set of candidates (A15) over all other candidates, so HarePSC requires at least one of (A15) must win. (Note that Sequential Monroe voting fails HarePSC in this example. However, one could forcibly make SMV do so by declaring that the candidate with the highest Monroe score within the set (A15) must win the first seat, for example.) ^{[1]}
Generally, DroopPSC makes it more likely that a majority will win at least half the seats than only HarePSC. The reason for this is that majority solid coalitions always constitute enough Drool quotas to always win at least half the seats, while with Hare quotas they can only guarantee they will win just under half the seats and have over half a Hare quota to win the additional seat required to get at least half the seats. 5winner example using STV with Hare quotas:
Number  Ballots 

26  A2>A1>A3>B1>B2>B3 
25  A1>A3>A2>B1>B2>B3 
17  B1>B2>B3>A1>A3>A2 
16  B2>B1>B3>A1>A3>A2 
16  B3>B2>B1>A1>A3>A2 
Note that 51 voters, a majority, prefer (A13) over all other candidates, and thus electing all 3 of them would mean 3 out of 5 seats, a majority, would belong to the majority. Also, the Droop quota here is 17, and thus by DroopPSC the majority has 51/17=3 PR guarantees, which would give them a majority of seats. However, by HarePSC, they only have 51/20 rounded down = 2 PR guarantees, and thus by HareSTV:
So, the Hare quota here is 20. A1 and A2 are immediately elected, but posttransfer A3 only has 11 votes, and is thus eliminated first. B1, B2, B3 take the remaining 3 seats.^{[2]}
There can be quota overlaps when assigning PSC claims; suppose a group constituting 80% of a quota of voters vote A>B>C>D, another group of 80% of a quota vote B>A>C>D, and another group of 50% of a quota vote C>A=B=D. Then, 2 candidates must be elected from the set (A, B, C, D), since in total 2.1 quotas mutually most prefer that set, but a further constraint is that 1 candidate must win from within (A, B), since 1.6 quotas mutually most prefer them. It would not satisfy PSC if the final winner set had neither A or B in it in other words, even if it had C and D.
Generalised solid coalitions
The Expanding Approvals Rule passes a stricter PR axiom than PSC:
Definition 5 (Generalised solid coalition) A set of voters N′ is a generalised solid coalition for a set of candidates C′ if every voter in N′ weakly prefers every candidate in C′ at least as high as every candidate in C\C′. That is, for all i ∈ N′ and for any c′ ∈ C′
 ∀c ∈ C\C′ c′ i c.
We note that under strict preferences, a generalised solid coalition is equivalent to solid coalition. Let c(i, j) denotes voter i’s jth most preferred candidate. In case the voter’s preference has indifferences, we use lexicographic tiebreaking to identify the candidate in the jth position.
Definition 6 (Generalised qPSC) Let q ∈ (n/(k + 1), n/k]. A committee W satisfies generalised qPSC if for all generalised solid coalitions N′ supporting candidate subset C′ with size N′ ≥ ℓq, there exists a set C′′ ⊆ W with size at least min{ℓ, C′} such that for all c′′ ∈ C′′
 ∃i ∈ N′ : c′′ i c(i,C′ ).
The idea behind generalised qPSC is identical to that of qPSC and in fact generalised qPSC is equivalent to qPSC under linear preferences. Note that in the definition above, a voter i in the solid coalition of voters N′ does not demand membership of candidates from the solidly supported subset C′ but of any candidate that is at least as preferred as a least preferred candidate in C′. Generalised weak qPSC is a natural weakening of generalised qPSC in which we require that C′ is of size at most ℓ.
Definition 7 (Generalised weak qPSC) Let q ∈ (n/(k + 1), n/k]. A committee W satisfies weak generalised qPSC if for every positive integer ℓ, and every generalised solid coalition N′ supporting a candidate subset C′
 C′ ≤ ℓ with size N′ ≥ ℓq, there
exists a set C′′ ⊆ W with size at least min{ℓ, C′} such that for all c′′ ∈ C′′
 ∃i ∈ N′ : c′′ i c(i,C′ ).^{[3]}
Notes
DroopPSC implies HarePSC, since a Hare quota is simply a large Droop quota, but the same doesn't hold the other way around. HarePSC is equivalent to the unanimity criterion and DroopPSC to the mutual majority criterion in the singlewinner case. Note that this means cardinal PR methods can only pass HarePSC and not DroopPSC in order to reduce to cardinal methods that fail the mutual majority criterion in the singlewinner case, which is most of them.
Note that PSC doesn't hold if some voters in a coalition back outofcoalition candidates i.e. 1winner example with Droop quota of 51:
26 A>B25 B
49 C
STV would elect C here. Yet if A hadn't run, then B would've been 51 voter's 1st choice, so a Droop solid coalition would've been backing them, and since STV passes DroopPSC, B would've guaranteeably won.
One could also consider various extensions of the solid coalition idea, in part to address examples like the above one; 5winner example:
9 A>F>G>H>I>J9 B>F>G>H>I>J
9 C>F>G>H>I>J
9 D>F>G>H>I>J
9 E>F>G>H>I>J
8 K
7 L
Arguably there is some kind of coalition of 45 voters backing candidates A through J here, and since the largest opposing coalition is 8 voters, D'Hondt would say that the 45voter coalition ought to win all 5 seats. At that point, one could eliminate all candidates outside the 45voter coalition (K and L) at which point A through E all are a Hare quota's 1st choice and must all win. This sort of thinking is generally what Condorcet PR methods such as Schulze STV do.