Brian Wichmann is the Editor of *Voting matters* and a visiting
professor of The Open University.

For an STV algorithm, we could have too much stability in that part of the ballot papers are simply ignored - for instance, by only using the first preference. On the other hand, we could have an algorithm which lacks stability in vital respects by changing the result for inconsequential changes to a ballot paper.

One change made to a ballot paper can be regarded as *small*, due to
the nature of the preferential system. Since the usual means of balloting
does not provide for the voter to give equal preference, when the ballot
paper records ABC, this might be because A and B were regarded as equal, but
the voter specified A first arbitrarily. Hence the voter could equally have
written BAC instead. Hence given the ballot ABC, the voter's true intentions
could perhaps have been expressed as BAC or ACB. In general, given *n*
preferences, *n-*1 ballot papers constructed by interchanging
neighbouring preferences could be regarded as *small* differences.

Now consider two algorithms for STV which have broadly similar properties (as do all serious contenders). Figures 1 and 2 represent graphically these two algorithms.

Figure 1

Figure 1 represents a stable algorithm since small changes are unlikely to change the result of an election, while Figure 2 represents an unstable algorithm. If we were operating in two dimensions, then the property of stability could be measured rather like the game of shove-halfpenny: one would measure the probability that a small circle placed at random on the figure crossed one of the dividing lines.

Figure 2

In the case of STV algorithms, we do not have a simple two-dimensional system, and hence the figures are a crude diagrammatic representation. To measure the probabilities we must conduct a suitably controlled experiment. Fortunately, we can use a computer to aid this process so that we can perform the equivalent of shove-halfpenny sufficiently often to obtain results which are likely to be meaningful.

We select an actual election for which the ballot papers are available. We
also choose a number, about 20, which is the number of ballot papers from
the full set that is to be selected at random. (We return to the choice of
this number *n* later.)

From each real election, we derive 100 mini-elections by randomly selecting
*n* ballot papers. The experimental method is to analyse the effect of
making small changes to these mini-elections. The analysis is as follows.
Firstly, we compute the result of the two algorithms from the mini-election.
(The result need not be the same for the two algorithms, nor the same as for
the full election.) We now consider all the possible similar mini-elections
derived by making one small change to one of the ballot papers. (This is
potentially hundreds of elections - hence the computer.) This particular
mini-election is on the edge if a specific criterion is met, say at least
one of the small changes produces a different result.

The choice of *n* is important. If *n* is very small (say 1), then
it is clear that the mini-election will not be representative of the real
election. On the other hand, if *n* is large (say the full election),
then the computation of the 'edge' becomes too large, and also the number of
possible mini-elections becomes too small (in this case only 1). Care must
be taken over the specific criterion for being on the edge. If one takes
something like the ERS council elections (i.e., several posts to fill with
no parties, so that small changes are likely to make a difference to the
outcome), with the criterion that *any* small change resulting in a
difference implies being on the edge, then there is a danger that *all*
mini-elections are on the edge!

For the 100 random mini-elections we perform a different analysis in each of the three experiments given here. If one could assume statistical independence, then it would be a simple matter to undertake a chi-squared test to see if the result is significant. Unfortunately, we do not have elections with a large enough number of ballot papers to ensure the independence, and therefore we must be content with a non-statistical treatment.

The number of changes to those elected for one small change is usually 0 (no
change), but is sometimes 1, rarely 2 and very rarely 3. Hence for each
ballot paper in the mini-election, *n*-1 integers are output,
representing the number of changes arising from each of the *n*-1
possible interchanges of adjacent preferences, where *n* is the number
of preferences marked on the ballot paper. This implies that the output is
of similar length to the input - an important consideration, since if
complete results were printed for each election result computed, hundreds of
pages of material would be produced.

The analysis is most easily seen by considering an example. A mini-election from election R038 is as follows:

17 5 1 11 9 10 0 1 10 17 5 9 11 16 0 1 6 16 2 1 14 17 10 9 11 5 8 4 12 13 15 0 1 4 8 12 15 13 0 1 17 5 11 1 16 10 2 0 1 5 9 10 11 17 0 1 3 7 9 14 17 0 ... 1 8 10 13 11 17 0 1 9 5 6 17 0 1 11 10 5 17 9 0 1 6 4 15 14 16 8 1 0 1 6 14 16 1 2 4 13 12 8 15 0 1 13 4 15 12 8 0 0 "A.1 " "B.2 " "C.3 " "D.4 " "E.5 " "F.6 " "G.7 " "H.8 " "I.9 " "J.10 " "K.11 " "L.12 " "M.13 " "N.14 " "O.15 " "P.16 " "Q.17 " "1R038: H3H "The above data is for an election with 17 candidates for 5 seats, in which the first ballot paper selects candidate 11 (K) as the first preference, then 9 and lastly 10. The names of the candidates are the letters A-Q, a convention used throughout.

The program computes the effect of making all possible interchanges of adjacent preferences, which for Meek gives:

v1 +F-L-B-O-P-H-G-N-E-M-C+I+Q-K+J+A-D 68 0 1 1 1 2 1 1 1 1 1 1 0 0 2 1 1 0 0 1 0 0 1 1 ... 2 1 1 1 0 1 0 1 1 0 0 1 1 0 0 0 0 0 2 1 0 1 1 1 0 2 0 0 1 1 0 1 0 0 1 1 1 1 0 1 1 0 1 mThe first line gives the result (with Meek) for this mini-election, where +F-L means F is elected and L is excluded, etc. (The v1 and 68 are not relevant.) Then, starting with the last ballot paper and working back towards the beginning, the number of differences to the result is printed for each possible interchange. Hence the last ballot paper has four possible interchanges, the first one giving no difference, but the last three each making a single difference. So in this case, interchanging the first two preferences makes no difference, but interchanging the 2nd and 3rd preferences does change the result by one candidate. The 'm' relates to the third experiment and is explained later.

One other program is needed which selects *n* ballot papers at random
from a real election, and repeats this 100 times. This program is fast and
straightforward.

For the main election data, six real elections have been chosen from the
data already available (see *Voting matters*, Issue 2). The statistics
from these elections are as follows:

Identifier Papers Candidates SeatsUnfortunately, none of the elections in the data base are from elections involving parties, and so such elections could not be selected for this study.nR006 239 9 2 20 R008 261 10 3 25 R010 270 9 5 27 R017 479 8 1 15 R033 196 14 7 25 R038 177 17 5 20

We can now summarise the results obtained by example. For election R017, 100 mini-elections are computed by selecting 15 ballot papers from the actual 479. For each of these mini-elections, we compute what difference (if any) would be made by a single transposition of a preference. This is repeated for each possible transposition, which in this case, involves the analysis of 4585 elections!

Criterion: Some change for any transposition

Election ERS edge Meek edge R006 74 65 R008 80 74 R010 95 87 R017 69 74 R033 99 95 R038 100 100This table means, for instance, that for the 100 mini-elections derived from R006, 74 are on the 'edge' for ERS and 65 for Meek - which implies that there were 26 or 35 elections for which no change was made by any transpositions. Hence a very high proportion of the mini-elections are on the 'edge', over three quarters in almost all cases. However, even the most optimistic assumption shows that there is not much difference between the two algorithms.

We now change the criterion for being on the edge so that a lower proportion are on the edge.

Criterion: More than three transpositions make a change

Election ERS edge Meek edge R006 41 38 R008 55 46 R010 76 57 R017 32 49 R033 91 75 R038 94 91We again conclude that there is not much difference between the two algorithms.

We need to look at aspects other than the actual size of the edge to see significant differences.

Given a mini-election which is on the edge, then we know at least some
transpositions of the preferences will change the result. It is therefore
natural to ask which specific transpositions can change the result. Clearly,
it is more likely that transposing the first two preferences will alter the
result, but what about the subsequent transpositions? We therefore analyse
the number of times a transposition makes a change, against the position of
the transposition (p*i*).

In the table above, for each of the six elections, the number of times a transposition makes (at least) one change to the result is tabulated against the preference position for all the 100 mini-elections. The difference between ERS and Meek is now obvious. The number of changes for the first preference between the two algorithms is similar and is surely not significant. However, in all subsequent preferences, many more changes arise from Meek than from ERS.Combined resultsp1 p2 p3 p4 p5 p6 p7 p8 p9 p10 p11 p12R006ERS 283 31 14 6 4 0... Meek 310 147 61 39 23 16 14 0...R008ERS 452 56 11 8 5 4 0 1 3 0... Meek 393 161 70 42 25 13 12 11 0...R010ERS 668 173 36 21 9 4 2 0... Meek 423 174 82 34 21 18 13 0...R017ERS 214 27 4 5 2 1 0... Meek 279 210 123 119 104 94 0...R033ERS 979 227 78 31 17 8 3 2 1 0 0 1 Meek1876 392 225 144 117 91 69 61 57 41 41 34 37R038ERS 734 203 44 31 17 6 3 2 0 1 1 0 Meek 723 502 376 346 157 138 107 97 91 44 36 33

In examining the subsequent preferences, there is no natural scale to work
to, since a change in preference *n* is more significant if there are
*n* candidates than 2*n* candidates. The number of seats is also
relevant to this scale. Hence in analysing the table above, both the number
of candidates and seats must be considered.

We can add up the results from each election for those positions beyond the
number of seats (*s*) for each election, giving the following results:

PositionHence we conclude that transposing preferences beyond the number of seats has virtually no effect with ERS as compared with Meek.s+1s+2s+3 >s+3 ERS 61 21 15 11 Meek 530 364 293 596 ratio 8.7 17 19 54

We can now compare the violation rate for ERS and Meek, which is as follows:

Election ERS violations Meek violations R006 0 32 R008 2 29 R010 5 8 R017 5 78 R033 5 70 R038 0 141Hence there is no question that Meek violates

- There is no evidence that the ERS and Meek algorithms are any different with respect to the size of the boundary between the election of different candidates.
- Making small changes by transposing preferences later than the number of seats makes virtually no difference with ERS but a substantial difference with the Meek algorithm.
- Meek violates
**mono-raise**much more than ERS.

It appears that the results presented here have some limitations. Firstly, the mini-elections necessarily have a small number of ballot papers and so the results need not apply to larger elections. Secondly, a consequence of the small number of ballot papers is that in many cases, random choices are made by both the ERS and Meek algorithms.