Thursday, April 6, 2017

Meek STV Explained

Brian Meek
Meek STV is the creme de la creme of STV counting rules. For you math nerds, I would even call it a beautiful algorithm! To appreciate all that beauty, we're going to have to get our hands dirty. I'm going to assume that you have a solid understanding of STV and that you've read our previous post describing Scottish STV. Feel free to brush up on STV and come back later if you need to.

Meek STV is named after Brian Meek (1934-1997) who first came up with these counting rules. I spent a lot of effort tracking down a photo of him to give him some publicity for his work!

As with all STV rules, there are two types of vote transfers: (i) vote transfers from eliminated candidates and (ii) transfers of surplus votes from candidates who have too many votes.

The magic of Meek STV is in transferring the surplus votes. Recall that STV rules have a winning threshold or a quota, and any votes held by a candidate above this winning threshold are surplus votes that need to be transferred.

Meek Surplus Transfers

Most STV rules handle transfer surplus transfers something like this. When transferring votes:
  1. candidates below the winning threshold receive votes, and
  2. candidates above the threshold do not receive votes and any votes that would go to them instead go on to the next choice on the ballot.
Accordingly, for most STV rules, a candidate exceeds the winning threshold exactly once. After this happens, the candidate is declared a winner and does not receive any more votes from future vote transfers.

With Meek STV, the key difference is that candidates who have exceeded the winning threshold can continue to receive votes and these candidates will continue to transfer surplus votes throughout the counting. This key difference is what makes Meek STV better than other STV rules.

Handling this continual receipt and transfer of votes sounds complicated, but there is actually a fairly easy way to do it. Each candidate in the election has a keep factor. For candidates below the winning threshold, the keep factor is 1 since they keep all of their votes. For candidates above the threshold, the keep factor is reduced to a number lower than 1. These candidates keep some fraction of their received votes and the remaining vote fractions get transferred to other candidates.

To illustrate, let's consider an election where we are electing 3 from a group of 5 candidates (we'll call them Alice, Bob, Chris, Don, and Eric) and there are 60 votes. The winning threshold is thus 16 (60/(3+1)+1). The 60 ballots for this election are the following:
  • 28 voters ranked Alice first, Bob second, and Chris third
  • 26 voters ranked Bob first, Alice second, and Chris third
  • 3 voters ranked Chris first
  • 2 voters ranked Don first
  • 1 voter ranked Eric first
The table below shows the vote counts for each round and the keep factors as indicated by the lower case letters in red. The first round is just the number of first place votes received by each candidate and this is shown in the table below along with an initial keep factor of 1 for each candidate. In the first round, Alice and Bob have each exceeded the winning threshold so we need to reduce their keep factors to transfer surplus votes.

R Alice Bob Chris Don Eric
1 28
a=1
26
b=1
3
c=1
2
d=1
1
e=1
2 21.97 = 28*a + 26*(1-b)*a
a=0.58
23.41 = 26*b + 28*(1-a)*b
b=0.62
11.10 = 3 + 28*(1-a)*(1-b) + 26*(1-b)*(1-a)
c=1
2
d=1
1
e=1
3 18.41 = 28*a + 26*(1-b)*a
a=0.43
18.04 = 26*b + 28*(1-a)*b
b=0.43
20.28 = 3 + 28*(1-a)*(1-b) + 26*(1-b)*(1-a)
c=1
2
d=1
1
e=1

To reduce Alice to the winning threshold of 16 votes, we use a keep factor of 16/28 since 16/28 times 28 reduces the 28 votes to 16. In practice, we use decimals instead of fractions so we'll convert the fraction to its approximate decimal value of 0.58. To reduce Bob to the winning threshold of 16 votes, we use a keep factor of 16/26 or a decimal value of 0.62.

Reducing the keep factors causes surplus votes to be transferred in the second round. Alice keeps 0.58 of her votes, and the remaining 0.42 of each of those votes go to the second choices on the ballots, which are all Bob in this example. Similarly, Bob keeps 0.62 of his votes, and the remaining 0.38 of each vote goes to the second choices on the ballots, which are all Alice in this example.

Accordingly, each of Alice and Bob are transferring surplus votes to each other. Additionally, however, fractions of votes are going down to the third choices on the ballots. Let's take a closer look at Alice with reference to round 2 in the table above.
  • At round 2, Alice keeps 0.58 of her initial 28 votes.
  • At round 2, Alice receives 0.38 [(1-b) in the table] of each of Bob's 26 votes, but because Alice keeps only 0.58 of her votes, she only keeps 0.58 of the votes received from Bob as well. Accordingly, Alice keeps 0.38*0.58 [(1-b)*a in the table] of the votes received from Bob.
  • Now since Alice is keeping only a portion of the votes received from Bob, where do the rest of those votes go? They go to the next choice on the ballot, which is Chris in this example. Accordingly, Chris receives 0.38*0.42 [(1-b)*(1-a) in the table] of the 26 votes that started with Bob.
The same applies for the surplus votes that Bob receives from Alice. Bob keeps only a portion of these votes and the remaining portions go to the next choice on the ballot, which is also Chris. Hopefully, the calculations for round 2 in the table above now make sense.

One funny thing. The goal of the surplus transfers was to reduce each of Alice and Bob to the winning threshold of 16, but this didn't happen. Alice now has 21.97 votes and Bob now has 23.41 votes. This is because each of Alice and Bob received votes from each other. If that hadn't happened, they each would have had close to 16 votes. Progress is being made however, as surplus votes are being transferred down the ballots and now Chris is receiving votes.

Since Alice and Bob still have surplus votes, we now need to further reduce their keep factors to continue to transfer their surplus votes. Alice currently has 21.97 votes with a keep factor of 0.58. We further reduce the keep factor by 16/21.97 to again get her close to the winning threshold of 16. This gives her a new keep factor of 0.43 (computed from 0.58*16/21.97). Similarly, Bob's keep factor is also reduced to 0.43 (computed from 0.62*16/23.41).

Round 3 shows the vote totals after updating the keep factors. Although Alice and Bob are still above the winning threshold, they are closer to it and Chris is receiving more votes. In fact, the election is now over because Chris has reached the winning threshold and all 3 winners have been selected.

The above explains how Meek STV works, but now let's look at why it is better than other STV counting rules. It all comes down to symmetry. All candidates are treated equally regardless of when or if they reach the winning threshold or if they are eliminated. Votes are always transferred from their first choice, to their second choice, to their third choice, and so on. With other STV methods, ballot choices will be somewhat arbitrarily skipped depending on when candidates reach the winning threshold.

Although the above example doesn't include eliminating candidates, another nice thing about Meek STV is that when a candidate is eliminated, the votes are counted as if the candidate was never in the election in the first place. With other STV methods, the presence of a candidate who is eliminated can change the outcome of the election.

Fixed Point Arithmetic

Those of you checking my math from the table above may question my math skills. Looking at Chris's vote total in the second round, it seems that 3 +28*(1-a)*(1-b)+26*(1-b)*(1-a) should be 11.6184 and not 11.10.

The reasons are too complex to address here, but floating point arithmetic is a really bad idea for counting votes. Accordingly, OpaVote uses fixed point arithmetic when counting votes. For the above example, 2 decimal places are used. When computing(1-a)*(1-b) the result is 0.1596 but since we are computing to two decimal places, this number gets rounded down to 0.15, and this is why the vote total is different from what you may expect. Generally, you will use more decimal places (OpaVote defaults to 6) so the effects of fixed-point arithmetic will be much smaller.

Warren STV

OpaVote also supports Warren STV which is similar to Meek STV, but there is a difference in how surplus votes are transferred. The table below shows Warren STV for the same ballots we used above for Meek STV.

Round 1 is the same as above, and in round 2 the keep factors are also the same as above. Though the vote totals for Alice, Bob, and Chris are now different. The difference is how the keep factors are applied to votes.

With Meek STV, the keep factors are applied on top of any keep factors applied to incoming votes. For round 2 above in the Meek count, Alice received 26 votes from Bob and both keep factors were applied to the votes so we have a product of the keep factors.

With Warren STV, the keep factors are applied relative to the vote itself. Consider round 2 below for Alice. Alice is receiving 26 votes from Bob that are each 0.38 [(1-b)] of a vote. Since the value of the incoming votes is less than Alice's keep factor of 0.58, Alice keeps all of the votes. Now consider round 3 below for Alice. Alice is now receiving 26 votes from Bob that are each 0.66 [(1-b)] of a vote. Since the value of the incoming votes is larger than Alice's keep factor of 0.36, Alice keeps only 0.36 of each vote, and the remainder of each vote goes to the next choice on the ballot, which is Chris.

One might wonder which of Meek STV and Warren STV is better... I personally don't have an opinion on this, and I generally recommend Meek STV simply because it was first and is more well known. If you would like more information about Meek STV and Warren STV, you can find their original papers here.

R Alice Bob Chris Don Eric
1 28
a=1
26
b=1
3
c=1
2
d=1
1
e=1
2 26.12 = 28*a + 26*min(a, 1-b)
a=0.58
27.88 = 26*b + 28*min(b, 1-a)
b=0.62
3
c=1
2
d=1
1
e=1
3 19.44 = 28*a + 26*min(a, 1-b)
a=0.36
19.44 = 26*b + 28*min(b, 1-a)
b=0.36
18.12 = 3 + 28*(1-a-b) + 26*(1-b-a)
c=1
2
d=1
1
e=1

No comments:

Post a Comment