Breaking ties in score/approval voting

[Toby Pereira]

If there is an exact tie between two or more candidates, it might seem fair to just apply some random procedure where each of the tying candidates has an equal probability of winning, but that's not necessarily fair, or indeed independent of clones. Take the following approval example:

10 voters: A

10 voters: B

It's an exact tie between A and B, and as far as random tie-breakers are fair, 50/50 is right here.

But we could have this example:

10 voters: A, C

10 voters: B

In this case, A has been cloned. A and C should have a 25% each of winning, with C having a 50% chance. So we'd need more than just the final totals/averages to determine the tie-break probabilities. You could just say that each voter has one point that they share equally among their approved voters, and the points a candidate ends up with is proportional to their probability of winning the tie-break. In this case, A and C would each end up with half the points of B, and we'd end up with the right numbers.

Score voting is a little more complicated. Let's say A and B are tied, and this is one person's ballot (with a max score of 100):

A=10, B=5

We could apply the single-point allocation procedure again, and say that A has been allocated 2/3 (10/15) and B has been allocated 1/3 (5/15) by this voter. But there is an alternative. We could apply the "KP transformation" where we convert scores into approvals, which is known to be useful for some PR methods. In this case, this one ballot would convert to:

0.5 voters: A

0.5 voters: A, B

And by doing this, A would be allocated 3/4 and B 1/4.

Which is better?

[Toby Pereira]

I think I'd go for the KP transformed version. If someone submitted the following ballot:

A=10, B=5, C=5, D=5, E=5

Then in the unlikely event of a five-way tie the maximum scoring candidate (A) would still be guaranteed half the allocation from this voter, plus a fifth of the remaining. So it would be 0.6 to A and 0.1 to each of the others.

Without the KP transformation, A would be swamped by the proliferation of 5-scoring candidates, and would end up with 1/3 of the allocation, with the others getting 1/6 each.

[Toby Pereira]

But this still isn't ideal. If we have:

1 voter: A=10, B=5

1 voter: A=0, B=5

Using KP, A and B would both get 3/4 of an allocation, so the tie-break would be a coin toss. But in this case:

1 voter: A=10, B=5, C=5

1 voter: A=0, B=5, C=5

A would end up with 2/3 of an allocation, whereas B and C would each end up with 5/12, making 5/6 in total. This favours the "clones". But there does seem to be a way around this. To borrow from my other recent discussion thread, we can work out the probability of each candidate being picked given the following algorithm after the KP transformation has been applied:

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.

With this example:

1 voter: A=10, B=5

1 voter: A=0, B=5

It would be 50/50 between A and B.

With this example:

1 voter: A=10, B=5, C=5

1 voter: A=0, B=5, C=5

It would be 50% for A, and 25% each for B and C.

I believe that this is the optimum way to break ties in score voting elections.

[Toby Pereira]

I just found this - http://rangevoting.org/TieBreakIdeas.html - it mentions a random ballot tie-breaker which is similar to what I suggested but not identical. Basically it takes a ballot at random and sees which candidate is scored higher, and if it's still a tie continues until the tie is broken.

With this example (max 9):

1 voter: A=9, B=3

2 voters: A=0, B=3

The random ballot method would elect B 2/3 of the time and A 1/3. In my system it would be 50/50.

[Neal McBurnett]

On Tue, Jun 21, 2016 at 03:06:29AM -0700, 'Toby Pereira' via The Center for Election Science wrote:
> If there is an exact tie between two or more candidates, it might seem fair to just apply some random procedure where each of the
> tying candidates has an equal probability of winning, but that's not necessarily fair, or indeed independent of clones. Take the
> following approval example:
>
> 10 voters: A
> 10 voters: B
>
> It's an exact tie between A and B, and as far as random tie-breakers are fair, 50/50 is right here.
>
> But we could have this example:
>
> 10 voters: A, C
> 10 voters: B
>
> In this case, A has been cloned. A and C should have a 25% each of winning, with C having a 50% chance. So we'd need more than just
> the final totals/averages to determine the tie-break probabilities. You could just say that each voter has one point that they
> share equally among their approved voters, and the points a candidate ends up with is proportional to their probability of winning
> the tie-break. In this case, A and C would each end up with half the points of B, and we'd end up with the right numbers.

This makes no sense at all to me. It is a totally clear three-way tie. If you took just one vote away from any two of the candidates, it would be a clear win for the one who still had 10 approvals. Suddenly changing the rules and pretending that voters have to allocate one point among candidates is wrong, since they likely would have voted differently if that was the method (essentially "Modified Cumulative Voting" as discussed at https://electology.org/voting-systems-confused-approval-voting)

By same logic, the score voting reapportionment below also would be very unfair.

On Tue, Jun 21, 2016 at 04:25:04AM -0700, 'Toby Pereira' via The Center for Election Science wrote:
> I just found this - http://rangevoting.org/TieBreakIdeas.html - it mentions a random ballot tie-breaker which is similar to what I suggested but not identical. Basically it takes a ballot at random and sees which candidate is scored higher, and if it's still a tie continues until the tie is broken.

Offhand, this makes much more sense for score voting.

Neal McBurnett http://neal.mcburnett.org/

> Score voting is a little more complicated. Let's say A and B are tied, and this is one person's ballot (with a max score of 100):
>
> A=10, B=5
>
> We could apply the single-point allocation procedure again, and say that A has been allocated 2/3 (10/15) and B has been allocated
> 1/3 (5/15) by this voter. But there is an alternative. We could apply the "KP transformation" where we convert scores into
> approvals, which is known to be useful for some PR methods. In this case, this one ballot would convert to:
>
> 0.5 voters: A
> 0.5 voters: A, B
>
> And by doing this, A would be allocated 3/4 and B 1/4.
>
> Which is better?
>

> --
> You received this message because you are subscribed to the Google Groups "The Center for Election Science" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to electionscien...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Toby Pereira]

On Tuesday, 21 June 2016 14:56:00 UTC+1, Neal McBurnett wrote:

On Tue, Jun 21, 2016 at 04:25:04AM -0700, 'Toby Pereira' via The Center for Election Science wrote:
> I just found this - http://rangevoting.org/TieBreakIdeas.html - it mentions a random ballot tie-breaker which is similar to what I suggested but not identical. Basically it takes a ballot at random and sees which candidate is scored higher, and if it's still a tie continues until the tie is broken.

Offhand, this makes much more sense for score voting.

Neal McBurnett                 http://neal.mcburnett.org/

This is pretty much where I ended up anyway, except that I would do the "KP" transformation. The main difference is that in my system if there are exactly two candidates that are tied, it will always be a 50/50 chance of either one winning, but it won't necessarily be so if you just take random ballots.

But also, you say that makes more sense, but it still goes against your original objection:

10 voters: A, C
10 voters: B

The random ballot tie-breaker on the page linked to would elected B with 50% chance and A and C with 25% chance each.

[Toby Pereira]

Basically, what I'm going for is:

1. For a two-way tie, it should be a coin toss

2. For any more, it should be cloneproof.

And I think my latest proposal (KP transformation followed by random ballot drawing) achieves that.

[Frank Martinez]

Can You explain what "KP transformations" are a bit more and how they translate scores into approvals?

--

You received this message because you are subscribed to the Google Groups "The Center for Election Science" group.
To unsubscribe from this group and stop receiving emails from it, send an email to electionscien...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--
P.S.: I prefer to be reached on BitMessage at BM-2D8txNiU7b84d2tgqvJQdgBog6A69oDAx6

[Toby Pereira]

Yes. Warren has a bit on his site about it here: http://scorevoting.net/QualityMulti.html#pertrans

But basically, if the max score is m, then each ballot is effectively split into m parts. So for a maximum score of 10, it's split into 10. If you then number the parts 1 to 10, a candidate given a score of x is approved on parts x and below.

For example, this might be a ballot rating the candidates A, B, C and D

A=10, B=9, C=5, D=1

The ballot is split into 10 approval ballots as follows:

Part 1: ABCD

Part 2: ABC

Part 3: ABC

Part 4: ABC

Part 5: ABC

Part 6: AB

Part 7: AB

Part 8: AB

Part 9: AB

Part 10: A

To unsubscribe from this group and stop receiving emails from it, send an email to electionscience+unsubscribe@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

[Frank Martinez]

Thank You. I am confused, though. How is this transformation different than summing the scores?

To unsubscribe from this group and stop receiving emails from it, send an email to electionscien...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--
P.S.: I prefer to be reached on BitMessage at BM-2D8txNiU7b84d2tgqvJQdgBog6A69oDAx6

--

You received this message because you are subscribed to the Google Groups "The Center for Election Science" group.

To unsubscribe from this group and stop receiving emails from it, send an email to electionscien...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

[Kevin Baas]

To make it clone proof you switch it to an allocation vote (that is, normalize each ballot so the scores sum to one) with proportional vote transfer.

here's a counter i wrote to demonstrate:  http://autoredistrict.org/allocation_counter.zip

in the first scenario, a tie is a tie - you break it randomly.  (and when you have a tie picking a ballot at random is no different from flipping a coin - except for being more work.)

if you have a clone, then votes transfer proportionally until quota is reached.

let's say there are 24 ballots, electing 2 seats, so quota is 24/2 = 12.

14: 0.6 A 0.4 B 0 C

10: 0.0 A 0.0 B 1 C

A has 8.4, B has 5.6, C has 10.  No candidate makes quota so the weakest - B - is transfered proportionally to the other choices.  resulting in:

14: 1.0 A 0.0 B 0 C

10: 0.0 A 0.0 B 1 C

A has 14, C has 10.  A makes quota and is elected.  those ballots now each count as (ballots used - quota) / (ballots used) ballots.  so that's (14-12)/14 = 1/7th of a ballot.

14*1/7=2: 0.6 A 0.4 B 0 C

But since A is already elected, the allocation is transferred proportionally:

2: 0.0 A 1.0 B 0 C

so now there's 2 for B, 10 for C.  neither has quota, so weakest is transferred.  there are no scores left to transfer to, so the ballots are just eliminated, leaving only one candidate: C.  Thus C is elected.

Final outcome: A,C.

introducing proportional transfer makes it clone-proof.  in order to introduce proportional transfer you have to first normalize the scores, thus turning it into allocation voting.

[Kevin Baas]

self-correction: when i said "when you have a tie picking a ballot at random is no different from flipping a coin" i didn't consider the problem of clones.  yeah, the easy way out there is to pick a ballot at random.

[Kevin Baas]

...but that's only AFTER you can't transfer votes any more.

[Toby Pereira]

It only comes into play for the tie-break. Transforming the ballots that way wouldn't make any difference to the total/average scores.

It also happens to be useful for some systems of proportional representation that use approval ballots, as it allows them to easily be converted to a score method.

On Tuesday, 21 June 2016 16:51:07 UTC+1, Frank Martinez wrote:

[Toby Pereira]

So to explain the tie-breaker in one post:

If there is a tie, then do the KP transformation on all ballots, which gives you approval ballots. Start with a list of all the tied candidates. Pick one of the KP approval ballots at random and strike from your list any of the tied candidates not approved on this ballot. If this means that the number of remaining candidates goes from >1 to 0, then ignore this ballot. Pick ballots at random until one candidate is left. This candidate is elected.

The reason I prefer this to the idea on Warren's site (pick a ballot and random and elect the tied candidate with the highest score), is that in a two-way tie, my method is always equivalent to a coin toss. If two candidates have tied in a score voting election, then by score voting "philosophy" they are equal. Obviously we can look at other measures, but which one to pick would be to some extent arbitrary, as we'd be changing the standard by which candidates are measured. If we stick to score voting's own logic, then it's 50/50.

But when there are more than two tied candidates, the possibility of candidate clones becomes an issue, and this deals with that as well. So I would argue that this the most natural way of breaking ties.

[Kevin Baas]

regardless of what the most "natural" way is, the fairest way is to convert the ballots to allocation ballots, and then do proportional vote transfers until you get a winner (over quota or only remaining) or a tie among all remaining candidates, in which case you eliminate a random ballot and repeat.

[Toby Pereira]

But aren't you talking about how to run the elections generally, rather than just the tie-break? My question was originally about how to break the tie given that the initial election is held under "normal" score voting - so no normalisation, allocation etc.

[Kevin Baas]

And that's the question I answered.

In order "to break the tie given that the initial election is held under "normal" score voting", you have to first deal with clones.  To deal with clones you have to transfer votes.  Score voting votes aren't transferable, so you need to convert them to allocation votes by normalizing.  Then you deal with the clones.  Then if there is still a tie, that's a "true" tie; a clone-less tie.  Then to break the true tie, you randomly eliminate a ballot and repeat.

[Aaron Hamlin]

The general advice I give is to use score voting when the number of voters is few. If there is a tie in a score voting election, then you can take pairwise comparisons between the top two scores in the same vain as instant runoff range voting, which Mark Frohnmayer proposed awhile back.

If there's still a tie, then perhaps you can convert the scores to ranking and take a Condorcet winner if there is one and if not use a Condorcet tie breaking procedure.

Best,

Aaron

[Toby Pereira]

My system does deal with clones as well, and is also "neutral" in that without clones, a tie would end up in an equal probability tie-breaker. In other words the tie-breaking mechanism isn't biased towards any particular way of getting a score, whether through a small number of maximum scores, a large number of lower scores etc. So it would always be a coin toss in a two-way tie. I think this is correct behaviour. Does your method do this?

[Kevin Baas]

not sure who you're asking.  if you're asking me, yes.  with the method i described, tie-breaking is unbiased.