General stuff about approval/cardinal PR
-
Onto Phragmén then. There are essentially two Phragmén methods - max-Phragmén and var-Phragmén. Max-Phragmén reduces to D'Hondt party list for party voting, and var-Phragmén reduces to Sainte-Laguë, so these correspond to the two different PAV versions discussed in the previous post. But despite this, PAV and Phragmén have very different PR philosophies. PAV is all about maximising approvals, although in a diminishing returns way, whereas Phragmén is all about balancing representation across voters with no particular concern for actual amount of support. Phragmén's monotonic properties are not as strong because of this (although it does technically pass the main criterion).
In Phragmén, each elected candidate has a "load" (sometimes called cost but whatever) of 1 that is spread out among the voters of that candidate. The loads does not have to be spread equally but is spread in the way that allows for the best set score.
For max-Phragmén, only the single voter with the highest load is considered. The set with the lowest single voter load is the winning set. For var-Phragmén, the variance of all the loads is calculated. The set with the lowest variance wins. I'll give a couple of examples.
2 to elect
1 voter: AB
1 voter: ACNote that A is unanimously approved. If the load from a candidate had to be spread equally across its voters, this would cause a monotonicity failure. Take set AB. The AB voter would get a load of 0.5 from A and 1 from B, totalling 1.5. The AC voter would just get a load of 0.5 from A. So the two loads on the voters would be 1.5 and 0.5.
Now look at BC. The AB voter would get a load of 1 from B, and the AC voter would get a load of 1 from C. So the loads on both voters would be 1. This minimises the variance and the max load on a single voter. So BC would be elected. However, A is unanimously approved and would have fared better with just one approval, showing a monotonicity failure. One could argue that BC is more proportional in some sense, but I think most would agree that this would be taking it too far.
This is why loads are allowed to be spread unevenly. Under AB then, the entire A load can go to the AC voter with the B load going to the AB voter. Now both loads would be 1, minimising the max load and the variance.
But this still isn't a great victory for monotonicity. AB and AC only tie with BC. Similarly with 2 to elect:
1 voter ABC
1 voter: ABDThe unanimously approved AB is considered no better than CD.
Of course there could be some sort of tie-breaking mechanism, which would likely favour more approvals. But these are knife-edge results. Take the following example with 2 to elect:
99 voters: AB
99 voters: AC
1 voter: B
1 voter: CDespite 99% of voters approving A, and just 50% approving B and C, BC would be elected under Phragmén. I would consider this to be an undesirable result.
When every voter has an equal load, this is known as "perfect representation". Methods that elect a candidate set that gives perfect representation whenever it is possible pass the perfect representation criterion. The Phragmén methods but not PAV pass this.
In this respect perfect representation can be seen as too strong a criterion to insist on a method passing. On the other hand, closeness to perfect representation seems a good measure of proportionality. So it's a question of getting the balance right between proportionality and support. I will be discussing different PR criteria in the next post, and which ones make most sense to use.
I'll also just point out here that two other similarish methods people talk about are Monroe (also known as Fully Proportional Representation), and Chamberlin-Courant. Under Monroe, each elected candidate is assigned an equal number of voters. The winning set is the one that allows the most voters to be assigned to a candidate that they approved. As I understand it, this behaves fairly similarly to Phragmén, except that for party voting it reduces to the Hamilton apportionment method. Essentially this is like Sainte-Laguë but with IIB failures.
Chamberlin-Courant elects the set that allows the most voters to have an approved candidate in the winning set. It makes no difference how many voters have approved each candidate. If there are 10 voters and 2 to elect, Chamberlin-Courant would not distinguish between a set where each candidate is approved by 5 distinct voters, and a set where the ratio is 9:1. So it too is similar to Phragmén and Monroe, but can give more skewed (less proportional) results.
Both Monroe and Chamberlin-Courant are discussed here. It is said that Chamberlin-Courant could give weighted voting within the committee to counteract the disproportionality, but at this point it is getting away from the usual requirements of a proportional approval method.
So this is why PAV and Phragmén are the big two out of these methods.
-
Before I get onto PR criteria, I just want to mention quota-removal methods. As methods they are simple and intuitive to understand and can be of practical use, but I think they are less interesting from a mathematical and academic point of view. They are discussed in more detail in this thread.
In this context I will also mention the Method of Equal Shares (MES). I've seen people rave about how great this is. But as it's defined it's a method of participatory budgeting where different projects that people vote for can have different costs. There is also a set budget, rather than a set number of things to elect so in its default form, it isn't a standard proportional approval method.
Presumably to convert it, the cost for each candidate is set at the same price, which would be a quota (Droop, Hare etc.). This could still lead to not enough candidates being elected if not enough reach the quota, so something else would need to be added to the method.
In any case, it is just another quota removal method, so inherits all of their problems.
-
OK, so the criteria. They're often called axioms in the literature, but I'm not sure it seems the right word.
The paper Multi-Winner Voting with Approval Preferences by Martin Lackner and Piotr Skowron is probably the best single resource on this, but there are lots of papers on the subject obviously. On page 56 it has a chart of some of the criteria and which imply which others. You'll notice that most of them imply lower quota satisfaction.
Lower quota says that a party must get at least its correct proportional number of seats rounded down. It sounds reasonable on the surface, but it disqualifies Sainte-Laguë party list (equivalently Webster apportionment), and any proportional approval method that reduces to it under party voting. The authors acknowledge the problem:
Most axiomatic notions for proportionality are only applicable to ABC rules that
extend apportionment methods satisfying lower quota (see Figure 4.1). This excludes, e.g., ABC rules that extend the Sainte-Lagu¨e method. As the Sainte-Lagu¨e
method is in certain aspects superior to the D’Hondt method (Balinski and Young
[2] discuss this in detail), it would be desirable to have notions of proportionality
that are agnostic to the underlying apportionment method.As far as I'm concerned, the solution is not to demand specific proportionality requirements at exact points because different methods round in different ways, while still being proportional overall. Any specific requirements would likely be arbitrary and potentially disqualify reasonable methods (as seen) (edit - and also they can let in disproportional methods as PAV passes a lot of criteria). It is better instead to demand that a method becomes proportional in the limit as the number of candidates increases. And while this says nothing about the route to PR in the long haul, unless a method has been heavily contrived to do so in a "bad" way, it's likely to get there in a smooth, continuous and sensible way. (Similarly independence of clones only makes demands for candidates approved on exactly the same ballots, or ranked consecutively on all ballots, but it is generally accepted that a passing method will behave reasonably with near clones and it is a recognised criterion.)
And this takes us back to perfect representation. Closeness to it seems a good measure of PR, but as said above demanding it whenever it's possible seems too strong a requirement.
2 to elect
99 voters: AB
99 voters: AC
1 voter: B
1 voter: CWe would not want to be forced into electing BC. This is why I came up with the Perfect Representation In the Limit (PRIL) criterion. I also discuss all this in this thread. I got ChatGPT to come up with a formal definition that I put in there, but I have a better one now, though it doesn't copy and paste easily.
Also a deterministic method should pass perfect representation when the number of voters is the same as the number of elected candidates, as no rounding will be required. But PRIL is more general and works for non-deterministic methods, so it's my primary PR criterion.
So that's proportionality criteria covered. Next I want to talk about the "Holy Grail" criteria, which is something that has evolved out of internet discussions over the years. My version of the criteria are:
Proportionality (so PRIL)
Monotonicity (ideally a stronger version that won't elect BC in the above example)
Independence of Irrelevent Ballots (IIB)
Independence of Universally Approved Candidates (IUAC)No known deterministic method passes all of these, so we have to look beyond the likes of PAV and Phragmén. So in the next post I will talk about non-deterministic methods and also about optimal methods that can elect any number of candidates with any weight. They may not be practical election methods, but they are of theoretical interest and are closely related to non-deterministic methods.
In an optimal method the "Holy Grail" criteria are the same except without IUAC. In a good optimal method, universally approved candidates should take all the weight, so there's nothing left to be independent of them. Also optimal methods are already "in the limit" so PRIL and perfect representation are the same thing.
-
Right so moving on to finding the "Holy Grail". The criteria again:
Proportionality (so PRIL)
Monotonicity (ideally a stronger version that won't elect BC in the above example)
Independence of Irrelevant Ballots (IIB)
Independence of Universally Approved Candidates (IUAC)On monotonicity, I would also add strong candidate Pareto efficiency as a strengthener.
Candidate A Pareto dominates candidate B if A is approved on all the ballots that B is and at least one other ballot. Passing strong candidate Pareto efficiency means that an election method must not elect a Pareto dominated candidate unless the candidate that dominates it is also elected. For an optimal method, the Pareto dominated candidate must not be elected with any weight. (Weak efficiency would allow for such a dominated set to be tied at the top.)
This criterion is being used as a proxy for a stronger form of monotonicity where adding an approval for a candidate should actively count in a candidate’s favour rather than merely not count against.
It is actually possible to pass strong candidate Pareto efficiency and fail monotonicity (as will be seen), but having both should protect against the "pathological" examples.
While normal PAV fails PRIL, Optimal PAV passes. The failure in the example a few posts above is avoided because the U candidates Pareto dominate the A and B ones, so you essentially end up with just a U and a C faction. And while this is just a simple example, it can be shown that Optimal PAV passes PRIL in general.
Optimal PAV looks like taking the clean sweep of Holy Grail criteria - except that it actually fails monotonicity, unlike normal PAV!
Optimal PAV is equivalent to the Nash Product Rule as I found out the other day. This is where you maximise the product of the voters' utilities. (By utility, I mean the number of approved candidates they have elected.) Intuitively this makes sense because product of utilities is the same as adding the logs, and the harmonic function of x converges to ln x + 0.577, and the 0.577 proportionally disappears as you get higher. A more formal proof is here. An example of monotonicity failure is here.
Anyway, Optimal PAV can be turned into Optimal PAV Lottery. This is where candidates are elected sequentially with probability equal to their weight in the PAV optimal committee. The weights are recalculated each time a candidate is elected and removed from the pool.
Unlike normal PAV, Optimal PAV Lottery passes IUAC because any universally approved candidates are elected to the first positions with probability 1, and then the rest is the same from there. But like Optimal PAV it fails monotonicity so cannot be deemed a Holy Grail method.
I'll do COWPEA in the next post.
-
OK, so COWPEA:
The weight each candidate gets in parliament is the same as the probability that they would be elected in the following lottery:
Start with a list of all candidates. Pick a ballot at random and remove from the list all candidates not approved on this ballot. Pick another ballot at random, and continue with this process until one candidate is left. Elect this candidate. If the number of candidates ever goes from >1 to 0 in one go, ignore that ballot and continue. If any tie cannot be broken, then elect the tied candidates with equal probability.
I recently found in the literature that this idea does exist. In the paper Approval-Based Apportionment it's referred to as Random priority. This puts me in a slight dilemma about pushing ahead with making my COWPEA paper fit for publication and trying to get it published, but I think there's enough in it that hasn't been discussed. Plus my original formulation of it in 2016 pre-dates the general discussion of it in proportional approval method literature.
Anyway, this passes PRIL quite trivially as each voter is picked as the starting voter 1/v of the time for v voters.
It is also monotonic. For it to fail monotonicity, there would have to be a possible iteration of the lottery where A gets elected and where adding A to a ballot prevents this election. In such a case, this could only happen when this particular ballot is picked in the random process. For this ballot to get picked (without A on) and A to still get elected, none of the other remaining candidates could also be approved on that ballot, so it continues the process where A is eventually elected. Now imagine approving A on that ballot. In this scenario, it must result in the election of A. So a non-monotonic case is impossible.
It passes strong candidate Pareto efficiency. Any dominated candidate takes zero weight.
It passes IIB as picking a ballot that approves all or none of the candidates does nothing and another one is then picked.
So COWPEA passes the Holy Grail criteria for optimal methods!
COWPEA Lottery passes the same criteria and also passes IUAC as any universally approved candidates are elected to the first positions, as with Optimal PAV Lottery.
As far as I know COWPEA and COWPEA Lottery are the only known methods that pass the Holy Grail criteria.
Optimal PAV Lottery also requires complex calculations to be run. A COWPEA Lottery election can be run by just picking a few ballots at random. The overall weights do not need to be calculated. This could be useful for e.g. groups of friends picking an activity where proportionality over time can be achieved without anyone keeping count and also if not everyone is present each time.
Next I will make a couple of other comparisons between COWPEA and Optimal PAV, specifically relating to the consistency and multi-winner Pareto efficiency criteria. Optimal PAV passes these but COWPEA doesn't, but they are of debatable utility.
-
Strong multi-winner Pareto efficiency: A set of candidates S Pareto dominates set S′ if every voter has approved at least as many candidates in S as S′ and least one voter has approved more in S.
For a method to pass the criterion S′ must not be the elected set.
(For optimal methods it would refer to weight in the committee rather than number of candidates.)
COWPEA fails this.
250 voters: AC
250 voters: AD
250 voters: BC
250 voters: BD
1 voter: C
1 voter: DOptimal PAV would simply elect C and D with half the weight each. COWPEA would elect each with about 1/4, but C and D slightly more.
This example can be seen as a 2-dimensional voting space with A and B at opposite ends of one axis and C and D at opposite ends of the other. No voter has approved both A and B or both C and D. Viewed like this, electing only C and D seems restrictive and arguably does not make best use of the voting space, which may include policy areas not considered by all candidates. This potentially calls into question the utility of the multi-winner Pareto efficiency criterion. It's certainly not a "slam dunk".
In certain allocation scenarios, it would make more sense as a criterion where utility is purely determined by number of approved things, but it's less clear for voting.
Also in normal election cases with fixed candidates, the case against it is clearer.
2 to elect
150 voters: AC
100 voters: AD
140 voters: BC
110 voters: BD
1 voter: C
1 voter: DThe winning set must be AB or CD. If we elect any other pair, then too many voters would be without any representation. Candidates A and B are each approved by 250 voters, distinct from each other, and adding up to 500. Candidate C is approved by 291, and candidate D by 211, also distinct from each other, and adding up to 502. The strong multi-winner Pareto criterion would insist on the election of CD, since every voter would have one candidate that they approved in the committee. Under AB, there would be two unrepresented voters. However, CD is a disproportional result, as the D voters, numbering only 211 wield a disproportionally large amount of power. Without the two voters that only vote for one candidate, it seems clear that AB would be the better result, as it is more proportional with no disadvantages.
It purely comes down to whether the Pareto dominance caused by the single C-only and single D-only voter is enough to overturn the better-balanced result of AB. Unless level of proportional representation is of only negligible or tie-break value, AB must be the better result. Deterministic PAV would elect CD but other methods such as Phragmén would elect AB.
Consistency is where when two elections that give the same result are combined, the overall result must still be the same. Sticking with the fixed candidate case, we could swap the C and D voters above:
150 voters: AD
100 voters: AC
140 voters: BD
110 voters: BC
1 voter: D
1 voter: CIf it was reasonable to elect AB before, it still is now. But we can combine them:
250 voters: AC
250 voters: AD
250 voters: BC
250 voters: BD
2 voters: C
2 voters: DAnd clearly CD becomes the best result, meaning consistency isn't essential. Obviously COWPEA and Optimal PAV can elect candidates in different proportions so they are not directly affected by this.
However, take these election examples:
2 voters: AC
1 voter: A
3 voters: BC is Pareto dominated by A so COWPEA would elect AB with half the weight each.
3 voters: A
2 voters: BC
1 voter: BSimilarly here, COWPEA would elect AB in the same manner. Then combine the ballots:
4 voters: A
4 voters: B
2 voters: AC
2 voters: BCCOWPEA would now elect C with 1/9 of the weight as it is no longer Pareto dominated. Combining the ballots sets has changed C’s position within the electoral landscape. It does not seem unreasonable to elect C with some weight in this election, and it is therefore not clear that passing the consistency criterion is necessary for a proportional approval method.
Next I will briefly consider a couple of other optimal methods, one of which will also show problems with the multi-winner Pareto criterion.
-
One other method would be to pick a voter and split their representation equally among the candidates that they have approved. This would be strategy-proof. However, it fails candidate Pareto efficiency.
1 voter: AB
1 voter: AB would get 1/4 of the weight, and A 3/4. But B is Pareto dominated by A.
Another method is called the Conditional Utility Rule. This puts all the voter's representation onto the candidate that is most approved overall (or splits it equally if there's a tie). This guarantees a the maximum total approval score among a proportional result. But it fails IIB.
2 voters: A
1 voter: B
7 voters: ABThis would weight A:B 9:1. Passing IIB would give 2:1. But despite guaranteeing the maximum total approval score for a proportional result, it still fails multi-winner Pareto efficiency. It can sometimes be possible to find a set that dominates the winning set, although the result won't be proportional. See the result on this page. This is another reason why the multi-winner Pareto efficiency criterion is not necessarily a good thing within the voting election landscape.
I think this is largely it. This project hasn't purely been altruistic - it's been helpful to me by laying everything out for reworking my COWPEA paper!
-
I greatly appreciate your work!
Is this correct?
"COWPEA is the only method that is fair and consistent, but it may be the most difficult to sell to the public."Thank you, GregW
-
@gregw COWPEA doesn't pass consistency. Fairness is subjective. But COWPEA itself is just a proportional weighting thing rather than an election method itself. The lottery version could be used for elections but being non-deterministic would likely be a difficult sell.
-
@toby-pereira I have a moment now to take a look and I’m taking notes. I have a specific question for you though: Generally, do you think that registering for political parties and having that registration play a role in the voting process is something to be avoided?
-
@cfrank Yes. I think parties have their place as it makes it easier to know what someone is standing for in some cases and can simplify the process for voters, but I don't think they should form an essential part of the process, and it should be just as possible for independent candidates to stand.
-
This post is deleted!
