Proportionality criteria for approval methods
-
There was some off topic discussion in this thread but I want to expand on it.
This paper discusses a lot of the approval proportionality criteria that have come up over the years. And there are a lot of them. For example, there's Justified Representation (JR), Fully Justified Representation (FJR), Extended Justified Representation (EJR), Proportional Justified Representation (PJR), Laminar Proportionality, Priceability, Stable Priceability, Perfect Representation (PR), Core Stability. And probably some I've missed.
That's a lot of proportionality criteria. But the question is whether we need that many and whether they're all useful. If I want to know if a particular approval method is "proportional", I don't want to have to check it against 10 different criteria and then weigh them all up.
Well actually, I don't really think any of them really capture the essence of proportionality very well. On page 56 in that paper, there's a chart showing which criteria imply which others. And as you can see, almost all of them imply lower quota. According to lower quota, under party voting, no party can receive less than the proportion of seats they are due, rounded down to the nearest integer. However, as can be seen here, Sainte-Laguë/Webster fail lower quota, and are seen by many as the most accurately proportional methods. I don't think proportionality criteria that imply lower quota are fit for purpose.
Of the remaining criteria, I think Justified Representation is too weak to be worth anything. Perfect Representation, however, is too strong, but I think it makes a good base for a criterion. According to the wiki:
if there is a possible election result where candidates could each be assigned an equal number of voters where each voter has approved their assigned candidate and no voter is left without a candidate, then for a method to pass the perfect representation criterion, such a result must be the actual result.
I would say the main reason it is too strong is that it is incompatible with strong monotonicity. Consider the following ballots:
x voters: A, B, C
x voters: A, B, D
1 voter: C
1 voter: DWith 2 to elect, a method passing Perfect Representation must elect CD regardless of the value of x. There could be almost unanimous support for both A and B, but CD (with half the votes each) would still be elected.
In my paper on the COWPEA method, I define Perfect Representation In the Limit (PRIL):
As the number of elected candidates increases, then for v voters, in the limit each voter should be able to be uniquely assigned to ¹⁄ᵥ of the representation, approved by them, as long as it is possible from the ballot profile."
As I explained in the paper:
The common thread among proportionality criteria is the notion that a faction that comprises a particular proportion of the electorate should be able to dictate the make-up of that same proportion of the elected body. But this can be subject to rounding and there can be disagreement as to what is reasonable when some sort of rounding is necessary. However, taken to its logical conclusions, each voter individually can be seen as a faction of ¹⁄ᵥ of the electorate for v voters.
I also say that any deterministic method should obey Perfect Representation when Candidates Equals Voters (PR-CEV):
For a deterministic approval method where a fixed number of candidates are elected, a stronger proportionality criterion is Perfect Representation when Candidates Equals Voters (PR-CEV): if the number of elected candidates is equal to the number of voters (v), then it must be possible for each voter to be assigned to a unique candidate that they approved, as long as it is possible from the ballot profile. This is because no compromise due to rounding is necessary at that point.
One other thing I explained about PRIL, in case it is considered too weak for any reason:
One potential downside is that it does not define anything about the route to Perfect Representation, other than that it must be reached in the limit as the number of candidates increases. However, in that respect it has similarities with Independence of Clones, which is a well-established criterion. Candidates are only considered clones if they are approved on exactly the same ballots (or ranked consecutively for ranked-ballot methods). We would also want a method passing Independence of Clones to behave in a sensible manner with near clones, but it is generally trusted that unless a method has been heavily contrived then it would do this. Similarly, one would expect the route to Perfect Representation in a method passing PRIL to be a smooth and sensible one unless a method is heavily contrived, and none of the methods considered in this paper are contrived in such a manner.
So this is why I consider PRIL to be the standard proportionality criterion for approval methods. Any deterministic method should also pass PR-CEV.
-
I've been on the EndFPTP Reddit posting on this subject and I got ChatGPT to formalise the PRIL criterion. I'll copy my post from there wholesale:
On the formalisation of PRIL, I put to ChatGPT my idea of using the var-Phragmén metric and the concept of loads and told it to put the criterion in formal notation. PRIL is method agnostic though and could be used in conjunction with other methods that aim for Perfect Representation like leximax-Phragmén or Monroe. Anyway, here is what ChatGPT came up with. I make no guarantees an error hasn't slipped in:
Formal Definition of PRIL Using var-Phragmén:
Consider an election with: A set of voters N = {1, 2, . . . , n}.
A set of candidates C = {c1, c2, . . . , cm}.
Each voter i ∈ N has an approval ballot Ai ⊆ C.
A target number of winners k.
In the context of the var-Phragmén method:
Each voter i is assigned a "load" ℓi representing their share in the election of the chosen committee.The PRIL criterion can be formalized as follows:
For any arbitrarily small positive number ϵ>0, there exists a number of winners k such that for all k′ ≥ k, the normalized variance of the voter loads satisfies:
Var (ℓ) / k′ < ϵThis condition ensures that as the number of elected candidates k′ increases, the distribution of voter loads becomes increasingly uniform, approaching perfect representation in the limit. In essence, PRIL requires that for sufficiently large committees, the method should allocate representation so evenly among voters that the per-candidate variance of their loads becomes arbitrarily small, reflecting an ideal proportional representation.
-
@toby-pereira I didn’t get to check this in detail but I find it interesting. It also makes sense, although I wonder if it should be stated a bit more generally, saying maybe that there is some fixed positive constant C such that for all epsilon>0, there is some k such that for all k’>=k, C*Var(l)/k’<epsilon.
Is there a reason for choosing the normalized variance Var(l)/k’ rather than the normalized standard deviation sqrt(Var(l))/k’? Or even expressing in terms of sqrt(Var(l))/E(l)?
-
@cfrank said in Proportionality criteria for approval methods:
@toby-pereira I didn’t get to check this in detail but I find it interesting. It also makes sense, although I wonder if it should be stated a bit more generally, saying maybe that there is some fixed positive constant C such that for all epsilon>0, there is some k such that for all k’>=k, C*Var(l)/k’<epsilon.
Is there a reason for choosing the normalized variance Var(l)/k’ rather than the normalized standard deviation sqrt(Var(l))/k’? Or even expressing in terms of sqrt(Var(l))/E(l)?
I could have made it specify the proportionality level more specifically, but left it more open so that it doesn't throw out non-deterministic methods such as COWPEA Lottery.
But in terms of maximum allowable load variance for a deterministic method, I think we would look at the worst case scenario of every voter approving a completely different set of candidates. We would then sequentially award a candidate to each voter until they all have one, and then start the process again. As I understand it, the variance would be highest when half the voters have an "extra" candidate and half don't.
As every candidate adds a "load" of 1, at this point every voter would have a load that is 0.5 away from the mean. So the variance would be 0.25. So instead of talking about tending towards zero, we could just say that to pass PRIL it must satisfy: var (ℓ) ≤ 0.25 (or 0.5 if we use the standard deviation instead).
I could have used other measures such as the standard deviation. I mainly used variance because of the existence of var-Phragmén. I could also have put it in terms of the leximax-Phragmén metric or Monroe.
Of course, as discussed, this doesn't define anything about the route to Perfect Representation. If there are 50 voters of party A and 50 of party B, it would allow the first 50 candidates to all go to the same party. But as also discussed, unless a method has been heavily contrived, this won't happen, and it's similar to Independence of Clones in this way.
-
I think talking about Phragmén loads is over-complicating the matter. We could just say that for a method to pass (in the deterministic case), then as long as it's possible from the ballot profiles (each voter has approved enough candidates), then under any result produced by the method, it must be possible to uniquely assign each elected candidate to a voter who approved them in a way that means no voter has ≥2 candidates more than another.
For non-deterministic methods we could still talk in terms of whole candidates rather than loads and just say that the variance / total elected candidates must approach zero as the number of elected candidates increases.
-
@toby-pereira I really like the concept of the Phragmén method. You’re also right that the proportionality constant doesn’t change things, I was crossing wires about the ratio.
Lots of interesting things to think about. Do you know of any graph-based PR algorithms?
-
@cfrank I also like the concept of the Phragmén method to a point, but because it only cares about proportionality, it's not as monotonic as other methods such as Thiele's PAV method. I mean, it passes in that an extra approval can't count against a candidate, but sometimes it makes no difference, so I call it weakly monotonic.
By graph-based do you mean like Schulze for single winner? There is also a Schulze STV method, which reduces to Schulze in the single-winner case.