Thursday, April 6, 2017

Meek STV Explained

Photo of Brian Meek, the inventor of Meek STV.
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

10 comments:

  1. When does elimination takes place? I mean how long is this transfer of voting and manipulation of keep values done? When does one stop chaning keep values and eliminate a candidate?

    ReplyDelete
    Replies
    1. Hi Saumo, good question. The last place candidate is eliminated when the total number of surplus votes is less than the vote difference between the last two candidates. Suppose E is in last with 1 vote and D is second to last with 4 votes. E will be eliminated when the total number of surplus votes is less than 3.

      Delete
    2. Thank you Jeff O' Neill. I suppose this holds for Warren as well?

      Delete
    3. Yes, Warren is the same as Meek except for surplus transfers as described in the blog post.

      Delete
  2. Thank you Jeff, one last question, when the candidates are eliminated, it is mentioned that the counting takes place as if the candidate never existed. So in that case, are the keep values of all the candidates again made into one, or just the excluded candidates' kv made zero? I guess its the second option but I would like you to verify once.

    ReplyDelete
    Replies
    1. Only candidates still in the election have a keep factor so I would not say that an eliminated candidate has a keep factor of 0 (though intuitively it sort of makes sense). For eliminated candidates, they are simply ignored on the ballots. A candidate being eliminated always has a keep factor of 1 right before elimination (otherwise the candidate would be above quota and a winner so couldn't be eliminated) so the ballot is simply transferred to the next candidate. After transferring the ballot other keep factors may be updated as described in the blog post.

      Delete
  3. I notice your initial threshold is calculated via Droop quota (num votes/(seats +1)) + 1. On subsequent rounds of Meek the quota is typically recalculated via (votes - excess)/(seats + 1).

    Does this mean that the threshold would be reduced to 15 after round 1? Granted this doesn't change the outcome in this example.

    ReplyDelete
    Replies
    1. The Meek threshold can be reduced in subsequent rounds based on exhausted votes: (votes - exhausted)/(seats + 1). I've never seen it reduced based on excess votes. In the example above, no votes have been exhausted so the threshold wouldn't change.

      Delete
    2. Thanks for the quick reply! This article has been a great help towards my understanding of Meek STV.

      I think I've figured out where I was hung up. In my math I was finding exhausted votes in round 2. Assuming exhausted votes is just (total votes - current votes) we have (21.97 + 23.41 + 11.10 + 2 + 1) = 59.48, leaving 0.52 exhausted votes (60 - 59.48) = 0.52.

      Using a precision of 2 (scale factor of 100) and keeping the quota as a whole number we would then have something like this for quota calculation: (6000 - 52)/(3+1)/100 * 100 + 100 = 1500, or 15

      If there are no exhausted votes then it would still be 16.

      Delete
    3. Yes, that is right. I had forgotten that the rounding of keep factors causes exhausted votes. Glad you found this post useful.

      Delete