Up: Issue 15 Previous: Paper 3

Voting matters - Issue 15, June 2002

Sequential STV - a new version

I.D. Hill and Simon Gazeley

In Issue 2 of Voting matters, a system was reported called Sequential STV [1], designed to overcome, at least to some extent, the problem of premature exclusion of a candidate, which occurs when the one who has the fewest votes at the time is excluded, though due to receive many transfers later if only that exclusion had not taken place. That system has now been improved and we report here on the new version. One particular result of the improvement is that, in the case of a single seat, it is now certain to find the Condorcet winner if there is one.

The aim is to find a set of candidates of size n, where n is the number of seats to be filled, such that any set of n+1 candidates consisting of those n and 1 more, will result in the election of those n when an STV election is performed. When n=1 this reduces, of course, to the Condorcet rule. In a small election, or when n=1, it would be relatively easy and quick to do a complete analysis to find if there is such a set. The challenge is to find a way of doing so that will work in a reasonable time in large elections, where such a complete analysis would be impracticable. We recognise that the meanings of 'a reasonable time' and 'impracticable' are open to dispute, and that what is practicable will change as computers continue to get faster.

In the old version of Sequential STV, an initial STV count divided the candidates into probables and others, but the others were regarded as 'in a heap' and all of equal status. Consequently, if a challenger was successful, it would have been contrary to the axioms of anonymity and neutrality[2] to make a change of probables until all the others had been tested too, and that could lead to more than one challenger in the next main stage. In the new version the others are not put in a heap but in a queue, where the order depends upon the voting pattern. It is then fair to implement any change of probables at once, and the division of the method into main stages and sub-stages is no longer necessary.

How it works – the easy part

An initial STV count is made but instead of dividing into those elected and not elected, it classifies those who would have been elected as probables, and puts the others into a queue, in the reverse order of their exclusion in that initial count, except that the runner-up is moved to last place as it is already known that an initial challenge by that candidate will not succeed. Having found the probables and the order of the queue, further rounds each consist of n+1 candidates, the n probables plus the head of the queue as challenger, for the n seats.

It should be noted that, apart from the initial count, which is only to get things started, all counts are of n+1 candidates for n seats, so the 'exclude the lowest' rule, which is the least satisfactory feature of STV, is not used.

If the challenger is not successful, the probables are unchanged for the next round and the challenger moves to the end of the queue, but a successful challenger at once becomes a probable, while the beaten candidate is put to the end of the queue. The queue therefore changes its order as time goes on but its order always depends upon the votes.

The reordering of the queue during the count, by putting any losing candidate to the end of the queue, is to make sure that it cannot ever get into a state where, say, a set X are probables, A, B and C are all near the top of the queue and X+A beats X+B beats X+C beats X+A, while D is further down and X+D has not been tested. Putting losing candidates to the end means that D must head the queue at some point before A, B and C come round again.

This continues until either we get a complete run through the queue without any challenger succeeding, in which case we have a solution of the type that we are seeking, or we fall into a Condorcet-style loop. In the latter case, we have to enter the more difficult part, set out below, but it should be emphasised that in real elections, as distinct from specially devised test cases, that rarely happens.

How it works – the more difficult part

To decide that a loop has been found, a set that has been seen before must recur as the probables. If the queue is in the same order as before then a loop is certain and action must be taken at once. If, however, a set recurs but the queue is in a different order, it is conceivable though unlikely that something different, that breaks the loop, could happen. So, in that case, a second chance is given and the counting continues but, if the same set recurs yet again, a loop is assumed and action taken.

In either event the action is the same, to exclude all candidates who have never been a probable since the last restart (which means the start where no actual restart has occurred) and then restart from the beginning except that the existing probables and queue are retained instead of the initial STV count.

If there is no candidate who can be excluded, then a special procedure is used, in which any candidate who has always been a probable since the last restart is classified as a certainty and any other remaining candidate as a contender. From each possible set of n+1 candidates that includes all the certainties, an election for n seats is conducted. Since, at this point, most of the original candidates will be either excluded or certainties, there is no need to fear an astronomical number of tests needing to be made.

At the end of each test, the one candidate who has not reached the quota is assigned a fractional value calculated by dividing that candidate's votes by the quota. When all the tests have been done, the average of these fractions is calculated for each candidate. Additionally candidates are awarded one point for each contest in which they did reach the quota. It is these complete points that mainly decide, the average fraction being really only a tie-breaker.

The contender with the highest score is then reclassified as a certainty and, if the number of certainties is less than the number of seats, the special procedure is repeated with one contender fewer and one seat fewer to fill.

While this process may look complicated, it should be remembered that, on most occasions, only the part called 'the easy part' above is used, while the complications are used to sort out a Condorcet paradox if it occurs.

Programming

Where loops occur it will often be found that a particular set of candidates is being tested more than once. Storing results and accessing them as necessary would obviously be much quicker than repeating the same STV count many times. However, since most voting patterns do not have such loops, such storing of results would usually be unproductive extra work. For the present, the system has been programmed with repetition rather than storing.

The name 'Sequential STV'

From now on the name Sequential STV will be used to mean this new version.

A random version

The initial STV count, to choose the initial probables and to determine the initial order of the queue, turns out to be not very important, in that an alternative version that selects the initial probables at random, and orders the initial queue at random, nearly always reaches the same eventual answer. It is fun to watch it getting from an initial nonsense selection to end up at the correct solution, but this version should not be used in practice because of rare cases where it can get a different result from that given by starting with an STV count and, where this is so, we suspect that it would usually be a less good result.

An example of such a rare case has been given previously[3] with a fictitious set of votes, having 4 candidates for 2 places, in which testing ABC elects AB and testing ABD elects AB, yet testing ACD elects CD and testing BCD elects CD. In that example, Sequential STV elects AB (which is, in fact, the better choice) whereas the random version has a 50-50 chance of finding either AB or CD. Such an example seems unlikely ever to occur in reality but the fact that it is possible means that it is better to guard against it by not using the random version.

Examples

With 5 candidates for 2 seats, consider the voting pattern
        104 ABCD
        103 BCDA
        102 CDBA
        101 DBCA
          3 EABCD
          3 EBCDA
          3 ECDBA
          3 EDCBA
Plain STV elects BC. Sequential STV chooses BC as probables, then tests BCD, BCE and BCA in that order. BC win each time and are elected.

Suppose, however, that the voters for A, B, C and D had all put in E as second preference to give (the example used in reference 1).

        104 AEBCD
        103 BECDA
        102 CEDBA
        101 DEBCA
          3 EABCD
          3 EBCDA
          3 ECDBA
          3 EDCBA
This evidently makes E a very much stronger candidate, for if any one of A, B, C or D had not stood, E would have been the first elected, but plain STV takes no notice, electing BC just as before. Sequential STV chooses BC as probables but then tests BCD, where BC stay as probables and D goes to the end of the queue, followed by BCE where BE become the new probables and C goes to the end of the queue. It then tests BEA and BED, BE winning each time. There is no need to test BEC again as that result is already known, so BE are elected.

Real voting patterns

In 43 real elections held on file, the sequential method merely confirmed the original result in 38 of them, and replaced just 1 candidate in 3 more of them. In only 2 cases were loops found, making it necessary to do more than the easy part of the method.

Timings

Some timings were made on an 11-year old PC with a 386 chip. In a real election with 10 candidates for 6 seats and 841 voters, simple STV took 11 seconds. Sequential STV made no change in those elected and took 23 seconds.

In a much more difficult case with 30 candidates for 15 seats and 563 voters, simple STV took 1 minute 6 seconds. Sequential STV found 1 candidate to be definitely replaced and 3 others who were in a loop for the final seat. It took a total of 18 minutes 30 seconds.

Should it be used?

With this new version, should it be recommended for practical use? That depends upon whether the user is willing to abandon the principle that it should be impossible for a voter to upset earlier preferences by using later preferences. Many people regard that principle as very important, but reducing the frequency of premature exclusions is important too. We know that it is impossible to devise a perfect scheme, and it is all a question of which faults are the most important to avoid.

In considering this, we need to take into account, among other things, that the true aim of an election should not be solely to match seats as well as possible to votes, but to match seats to the voters' wishes. Since we do not know the wishes we must use the votes as a substitute, but that makes it essential that the votes should match the wishes as far as possible. That, in turn, makes it desirable that the voters should not be tempted to vote tactically.

They would not be so tempted if they felt confident that later preferences were as likely to help earlier ones as to harm them, and if they could not predict the effect one way or the other. At present, we see no reason to doubt that these requirements are met.

All things considered, we believe that Sequential STV is worthy of serious consideration.

Comparison with STV(EES) and with CPO-STV?

STV(EES) [4] was designed to meet much the same aims as Sequential STV, and also has the same disadvantage that later preferences can upset earlier ones. A comparison of the two would be interesting. As at present defined, however, STV(EES) is so slow that a comparison is not easy. For an electoral method to be slow should not be considered too much of a disadvantage for real elections if it can be shown to get better results, but it is certainly a disadvantage for research purposes where a large number of counts of different data may be required within a reasonable time.

Using the examples above, STV(EES) elects BC from the first but BE from the second, just as Sequential STV does.

In the example given in section 6 of reference [4], AC were elected by STV(EES), which was not wrong as there was a paradox in the votes, but the paper admitted that 'I would still have preferred AB to be the winning set in this case', so it may be worth noting that Sequential STV does indeed elect AB.

CPO-STV [5][6] was designed to search for an outcome that is globally optimum rather than merely locally stable. Again a comparison would be interesting.

Acknowledgements

We are grateful to Douglas Woodall and Nic Tideman for helpful comments on earlier versions of this paper.

References

  1. I.D. Hill, Sequential STV. Voting matters, Issue 2, 5-7. 1994.
  2. D.R. Woodall, Properties of preferential election rules. Voting matters, Issue 3, 8-15. 1994.
  3. I.D. Hill, Trying to find a winning set of candidates. Voting matters, Issue 4, 3. 1995.
  4. Simon Gazeley, STV with elimination by electability scores. Voting matters, Issue 12, 9-13. 2000.
  5. T. Nicolaus Tideman, The single transferable vote. Journal of Economic Perspectives, 9, 27-38. 1995.
  6. T. Nicolaus Tideman, Better voting methods through technology: the refinement-manageability trade-off in the single transferable vote. Public Choice, 103, 13-34. 2000.

Up: Issue 15 Previous: Paper 3