Voting matters - Issue 12, November 2000

STV with Elimination by Electability Scores

Simon Gazeley

1. Introduction

There are two problems with this extended form of Condorcet. One is that, when two or more seats are being contested, it is not practicable for any but the smallest elections: 15 candidates contesting 5 seats would give rise to 5005 contests; 27 candidates standing for the 15 seats on the Council of the Electoral Reform Society would give rise to 13,037,895 contests. Confronted with the result sheet of such an election, the electorate would find it difficult to understand how the winning candidates won and, perhaps more importantly, how the losing candidates lost. The other problem is that there could be more than one set of n candidates (whether n>1 or n=1) which gain the equal greatest number of victories. We would have to provide some kind of tie-breaker.

I believe that we can achieve the effect of Condorcet for one or more seats without these practical difficulties. Indeed, David Hill[1] has suggested one such scheme which selects sets of n candidates and tests each set against the other candidates one at a time. He admits that his scheme can elect a candidate other than the Condorcet winner in an election for one seat: I believe that the system propounded here will always elect the Condorcet winner, if there is one.

2. A Brief Digression on Proportionality

1. Increased support, for a candidate who would otherwise have been elected, should not prevent their election.
2. 1. Later preferences should not count against earlier preferences.
   2. Later preferences should not count towards earlier preferences.
3. If no second preferences are expressed, and there is a candidate who has more first-preference votes that any other candidate, then that candidate should be elected.
4. If the number of ballots marked X first, Y second, plus the number marked Y first, X second, is more than half the number of ballots, then at least one of X and Y should be elected.

If, for some whole numbers K and L satisfying 0 < K <= L, more than K Droop quotas of voters put the same L candidates (not necessarily in the same order) as the top L candidates in their preference listings, then at least K of those L candidates should be elected.

A voter who puts those L candidates (in any order) as the top candidates in order of preference is said to be 'strongly committed' to that set of L candidates. We will refer to a set of candidates to whom one set of voters is strongly committed as a 'DPC set'.

Under any of the rules in current use, the elimination of candidates in an STV election makes votes available to other candidates in the DPC sets to which they belong. No candidate who has a quota at the relevant stage is eliminated, and, with insignificant exceptions, eliminations are made one at a time. This ensures that the result of an STV count is consistent with the Droop Proportionality Criterion. STV with Elimination by Electability Scores (STV(EES)) shares this characteristic.

3. The aim of STV(EES)

On the other hand, the aim of STV(EES) is to identify those candidates who certainly should not be elected. It does so by taking account of all the preferences of every voter; in some circumstances, this feature will cause the system to fail on Woodall's second property. To identify candidates for elimination, it calculates 'electability scores' (see below) for the candidates: as new electability scores are calculated at successive stages, these form the basis for the elimination of candidates one by one until only sufficient are left to fill the available seats. These remaining candidates are elected.

STV(EES) differs in another way from conventional STV. As we are identifying candidates for elimination, not election, we do not have to use the Droop quota, and in fact its use can lead to perverse results. Instead, we calculate the 'threshold', which any of the other candidates must be able to attain in order to survive.

4. How STV(EES) works

A stage of STV(EES) culminates in the withdrawal, either temporary or permanent, of a candidate. It consists of two substages: the first establishes the threshold of votes which a candidate must be capable of achieving in order to survive; the second is to test whether the candidates who start with less than the threshold can in fact achieve it. At the end of the second sub-stage, one of these candidates is withdrawn from contention. This withdrawal takes one of two forms: the candidate is either 'eliminated', which means that (s)he takes no further part in the count, and is treated from that point on as though (s)he had withdrawn before it started; or is 'temporarily excluded', which means that (s)he is withdrawn for the time being, but comes back in after the next elimination.

Before explaining how to calculate electability scores, we must define the 'retention factor', which Meek calls the 'proportion retained'. In a Meek count, a point will be reached when a candidate has more than the quota. Clearly, that candidate should get less of the incoming votes in the next iteration of the count than were credited this time; and in successive iterations, the proportion of each incoming vote that stays with that candidate will diminish. The tendency will be for each new total of votes credited to that candidate to be closer to the quota than the last. To achieve this, an incoming whole vote or fraction of a vote is multiplied by an amount m where 0<m<1; the result of this multiplication is the fraction of that vote which is credited to that candidate. This amount m is known as the retention factor. Retention factors start with a value of 1.0, and those for the candidates with more than the quota are re-calculated at every iteration; thus retention factors will diminish as the count progresses. The Droop quota is also re-calculated at every iteration on the basis of the votes credited to candidates, ignoring those which have become non-transferable.

In an STV(EES) election, the first sub-stage of each stage is the calculation of the threshold. It does this by calculating the mean of the votes of the n candidates who have the most votes. Surpluses over the mean are transferred, then a new mean is calculated. This process of distributing the votes, calculating the mean, and transferring surpluses is repeated until the first n candidates have the same number of votes. The top n candidates are then known collectively as the 'probables', and their common total of votes is the threshold (T). The value of T remains fixed throughout the second substage, which is the calculation of the contending candidates' electability scores. Let C be the contending candidate whose electability score we are calculating (the 'candidate under test'), and let all the contending candidates other than C have a common retention factor of c. C's own retention factor remains at 1.0. In successive iterations, c and the retention factors of the probables are recalculated until the votes credited to all the probables are equal to the threshold and C either has the threshold or has less than the threshold while no other contending candidate has any votes at all. At this point, c is declared to be C's electability score. The electability scores of the remaining contending candidates are calculated in like fashion. The smaller C's electability score, the greater the number of votes that have had to be transferred from contending candidates other than C in order to ensure that C and the probables get their thresholds.

If the votes credited to the candidate under test and the contending candidates have a collective total of less than T, this indicates that the probables had a Droop quota of votes each when that candidate's electability score was being calculated. In that case, that contending candidate is eliminated, and all the non-eliminated candidates are re- classified as contending. On the other hand, if all the contending candidates' electability scores are at least 0.0, the one with the highest electability score is temporarily excluded, and only the existing probables are re-classified as contending. The new set of contending candidates proceeds to the next stage.

Stage succeeds stage until there are only n candidates who have not been eliminated, and those final candidates are elected. Note that at any stage when there are only n+1 'active' candidates (ie, candidates who have not been eliminated or temporarily excluded), one of them is certain to be eliminated. We therefore know that candidates will be eliminated until only n active candidates survive; thus an STV(EES) election must come to an end.

STV(EES) aims to identify a set of n candidates which can score at least as many victories in Condorcet mini-elections as every other. This means, for every eliminated candidate X, that there must be no set of n candidates including X which can score more victories in Condorcet mini-elections than every set of n not including X. We know at any given stage that every probable is better supported at that stage than X, and that every temporarily excluded candidate was better supported than X at the time of their temporary exclusion. Any DPC set to which X belongs has more members than can be elected by the number of voters that support it, and every other member of that DPC set is better supported than X. We can therefore be confident, though not certain, that there is no set of n candidates including X that can score more victories in Condorcet mini-elections than every set of n not including X. We can, however, state with certainty that in a count for one seat, the Condorcet winner (if there is one) will win. This is because, by definition, the Condorcet winner will win a contest with any one other candidate: and since no candidate is eliminated unless n other candidates have a Droop quota of votes each, the Condorcet winner cannot be eliminated.

5. An Illustration

ABCDEF 3670
CBAEFD 3436
DEFABC 1936
EFDBCA 1039
FDECAB 1919
      =====
      12000

B 0.1319
D 0.4125
E 0.2860
F 0.3478

This means that if D, E, and F had a common retention factor of 0.1319, A, B, and C would have 3436 votes each when surpluses have been transferred; if B, E, and F had a common retention factor of 0.4125, A, C, and D would have 3436 votes each when surpluses have been transferred, and so on. As D has the largest electability score at this stage, we act on the presumption that D has a better chance of being elected than B, E, or F, and so we ensure by temporary exclusion that D does not run the risk of being eliminated at substage 1.2. Note that this presumption is like the presumption of innocence in a criminal trial: the process tests it and may very well overturn it.

At substage 2.1, effective votes are:

ABCEF 3670
CBAEF 3436
EFABC 1936
EFBCA 1039
FECAB 1919
     =====
     12000

ABCF 3670
CBAF 3436
FABC 1936
FBCA 1039
FCAB 1919
    =====
    12000

ADEF 3670
AEFD 3436
DEFA 1936
EFDA 1039
FDEA 1919
    =====
    12000

ADF 3670
AFD 3436
DFA 1936
FDA 1039
FDA 1919
   =====
   12000

AEF 3670
AEF 3436
EFA 1936
EFA 1039
FEA 1919
   =====
   12000

6. Discussion

If there are too few DPC sets with sufficient support to 'soak up' all n seats being contested, can the system still produce a reasonable outcome? Let there be 4 candidates contesting 2 seats with votes:

ABCD 41
BCDA 30
CDAB 25
DABC 24
    ===
    120

Contest Winners

ABC AB
ABD AD
ACD AC
BCD BC

Under STV(EES), A and B are probables, and the initial threshold is 35.5. At stage 1, the electability scores of C and D are respectively 0.5625 and 0.54, so C is temporarily excluded. At stage 2, A and D win the ABD contest, and B is eliminated. At stage 3, A, C, and D remain in the contest, so A and C are elected.

How can the elimination of B and D be justified? Part of the answer is that D was in only one winning set in the exhaustive Condorcet count, whereas the other candidates were in at least two. But is there any objective reason why B rather than C should be eliminated? Here we must confess that the system may be said to be perverse: 95 voters prefer B to C, but only 25 prefer C to B. In defence of this outcome, we can say that set AC is one of the joint Condorcet winners, so it meets the aim of STV(EES); and that when a tie is the result of a paradox, it will be arbitrary to some extent. But I would still have preferred AB to be the winning set in this case.

I submit that STV(EES) will in most cases (perhaps all) give a result that is compatible with an exhaustive Condorcet count: and that even if it does not, the result will still be defensible.

Acknowledgement

References

1. I D Hill, Sequential STV, Voting matters, Issue 2 (1994), 5-7.
2. D R Woodall, An impossibility theorem for electoral systems, Discrete Mathematics, 66, (1987) 209-211.
3. D R Woodall, Properties of Preferential Election Rules, Voting matters, Issue 3 (1994), 8-15.
4. B L Meek, A New Approach to the Single Transferable Vote, Voting matters, Issue 1 (1994), 1-6. (Paper 1), 6-11 (Paper 2).

Annex - An Algorithm for STV(EES)

The suggested procedure is as follows:

Substage 1

1. Set every active candidate's retention factor to 1.0.
2. Repeat the following procedure until n candidates have T votes each.
   1. Distribute the votes in accordance with 'Distributing the Votes' below.
   2. Calculate T, the mean of the votes of the n candidates with most votes.
   3. For every candidate who has more than T votes, calculate a new retention factor by multiplying their present RF by T and dividing the result by the number of votes credited to that candidate.
3. If n candidates have T votes each, classify those n candidates as probables. If more than n candidates have T votes each, classify the first n in ranking order as probables.

Substage 2

1. Select each contending candidate in turn to be the 'candidate under test' and calculate their electability scores as follows:
   1. If T>V/(n+1), where V is the total of votes credited to all the candidates, mark the candidate under test for elimination. Otherwise, set the retention factor of the contending candidates, the candidate under test, and the probables, to 1.0, then repeat the following procedure until the probables and the candidate under test have T votes each, or until T>V/(n+1):
      • Distribute the votes in accordance with 'Distributing the Votes' below.
      • Recalculate the retention factor (RF) of any probable who has more than T votes by multiplying it by T and dividing the result by the number of votes credited to that candidate. Recalculate the common RF of the contending candidates by multiplying it by (V-(n+1)T)/C, where C is the total of votes credited to the contending candidates other than the candidate under test.
   2. If T=V/(n+1) and there are only n+1 active candidates. or if T>V/(n+1) mark the candidate under test for elimination. Otherwise, set the electability score of the candidate under test to the common RF of the other contending candidates.
2. Award the probables a notional electability score of 1.0, then rank the active candidates in their present order within descending order of electability score.
3. If any contending candidate is marked for elimination, eliminate all the marked candidates, reclassify all the non-eliminated candidates as contending, and rank them in random order. Otherwise, temporarily exclude the highest-ranked contending candidate, set that candidate's RF to 0.0, and reclassify only the probables as contending candidates.

Distributing the Votes

1. Multiply the value of the vote by the retention factor of the voter's first preference. Award that amount of the vote to that candidate.
2. If any of the vote is unallocated, multiply it by the retention factor of the candidate of the voter's next preference. Award that amount of the vote to that candidate. Repeat until none of the vote is left, or until the voter's preferences are exhausted.
3. If any of the vote is left when all the candidates have had their shares, put it to non-transferable.