Up: Issue 12 Previous: Paper 3 Next: Paper 5

# Voting matters - Issue 12, November 2000

## The computational accuracy using the Meek algorithm

### Introduction

The Meek algorithm is specified without regard to the accuracy of the computation (with the exception of the convergence criterion, which is not relevant to this paper). The formulation in Pascal uses the type real which is traditionally floating point, but this could have varying accuracy or even be replaced by a rational arithmetic package of unbounded precision. A natural question to ask is what computational accuracy is required to ensure that the 'correct' candidates are elected, ie, the same candidates as if infinite precision was used. We demonstrate by examples, that there are cases in which very high precision is required.

### An example

If a candidate A has first preference votes which only just exceed the quota, then those who have given A as their first preference will have only a small fraction of their vote passed on to their subsequent preference. Moreover, if most of A's subsequent preferences are for B (say) and just one for C, then the fraction going to C can be made smaller still.

The above leads to the following example in which 3 seats are to be filled:

```    333    AX
333    AY
333    AZ
333    BX
333    BY
333    BZ
667    X
667    Y
667    Z
1    ABX
1    ABY
2    BAX
```
The total number of votes is 4003, which gives an initial quota of 1000.75. Since A and B each have 1001 first preference votes, there is a surplus to transfer after their election of a quarter of a vote. This implies that the weight associated with A and B is roughly (1-1/4000). This further implies that the vote ABX makes a contribution to X of roughly 1/16,000,000th of a vote.

After the election of A and B, one of X, Y or Z must be eliminated. In the cases above, it is clear this should be Z, since that candidate has no contribution from the last three votes, but X and Y do. However, if the implementation of Meek only recorded millionths of a vote, then the last three candidates would be regarded as equal, in which case, a tie- break would occur.

For this test, we are only concerned as to what happens at the third stage. If a tie-break occurs, we know that the implementation does not have the accuracy necessary to compute the same result that would arise from infinite accuracy.

The above example illustrates that the accuracy required to give the same result as with infinite precision is unbounded even with six candidates (since we can just use more votes to increase the accuracy needed). However, the same technique can be employed with more candidates to increase the accuracy without increasing the number of votes. For instance, with 69 candidates and less than 1,000 votes, one can produce an example requiring 127 decimal places! The full details of this are available from the author.

### Conclusions

There are somewhat bizarre voting patterns in which the accuracy required by the Meek algorithm is high, if the same result is to be obtained as that which would result from infinite precision.

One cannot expect the accuracy provided by an actual implementation to be high enough to guarantee the same result as that from infinite precision. (The highest available accuracy that is easily provided on a modern computer is 17 decimal places.)

The examples used here involved only the first two stages of a count. However, an important property of the Meek algorithm is that there is no accumulation of rounding error from one stage to the next, since the state is just the (discrete) record of those elected and eliminated. The weights are not really relevant since they only provide a starting point for the next iterative step.

One could gauge the impact of computational accuracy if one knew the rate at which ties arose which are not due to an algebraic tie. If such a computational tie arose with my database of around 370 elections, then it should be detected. In work which involved comparing two implementations of Meek(using all these 370 elections), it is likely that one implementation would report a tie-break when the other implementation did not. Such an occurrence did not arise.

Hence the overall conclusion is that the accuracy of the existing implementation of 64-bits is sufficient in practice, but not theoretically if the requirement is to produce the same result as that given by infinite precision.

### Reference

Up: Issue 6 Previous: Paper 3 Next: Paper 5