Proportional approval system based on random ballots

[Toby Pereira]

I'm not entirely sure what results this would produce or if it's a new idea, but I was having some thoughts about a new proportional approval method.

Part A

1. Voters cast approval ballots.

2. A ballot is picked at random, and of the currently-unelected candidates approved on this ballot, one of these candidates is chosen at random.

3. This ballot is put back with the other ballots, not eliminated. Although ballots are eliminated if they have no unelected approved candidates left on them.

4. If there are more candidates still to elect, go to 2. Otherwise end part A.

We now have all the positions filled by candidates.

Part B

1. Repeat part A many times. (This doesn't actually need to be a random process. We could instead deterministically go through every possible outcome.)

2. Calculate for each voter the average number of elected candidates that they have approved.

3. Find the candidate set that most closely matches the voters' average number of elected candidates based on the sum of squared deviations. Elect this set.

End part B.

End.

I think this should provide proportional representation of some sort. It certainly elects the approval winner in the single-winner case, and that's always a good start. And for party voting, it's quite easy to see that it would work. But the question is what would it do in other situations with overlapping factions etc.?

I certainly don't think it would be perfect in all situations though. For example:

2 voters, 2 to elect

1 voter: A1-10, C, D

1 voter: B1-10, C, D

With the random part, both voters would average about 1 elected candidate each (just over 1), so the winning set would be one of the A candidates and one of the B candidates, rather than the obviously superior CD. But I think this is quite a simple system and has some merit.

[Toby Pereira]

Maybe monotonicity could be restored by always picking the most approved candidate from the random ballot rather than a candidate at random. This might skew things in other ways, but I think it should still yield acceptable proportionality.

[Toby Pereira]

It would skew the result in a case like this:

100 voters: A1-10

50 voters: A1-10, B1-10

99 voters: B1-10

Every time one of the 50 voters' ballots is picked, one of the A candidates would be chosen.

[Toby Pereira]

Looking at this here - https://groups.google.com/forum/#!msg/electionscience/l2YfWQ1XX7M/HPTrsFgVDQAJ - it would seem that PAMSAC wouldn't be bothered about equality between the As and Bs anyway, so I don't think it's that bad for this to happen.

Also, there might be ways around it anyway. Pick a ballot at random, and instead of picking an approved candidate from this ballot at random (the first idea) or the overall most approved candidate from this ballot (the second idea), note all the approved candidates on the ballot. Then pick another ballot at random and strike off from your list any candidates that aren't also approved on this ballot. Continue until one candidate is left. If the number of remaining candidates goes from >1 to 0 in one go, ignore the last ballot and continue. If it proves impossible to find a winner after continued searching, pick a candidate at random from those remaining on the list. We're adding complexity now, but this step isn't essential.

[Toby Pereira]

On Monday, 13 June 2016 16:09:45 UTC+1, Toby Pereira wrote:

3. Find the candidate set that most closely matches the voters' average number of elected candidates based on the sum of squared deviations. Elect this set.

This bit requires some explanation. It would need to be the squared deviation of the difference in a proportional sense.

For example, instead of (projected seats - seats)^2 it would be ((projected seats - seats)/(projected seats))^2.

And generally speaking, what is the optimum A/B split here?

2 voters: A1, A2...

100 voters: A1, B1, A2, B2...

1 voter: B1, B2...

The original formulation here would give a 52/51 split.

The first modification would give a 102/1 split.

The second modification would give a 2/1 split.

But if we changed it to:

3 voters: A1, A2...

100 voters: A1, B1, A2, B2...

0 voters: B1, B2...

The original formulation would give a 53/50 split.

The first modification would give a 103/0 split (100% A candidates).

The second modification would give a 3/0 split (100% A candidates).

Given that 53/50 in the second example seems wrong, I would inductively conclude that 52/51 in the first example is wrong, or at least not uniquely correct.

I'm not 100% sure off the top of my head what PAMSAC would do, and I see it as a decent yardstick. I will come back to this.

[Toby Pereira]

On Monday, 13 June 2016 23:59:39 UTC+1, Toby Pereira wrote:

On Monday, 13 June 2016 16:09:45 UTC+1, Toby Pereira wrote:

3. Find the candidate set that most closely matches the voters' average number of elected candidates based on the sum of squared deviations. Elect this set.

This bit requires some explanation. It would need to be the squared deviation of the difference in a proportional sense.

For example, instead of (projected seats - seats)^2 it would be ((projected seats - seats)/(projected seats))^2.

This would actually require a bit more modification actually. Let's say there is one candidate to elect and the ballots are as follows:

1 voter: A

1 voter: B

1 voter: C

Also standing but with no votes: D

After the "random" phase, each voter would average 1/3 elected candidates. This is closer to 0 than to 1, so basing it purely on squared deviation from the mean, we'd elect D, which would clearly be ridiculous. So we could say that only candidates that have been approved by at least one voter can be elected. But more generally, it would be sensible to say that we can only elect a slate of candidates than can possibly come up as a slate in part A (the random phase). This should also sort out the following example:

1 to elect

100 voters: A

100 voters: B

100 voters: C

1 voter: D

Although the A, B and C voters average about 1/3 each making D the "best" outcome for them, electing D would sent the squared deviation for the one D voter through the roof.

The average for each type of voter would be:

A, B, C: 100/301

D: 1/301

Electing any of A, B or C would give a total squared deviation of 100*((1-100/301)/(100/301))^2 + 200*((0-100/301)/(100/301))^2 + ((0-1/301)/(1/301))^2 = 605.01 http://www.wolframalpha.com/input/?i=100*((1-100%2F301)%2F(100%2F301))%5E2+%2B+200*((0-100%2F301)%2F(100%2F301))%5E2+%2B+((0-1%2F301)%2F(1%2F301))%5E2

Electing D would give 300*((0-100/301)/(100/301))^2 + ((1-1/301)/(1/301))^2 = 90,300 http://www.wolframalpha.com/input/?i=300*((0-100%2F301)%2F(100%2F301))%5E2+%2B+((1-1%2F301)%2F(1%2F301))%5E2

So A, B or C would be elected

 

And generally speaking, what is the optimum A/B split here?

2 voters: A1, A2...

100 voters: A1, B1, A2, B2...

1 voter: B1, B2...

The original formulation here would give a 52/51 split.

The first modification would give a 102/1 split.

The second modification would give a 2/1 split.

But if we changed it to:

3 voters: A1, A2...

100 voters: A1, B1, A2, B2...

0 voters: B1, B2...

The original formulation would give a 53/50 split.

The first modification would give a 103/0 split (100% A candidates).

The second modification would give a 3/0 split (100% A candidates).

Given that 53/50 in the second example seems wrong, I would inductively conclude that 52/51 in the first example is wrong, or at least not uniquely correct.

I'm not 100% sure off the top of my head what PAMSAC would do, and I see it as a decent yardstick. I will come back to this.

On this, I've checked what PAMSAC would do, and it would appear that would be indifferent between any of the "sensible" results. In the second example it would elect all A candidates, and not do anything like the 53/50 split. But in the first example, it would be happy with anything between 102/1 and 2/101.

But based on the principle that voters who approve everyone are essentially ignorable, the 2/1 ratio does seem to be the most sensible one for the first example. And that's what the third formulation of this new method would give. So it doesn't completely disagree with PAMSAC, but "weakly disagrees". But it's interesting that it's more decisive than PAMSAC here.

This method also appears to be a Sainte-Laguë method. But it would also fail "positive support". In this example with 2 to elect:

x: ABC

x: ABD

1: C

1: D

It would elect CD for any value of x. But then by adding the coin-flip approval transformation, it would presumably become a D'Hondt method and pass this, putting it on a par with PAMSAC.

But one crucial difference between this method and PAMSAC is that this method does not involve the removal of any approvals. So I will see if I can find any examples where this makes a difference and which would give superior results.

[Toby Pereira]

On Tuesday, 14 June 2016 17:16:22 UTC+1, Toby Pereira wrote:

This method also appears to be a Sainte-Laguë method. But it would also fail "positive support". In this example with 2 to elect:

x: ABC

x: ABD

1: C

1: D

It would elect CD for any value of x. But then by adding the coin-flip approval transformation, it would presumably become a D'Hondt method and pass this, putting it on a par with PAMSAC.

I don't know why I thought this actually. It clearly could elect AB. I haven't worked out the value of x where it would start doing that because it's a bit fiddly, but I'll have another look into it. But the coin-flip approval transformation wouldn't do anything good for this method, so it actually just seems a reasonable Sainte-Laguë alternative to PAMSAC.

[Toby Pereira]

On Monday, 13 June 2016 16:09:45 UTC+1, Toby Pereira wrote:

3. Find the candidate set that most closely matches the voters' average number of elected candidates based on the sum of squared deviations. Elect this set.

For completeness (and to make eight consecutive posts by one person in one thread), there is a reason why I'm using voter averages rather than candidate averages here, and it's to do with candidate clones. If we take a simple single-winner case:

2 voters: A

1 voter: B

Part A (the random phase) would find that A is elected 2/3 of the time, and B 1/3 of the time, so we'd elect A. But we could have:

2 voters: A1, A2

1 voter: B

In which case it would be 1/3 each, and a tie. We could even have:

2 voters: A1, A2, A3

1 voters: B

In which case a candidate average would elect B, as the A candidates would be elected 2/9 of the time each and B 1/3 of the time in the random part. But obviously one of the A candidates should be elected, so that's why we look at voter averages (which would still be 2/3, 1/3) rather than candidate averages (2/9, 1/3).

If candidates were to be elected in differing amounts of power proportional to their support, then we could do away with voter-based averages. In that last example, all the A candidates would have 2/9 of the power each, and B would have 1/3 of the power.

On the Electorama list, Forest Simmons once posted an election example and wanted to know how much weight each candidate (or each party if they are parties) should have in the following example:

40: AB

30: AC

20: C

10: BC

We would just work out the probability of each candidate being picked given the following algorithm:

Pick a ballot at random and note the candidates approved on this ballot. Pick another ballot at random, and strike off from the list all candidates not also approved on this ballot. Continue until one candidate is left. If the number of candidates goes from >1 to 0 in one go, ignore the last ballot and continue. If any tie cannot be broken, then elect the remaining candidates with equal probability.

For A it would be 4/10*3/4 + 3/10*4/7 = 33/70 = 0.4714.

For B it would be 4/10*1/4 + 1/10*4/9 = 13/90 = 0.1444.

For C it would be 3/10*3/7 + 2/10 + 1/10*5/9 = 121/315 = 0.3841.

And these probabilities correspond to the power each candidate would have in parliament.

And obviously this method could be turned into a score method using the "KP" transformation - http://scorevoting.net/QualityMulti.html#pertrans

[Toby Pereira]

Using voter averages doesn't work as well as I'd hoped actually. For example with two to elect we could have the following ballots:

2: A1, A2

1. B1, B2

During the random phase, the As would outperform the Bs by 2:1, and that would be reflected in the "optimum" number of candidates for each voter. But in the following case:

2: A1, A2

1. B1

The B voter wouldn't get 1/3 of the representation in the random phase because there aren't enough B candidates to ever get two. I think you'd get a 13/5 A/B ratio or about 72/28. The probability of getting two As would be (2/3)^2 or 4/9, and the probability of getting one A would therefore be 5/9. The probability of getting zero As would be 0. These numbers "should" be 4/9, 4/9, 1,9.

There might be a fix to this but I haven't got a definitive one as yet. You could, as a compromise, use the same idea as in Jameson Quinn and Bruce Schneier's SDV-LPE - https://www.schneier.com/academic/paperfiles/Proportional_Voting_System.pdf

If we go back to Forest Simmons's example:

40: AB

30: AC

20: C

10: BC

In SDV-LPE, a voter has one point that is spread equally among the candidates they have approved. So the scores for the candidates above would be

A: 35

B: 25

C: 40

Then the two candidates with the lowest two scores are compared on total approvals, and the lowest is eliminated. Voters' points are redistributed accordingly, and candidates are eliminated until the correct number remain. In this case A and B would go head-to-head and B would be eliminated.

My system could use the same elimination method but by using the scores I calculated in a previous post. To recap:

"We would just work out the probability of each candidate being picked given the following algorithm:

Pick a ballot at random and note the candidates approved on this ballot. Pick another ballot at random, and strike off from the list all candidates not also approved on this ballot. Continue until one candidate is left. If the number of candidates goes from >1 to 0 in one go, ignore the last ballot and continue. If any tie cannot be broken, then elect the remaining candidates with equal probability.

For A it would be 4/10*3/4 + 3/10*4/7 = 33/70 = 0.4714.

For B it would be 4/10*1/4 + 1/10*4/9 = 13/90 = 0.1444.

For C it would be 3/10*3/7 + 2/10 + 1/10*5/9 = 121/315 = 0.3841."

Obviously this elimination method isn't going to yield "perfect" results, but I will have to do some more thinking before this system is going to be fully up to scratch. Although this system has an "optimum" result, which involves different candidates being elected with different weights, it doesn't have a proper measure to compare other results.

[Toby Pereira]

Right, I might have something that works now. To compare two candidate sets, we simply see which one "steals" more of the representation. For example:

2 to elect

20: AB

10: AC

30: D

20: BC

20: CD

First of all, we can see how much representation each individual candidate steals:

A: 2/10*1/3 + 1/10*1/3 = 1/10 = 0.1

B: 2/10*2/3 + 2/10*2/5 = 16/75 = 0.213

C: 1/10*2/3 + 2/10*3/5 + 2/10*1/2 = 43/150 = 0.287

D: 3/10 + 2/10*1/2 = 2/5 = 0.4

We can now compare some of the pairs head-to-head:

CD beats AB by 0.687 to 0.313

BD beats AC by 0.613 to 0.387

AD and BC tie 0.5 to 0.5

Although CD has the most support as a pair, this is not enough to declare them the winning pair. Only AB and AC have so far been eliminated.

We can compare CD against BD and BC by ignoring A approvals:

20: B

10: C

30: D

20: BC

20: CD

The candidate representations are as follows:

B: 2/10 + 2/10*2/5 = 7/25 = 0.28

C: 1/10 + 2/10*3/5 + 2/10*1/2 = 8/25 = 0.32

D: 3/10 + 2/10*1/2 = 2/5 = 0.4

When comparing pairs of candidates that have a candidate in common, we can ignore the common candidate and look at the totals without them. We can clearly see that CD beats BC and BD.

This leaves CD and AD.

20: A

10: AC

30: D

20: C

20: CD

The candidate representations are as follows:

A: 2/10 + 1/10*1/3 = 7/30 = 0.233

C: 1/10*2/3 + 2/10 + 2/10*1/2 = 11/30 = 0.367

D: 3/10 + 2/10*1/2 = 2/5 = 0.4

Because C has more than A, CD beats AD and CD is the elected candidate pair.

I have proved that there will always be one candidate set that defeats all others in a head-to-head or if there can be cycles, although my intuition is that there will always be a dominant winning set. If so, then this system is looking pretty good. If not, then there might be a better way of comparing candidate sets.

[Toby Pereira]

This should say "I haven't proved..."

[Toby Pereira]

This would not work in a reasonable way unfortunately.

If we had the following approval ballots:

8: AB

1: A

1: C

Because A Pareto dominates B, this system would determine that B should have zero power. It would be 90% for A and 10% for C. But in a two-seat proportional parliament, we should have A and B.

What we can do when comparing AB against AC is to limit the amount of power that A ends up with, using e.g. the Hare or Droop quota. But how do you limit it? One possible method would be to scale down all scores given to candidate A by a set percentage until the quota is reached. And if we start with an approval ballot, we could use the KP transformation. But this is likely to get overly complex with more candidates to elect. We'd have to be turning knobs for more than one candidate at a time, and each would affect the other candidate's amount of representation. So this is not simple.

But, if we were adopting a system where different candidates could end up with proportional power in parliament, this system is actually very neat and simple to describe. It could also potentially be used for the proportions in asset voting.

On Thursday, 16 June 2016 13:13:06 UTC+1, Toby Pereira wrote:

[Toby Pereira]

I've thought of a bit of a weird paradox relating to this. To recap, I think a method based on the following could potentially yield a good system of PR:

Work out the probability of each candidate being picked given the following algorithm:

Pick a ballot at random and note the candidates approved on this ballot. Pick another ballot at random, and strike off from the list all candidates not also approved on this ballot. Continue until one candidate is left. If the number of candidates goes from >1 to 0 in one go, ignore that ballot and continue. If any tie cannot be broken, then elect the remaining candidates with equal probability.

Electing candidates with power proportional to their probability in the above algorithm would arguably give very good PR. We'd then just need to find a method to give the "closest" candidate set to this optimal figure (so that each elected candidate has one unit of power), or these letters could represent parties so these proportions would represent the proportion of power they would have and we don't have to change anything. But anyway, take the following ballots:

1 voter: ABC

1 voter: ABD

1 voter: AC

1 voter: AD

1 voter: BC

1 voter: BD

The proportion for A (and also B) would be 11/30.

The proportion for C (and also D) would be 4/30.

But looking at the ballots, CD is Pareto dominated by AB. That is to say that if A and B just had half the power each, no voter would be worse off and some would be better off. So an arguably better system would elect A and B with half the power each. But then if D wasn't standing, we'd have the following ballots:

1 voter: ABC

1 voter: AB

1 voter: AC

1 voter: A

1 voter: BC

1 voter: B

In this case, using the algorithm above, A and B would have 13/30 of the power each, and C would have 4/30 (unchanged).

But now, despite the fact that the "better" system didn't C or D with any power in the previous election, eliminating D from the election means that C now has to be elected. There is no longer any Pareto domination. Changing this latest result to half A and half B makes some voters worse off. The AC and the BC voters would go from 17/30 each to 15/30.

[Toby Pereira]

I think I now have a method for this that elects whole numbers of candidates into set positions, rather than fractionally. It would still have that weird Pareto failure paradox mentioned in the post above, but that might be unavoidable with this. The original method, which elects candidates with different weights, elects candidates in proportion to the probability that they would be picked by the following algorithm:

"Pick a ballot at random and note the candidates approved on this ballot. Pick another ballot at random, and strike off from the list all candidates not also approved on this ballot. Continue until one candidate is left. If the number of candidates goes from >1 to 0 in one go, ignore that ballot and continue. If any tie cannot be broken, then elect the remaining candidates with equal probability."

This would mean that potentially all candidates would be elected, although they would have very different amounts of power in parliament. So what is needed is a way of modifying this method to give a score to a slate of candidates with one unit of power each. This is actually quite simple.

Because we are looking at the score for a particular slate of candidates in isolation, we can ignore approvals for all other candidates. Let's say we want to find the score for candidate set ABC. We only look at approvals for these three candidates. Then we run the algorithm in sets of three, and find out the proportion of times that ABC are elected. There are a couple of caveats to this. Part of the algorithm above is "If the number of candidates goes from >1 to 0 in one go, ignore that ballot and continue." However, for this method, this does not apply to the first ballot picked as part of the algorithm. If this ballot has approved none of A, B or C, then this counts as a failure. However, it does not count as a failure if at least one ballot has already been picked that contains at least one of the candidates in the slate. The other caveat is that if A, B or C is successfully elected in the first or second of the three runs, then the elected candidate is eliminated for the subsequent run(s). This way the slate won't be disadvantaged by e.g. A getting elected twice. This will probably need some examples:

3 to elect

2 voters: A1, A2, A3

1 voter: B1, B2, B3

The algorithm will pick an A candidate 2/3 of the time, and a B candidate 1/3 of the time.

The score for A1, A2, A3 is (2/3)^3 = 8/27 (if e.g. A1 is elected first in a run of three, then A1 is not longer considered in the other two runs. Duplicates can't happen, so if no B candidates are picked, then it must be A1, A2, A3.)

The score for B1, B2, B3 is (1/3)^3 = 1/27

The score for any of two As and 1 B is (2/3)^2 * (1/3) *3 = 12/27

The score for any of two Bs and 1 A is (1/3)^2 * (2/3) * 3 = 6/27

So in this case the most proportional result is the winner. I think I have a proof that this always gives D'Hondt proportionality. I won't put it in this post, but to give an example:

2 to elect

2 voters: A1, A2

1 voter: B1, B2

D'Hondt would award a tie between two As and one of each.

The score for A1, A2 is (2/3)^2 = 4/9

The score for one of each is 2/3 * 1/3 * 2 = 4/9

Which is what we wanted. It also trivially passes strong PR. This is because if there is a slate of candidates with universally approved candidates, then when the algorithm is run, these candidates would all be elected (and eliminated from further consideration) before any other candidates can be elected. So to modify the above example:

3 to elect

2 voters: U, A1, A2

1 voter: U, B1, B2

If we wanted to calculate the score for U, A1, A2, then in each set of three runs of the algorithm, U would be elected first (probability of 1) and then it would just become identical to the above example, so the score would be 1 * 4/9 = 4/9.

One other example:

2 voters: A1, A2...

100 voters: A1, B1, A2, B2...

1 voter: B1, B2...

I have argued previously that the optimal A:B split should be 2:1, and that the 100 voters who vote for everyone should effectively be ignored. In this method, that's what would happen.

I need to check a few things to make sure that this passes all the other criteria that it should, but I think this is very promising. But I need to revisit the Pareto failure first. I'll quote directly from the previous post, but we can imagine that A, B, C and D are all parties fielding several candidates and that there are 30 seats available:

"1 voter: ABC

1 voter: ABD

1 voter: AC

1 voter: AD

1 voter: BC

1 voter: BD

The proportion for A (and also B) would be 11/30.

The proportion for C (and also D) would be 4/30.

But looking at the ballots, CD is Pareto dominated by AB. That is to say that if A and B just had half the power each, no voter would be worse off and some would be better off. So an arguably better system would elect A and B with half the power each."

I said above that this might be unavoidable. But you might just think that as there are other methods that don't fail this criterion, why not just use one of them? Well, I don't know of any method that passes all the criteria this one does, and it might be impossible to pass them all plus Pareto. Of course, we could trivially make it pass by adding a rule saying not to elect a Pareto-dominated set, but even that wouldn't achieve much. Imagine the following ballots instead:

1000 voters: ABC

1000 voters: ABD

1000 voters: AC

1000 voters: AD

1000 voters: BC

1000 voters: BD

1 voter: CD

CD is now longer Pareto dominated, but nothing has really changed in practice as to what would be the "best" result. Also, in the original example, although CD is dominated by AB, neither C nor D individually are dominated.

I might also look at trying to get a Sainte-Laguë version.

Toby

[Warren D Smith]

On 1/12/18, 'Toby Pereira' via The Center for Election Science

<electio...@googlegroups.com> wrote:
> I think I now have a method for this that elects whole numbers of
> candidates into set positions, rather than fractionally. It would still
> have that weird Pareto failure paradox mentioned in the post above, but
> that might be unavoidable with this. The original method, which elects
> candidates with different weights, elects candidates in proportion to the
> probability that they would be picked by the following algorithm:
>
> "Pick a ballot at random and note the candidates approved on this ballot.
> Pick another ballot at random, and strike off from the list all candidates
> not also approved on this ballot. Continue until one candidate is left. If
> the number of candidates goes from >1 to 0 in one go, ignore that ballot
> and continue. If any tie cannot be broken, then elect the remaining
> candidates with equal probability."

--First of all, the tie always can be broken if there exist (or if we
artificially add
these fake voters to the voter pool) for each candidate a voter
who approves him and him alone.

Given that assumption, we may reword the above proposal
in a manner than I enjoy more, but seems nearly equivalent:

"The weight Wc we award to candidate c in the weighted legislature,
is proportional to 1/(1-A) where A is the fraction of voters who approve c."

This is since the chance c still survives after k real voters are
randomly chosen is
A^k, and then we can terminate the process by then going directly to the fake
voter who approves c only. Summing over k=0,1,2,3... we get 1/(1-A).

Right?

This seems to be suspiciously simple. Can we really obtain a good multiwinner
system that simply makes the voting-weight of a candidate be a
function solely of
the number of voters who approve him?

If not, give up this line of approach.

If yes, then a clearer way to investigate the situation is just to
decide what function
it ought to be.


--
Warren D. Smith
http://RangeVoting.org <-- add your endorsement (by clicking
"endorse" as 1st step)

[Warren D Smith]

Umm, in my attempt to analyse the probabilistic process,
maybe it is better to use a more general process where
each step you either pick a random real voter (chance B/V where
V is #voters, for each) or with chance Q=(1-B)/C for each
pick one of the C fake voters who approve
exactly one of the C candidates.

Then the weight awarded to a candidate, who is approved by fraction A
of the real voters, is
Q + (1-Q)*A*Q + (1-Q)^2*A^2*Q + (1-Q)^3*A^3*Q + ...
which we sum to
Q / [1-(1-Q)*A]
in the previous post I was sort of implicitly taking the Q-->0+ limit
of that, due to not clear enough thinking.

Anyhow, again, for any particular Q, this is just a function of A.

We immediately see all methods of this ilk are devastated by
candidate-cloning. Right?

[Toby Pereira]

I think you've misunderstood what I meant.

"Work out the probability of each candidate being picked given the following algorithm:

Pick a ballot at random and note [in a list] the candidates approved on this ballot. Pick another ballot at random, and strike off from the list all candidates not also approved on this ballot. Continue until one candidate is left. If the number of candidates goes from >1 to 0 in one go, ignore that ballot and continue. If any tie cannot be broken, then elect the remaining candidates with equal probability."

To take a very simple example:

2 to elect

1 voter: A1, A2

1 voter: B

If we run the algorithm, there is a 1/2 chance we first pick the A voter's ballot. Candidates A1 and A2 are put on the list. Another ballot is picked at random, if we get the A voter again, nothing changes. If we get the B voter, A1 and A2 are not on the ballot, but we can't strike them off the list because it would bring the remaining candidates down to zero. This ballot is therefore ignored. Nothing further can be done so the A1/A2 tie cannot be broken. So in the 1/2 chance that the A voter's ballot is picked first, A1 is elected half the time and A2 is elected half the time. 1/2 * 1/2 = 1/4, so this gives them 1/4 of the parliamentary power each.

Then there is also a 1/2 chance that the B voter's ballot. This contains just one candidate, so the algorithm ends there. So we end up with:

A1: 0.25

A2: 0.25

B: 0.5

It is cloneproof. It is also the same as the "random ballot" tie-break method mentioned here http://rangevoting.org/TieBreakIdeas.html except with approval voting.

It elects candidates with different weights, but my previous post before this one describes how to elect candidates "normally".

Toby

[Warren D Smith]

Sorry, indeed I was confused about cloneproofness.

[Toby Pereira]

I have a bit more to say about this Pareto failure, and how it's arguably different for multi-winner elections anyway. To start with a very simple example:

2 to elect

1 voter: AB

1 voter: AC

It's clear that you'd want to elect either AB or AC. However, BC is arguably the more proportional result as it leaves everyone equally represented. But this case would fail monotonicity as well as Pareto, and I don't think you'd get many people arguing that BC is the best result here. The new method here would not fail in this case anyway. Another example:

2 to elect

5 voters: AC

4 voters: BC

1 voter: BD

Most sensible methods would elect BC. But let's not worry about that for now. An optimising method that gives a score to any slate of candidates should be able to rank all slates of candidates in order. Compare AB with CD. In both cases, every voter would have exactly one candidate elected. But AB seems to me to be the far more proportional result and I might expect a method to give AB the better score. In the CD case, the single D voter is arguably better off as they don't have to share their representation with anyone else and effectively have this candidate to themselves. But then imagine this case:

2 to elect

500 voters: AC

400 voters: BC

100 voters: BD

1 voter: CD

Now CD Pareto dominates AB in this sense of number of elected candidates each voter has approved. So would we say that any method that gives AB a higher score than CD is a bad method? Or would we perhaps say that it doesn't matter because neither would actually be the winning set (BC would be)?

The point is that the Pareto failure of the new method I have described results in a parliament that is arguably more proportional in this sense, so maybe it's not such a bad thing.

But there are cases where this sort of Pareto failure is definitely bad. If a group of friends are deciding where to go out to eat or what film to watch on a few occasions then all that really matters to a voter is how many of their approvals get elected. It doesn't matter how many other people they have to "share their representation" with.

Toby

[Warren D Smith]

> But there are cases where this sort of Pareto failure is definitely bad. If
> a group of friends are deciding where to go out to eat or what film to
> watch on a few occasions then all that really matters to a voter is how
> many of their approvals get elected. It doesn't matter how many other
> people they have to "share their representation" with.

--it seems to me in a situation like the "group of friends watching
several films,"
the thing to do is simply hold repeated single-winner elections (reduce
the set of film-candidates by 1 each time one wins).

If we had a perfect single-winner system that maximizes summed-utility
of the winner, then the "repeated single-winner election" scheme would
also maximize summed utility of the full set of winners.

The multiwinner problem only gets particularly interesting and hard
when it is NOT
best to use repeated single-winner elections.

Now, to alter the scenario a bit, suppose your happiness when you get
to see N films you like, is NOT proportional to N, it only grows like,
say, log(N).
In that case we'd no longer want to maximize number of approvals in
the films scenario and some scheme like Thiele would become better.

[Toby Pereira]

Well I would say that I'd still want a proportional system the group of friends to stop one "faction" that had certain tastes dominating. For the meal example, if two of them always prefer curry and three prefer pizza, I don't think it would be satisfactory to go for pizza every time. So I wouldn't take a simple additive utility approach. I think PR makes sense, but arguably on the more majoritarian end of PR. But I'm not sure any of the methods we've discussed, including Thiele, work perfectly for this either.

[Warren D Smith]

> Well I would say that I'd still want a proportional system the group of
> friends to stop one "faction" that had certain tastes dominating. For the
> meal example, if two of them always prefer curry and three prefer pizza, I
> don't think it would be satisfactory to go for pizza every time. So I
> wouldn't take a simple additive utility approach. I think PR makes sense,
> but arguably on the more majoritarian end of PR. But I'm not sure any of
> the methods we've discussed, including Thiele, work perfectly for this
> either.

--I think you don't really mean it.
If you wanted to maximize "A tastes B" type happiness purely, you'd
go pizza every time. The real issue here is you also care about a certain other
kind of happiness, which arises from the friends being friendly.
And the perception of repeatedly ignoring the tastes of the same two of them,
might undermine that psychology.

Something like that happened to me once. There were 5 people writing
a scientific
paper. I was one of them. I was the "interloper" in the sense that
there had been
a public lecture by 1 or 2 of them about the work of the 4. I came to
them the next day and explained that their results were weak and here
was how to get a lot better results. So then I was to become a
co-author. However, there then were numerous joint decisions to be
made about the paper. And a funny thing happened. Every time such a
decision was to be made, the vote was always 4 to 1 with me being the
1. This happened about 8 times
in a row. Now I did not think my views were at all unreasonable on
those. It seemed
to me the only explanation was that there was a conspiracy, since I did not
think such incredible unanimity of tastes could have arisen by pure
luck. Further, the 4
were writing the paper in secret, with me not being allowed to see
what they were writing until soon before some deadline. I did not
think this was a reasonable way to write a paper. But those 4,
unanimously, did. Then one of them told me the reason for this
was he felt that I was "not a team player."

So anyhow, that episode left me very unhappy and disgusted. I still to this
day do not comprehend what was going through their minds. Probably
there was some kind of abusive power relationship where one of them
controlled the other 3 somehow?
However, as a matter of repeated vote democracy, I guess this was "optimum."

[Toby Pereira]

But my point is that I don't think that this form of repeated vote democracy would be appropriate in the friends situation, any more than I do in a parliament. I don't think utility would be accurately modelled by assuming it's the same every time. I think people would see it as fairer if things were done in a more proportional way, and this would have an effect on utility. And those constantly on the wrong end of a 3-2 majority might start feeling disillusioned.

Of course, I agree that in a situation where utilities are "reset" each time, then repeated single-winner votes would be optimum. I just think that this wouldn't be a case where the utilities can be considered to be reset.

In your case, I'd argue that the goal is not really utility of the paper writers anyway, but quality of the paper. Ignoring alternative opinions is likely to be counterproductive.

[Warren D Smith]

>
> In your case, I'd argue that the goal is not really utility of the paper
> writers anyway, but quality of the paper. Ignoring alternative opinions is
> likely to be counterproductive.

--well, I was certainly focused on paper quality, although I think the
other 4 had
other priorities. If we had used Thiele voting instead, first of all
they would have refused
to do that, and second it would have produced a random effect where,
instead of me losing
al 8 votes 4-1, say I would have won 2 of the 8 votes -- just which 2
being random.
This would have been strange. Further no matter which two it was, they
would have been
hard to justify by themselves. If via some scheme I wanted to be able to choose
(what I thought were) the two most important among the 8, then they might
have counter-reacted via strategic voting which might have made me win the
least-important two instead.

I don't think there was any solution in the case of that paper. In
retrospect if I knew then
what I know now, I should have just kept my improvements secret and
written my own paper without them. Although it seemed sometimes that
they would have also preferred that, if I had done it they probably
would have been angry and claimed my behavior was unethical. So there
was no way out.

[Toby Pereira]

Just to give this example again:

2 to elect

5 voters: AC

4 voters: BC

1 voter: BD

AB and CD both give every voter one approved candidate each, but AB is a proportional result, whereas CD is not. This new "random ballot" method gives AB a score of 1*0.5 = 0.5. It gives CD a score of 0.9*0.1 + 0.1*0.9 = 0.18. So it considers AB to be a better result. PAMSAC is a bit more awkward to work with, but if we start with the AB result, the relevant ballots are:

5 voters: A

5 voters: B

Then we apply the coin-flip approval transformation (CFAT), leaving us with:

2.5 voters: A

2.5 voters: B

5 voters: -

The sum of the squared loads is 5*(1/2.5)^2 = 0.8. Now for CD:

9 voters: C

1 voter: D

Applying CFAT gives us:

4.5 voters: C

0.5 voters: D

5 voters: -

The sum of the squared loads is 4.5*(1/4.5)^2 + 0.5*(1/0.5)^2 = 2.22. This is much higher than the 0.8 of AB, and with higher being worse, PAMSAC agrees that AB a better result than CD. Of course, this AB>CD result would also apply in the following case:

500 voters: AC

400 voters: BC

100 voters: BD

1 voter: CD

But in this case CD Pareto dominates AB in the sense that every voter would have approved at least as many elected candidates under CD as under AB and at least one voter would have approved more. And while AB or CD wouldn't be the winning result anyway (BC seems the best result here), it does raise the possibility that PAMSAC could fail this form of Pareto efficiency when it comes to a winning result, just like the random ballot method does. It might fail the same example, but PAMSAC is difficult to work with so I won't try to work it out just now.

However, it seems to me that for a method to regard AB and CD as equal and for it to regard CD as better in the case with one extra CD voter, then its methodology would have to be just to look at the number of elected candidates each voter has approved, and use satisfaction scores for the voters based on this. But then it would just be the Thiele method, which comes with its own set of problems. So it might be that this form of Pareto failure is unavoidable for approval PR methods unless you want to stick with Thiele. And I definitely don't want to do that.

Toby