Douglas Woodall is Reader in Pure Mathematics at Nottingham University.
Throughout this article I consider only the single-seat case. This does not reduce the force of the impossibility theorems in Section 4. We are interested in universal election rules, which will work for filling any number of seats. If certain properties are mutually incompatible even in the single-seat case - that is, there is not even a single-seat election rule with all these properties - then it is almost inconceivable that there will be an election rule with all these properties that works for any other number of seats, and there certainly cannot exist a universal election rule with them all. So, in practice, an impossibility theorem for single-seat election rules is as good as one that considers multi-seat elections as well. But in the case of the examples in Section 3, considering only single-seat elections is a real limitation, and I have resorted to it only because I have found the multi-seat case too hard to handle. There are many election rules that possess properties in the single-seat case that they do not possess in the multi-seat case, and there are many single-seat election rules that cannot apparently be extended to multi-seat elections in any sensible way, and so the multi-seat case is much harder to analyze.
I think the most important problems facing mathematicians who are interested in STV are, first, to discover which monotonicity properties are compatible with DPC (the Droop Proportionality Criterion)[4], or with majority (the property that DPC reduces to in single-seat elections-see Section 2 below); and then to find an election rule that satisfies DPC and as many monotonicity properties as possible. In the case of single-seat elections, I have found a rule (DAC) that satisfies majority and many monotonicity properties, which I would be prepared to recommend as preferable to the Alternative Vote (AV). Admittedly it fails to satisfy one important property of AV, that later preferences should not count against earlier preferences, but in return for this it gains five properties that AV does not possess. However, at the moment I have not been able to extend DAC in any sensible way to multi-seat elections, and I do not know whether this will prove to be possible, or whether it will be necessary to start afresh with a new idea.
Among the local or relative properties introduced in Woodall we shall consider seven of the nine versions of monotonicity, together with participation, later-no-help and later-no-harm. The remaining two versions of monotonicity, mono-append and mono-add-plump, are omitted because they hold for all the election rules discussed in Section 3 and do not feature in any of the impossibility theorems in Section 4.
Monotonicity. A candidate x should not be harmed if:
Participation. The addition of a further ballot should not, for any positive whole number k, reduce the probability that at least one candidate is elected out of the first k candidates listed on that ballot.
Later-no-help. Adding a later preference to a ballot should not help any candidate already listed.
Later-no-harm. Adding a later preference to a ballot should not harm any candidate already listed.
ab 30
Election 1: ba 25
c 45
Point Scoring (PS) methods are those where each candidate is given a
certain number of points for every voter who puts them first, a certain
(smaller) number for every voter who puts them second, and so on, and the
candidate with the largest total number of points is elected. These methods
have very similar properties to FPP, although later preferences can now
count against earlier preferences, so that later-no-harm fails, and
mono-raise-random and mono-sub-top also fail in most cases.
To see that PS systems do not satisfy majority or Condorcet,
suppose that just over half the voters list three candidates in the order
abc, and just under half list them in the order bca. Then
both majority and Condorcet require that a should be
elected, but any PS method will choose b.
The Alternative Vote (AV) was discussed at length in Woodall and so I shall content myself here with tabulating its properties in Table 1. Unlike FPP and PS, it satisfies the all-important majority property, but it behaves rather badly with respect to monotonicity.
There are many known election rules that satisfy Condorcet's principle; for example, nine such rules are discussed by Fishburn. In the present context (looking for a more monotonic substitute for AV) we are really only interested in rules that satisfy majority. Among such rules, the one with the largest number of other properties seems to be one that is not among the nine considered by Fishburn, namely to use a point scoring method to select a candidate from the Condorcet top tier. This method is described as C-PS in Table 1. It satisfies all three of the global properties that we are considering, but it behaves badly with respect to the local properties.
My first serious attempt to find a rule that would rival AV resulted in what I call Quota-Limited Trickle-Down (QLTD). Although this has now been superseded by DAC, I describe it here because it is simpler. One starts by crediting every candidate with all their first-preference votes. If no candidate exceeds the quota (of half the number of votes cast), then one gradually adds in the second-preference votes, then the third-preference votes, and so on, until some candidate reaches the quota. For example, it may be that if one credits every candidate with all their first-preference votes, all their second-preference votes and 0.53 times their number of third-preference votes, then exactly one candidate is brought up to the quota; that candidate is then declared elected.
abcdef 12
cabdef 11
Election 2: bcadef 10
def 27
It is easy to see that this rule satisfies majority. At first I
thought it satisfied all the most important monotonicity properties as well.
However, I now realize that it fails mono-add-top. This can be seen
from Election 2 above. Here the quota is 30, and if one gives every
candidate all their first and second-preference votes, plus 0.7 of their
third-preference votes, then a gets 30 votes, b 29.7, c
29.4, d 27, e 27 and f 18.9; thus a is elected.
However, if one adds six extra ballots marked ad, then the quota goes
up to 33, but now d reaches the quota on first and second preferences
alone: the count is d 33, a 29, b 22, c 21,
e 27 and f zero. In Election 2 itself, a is behind
d (by 23 to 27) on the basis of first and second-preference votes,
but a overtakes d when the third-preference votes are added
in. Adding six extra ad ballots increases a's and d's
first and second-preference votes by the same amount, and this causes
d to reach the quota: a would again overtake d if the
third-preference votes were added in, but this does not happen because the
election has already ended.
Election 3 Acquiescing Coalitions
ab 11 {a, b, c} 30 {c} 12
b 7 {b, c} 19 {a} 11
c 12 {a, b} 18 {b} 7
{a, c} 12
My most recent attempt to find a substitute for AV has resulted in what I
call the method of Descending Acquiescing Coalitions, or DAC, which is the
first election rule that I am really happy with. The coalition
acquiescing to any set of candidates comprises all voters who have not
indicated that they prefer any candidate not in that set to any candidate
in that set. For example, in Election 3 above, there are 19 voters who
acquiesce to b and c, namely, the 7 who voted b and
the 12 who voted c; none of them actually voted for both b
and c, but none of them have said that they prefer a to
either of these candidates, and so they are said to acquiesce to this set
of two candidates. Similarly, the 18 voters who acquiesce to a and
b comprise the 11 who voted ab and the 7 who voted b.
The 12 voters who acquiesce to a and c are exactly the same
as those who acquiesce to c, namely, the 12 c voters. And so
on.
In DAC, one first lists the sizes of all the acquiescing coalitions in decreasing order, as I have done above, and then works down the list from the top, eliminating candidates until only one is left. The largest acquiescing coalition always contains every voter, since every voter acquiesces to the set of all candidates; this does not help towards deciding who should be eliminated. In the above example, the next largest acquiescing coalition comprises 19 voters, for {b, c}; the fact that a is not included in this set means that a is the first candidate to be eliminated. The next acquiescing coalition comprises 18 voters, for {a, b}. Since c is not included in this set, c is next to be eliminated. This leaves only one candidate not eliminated, namely b, and so b is declared elected. (Note that AV would exclude b first and then elect c in this example.)
Election 4 Largest Acquiescing Coalitions
adcb 5 {a, b, c, d} 30 {a, c} 8
bcad 5 {a, b, c} 13 {b, c, d} 8
cabd 8 {d} 12 {b, d} 8
dabc 4 {a, d} 9 {c} 8
dbca 8
Sometimes several candidates can be eliminated at once. For example, in
Election 4, the largest acquiescing coalition not containing all voters
comprises 13 voters, for {a, b, c}; thus d is
the first candidate to be eliminated. The next largest acquiescing
coalition is for {d}, and so it appears that a, b and
c should all be eliminated at once, leaving no candidate remaining
uneliminated. In this case one simply ignores this coalition: it does not
help in distinguishing between the remaining three candidates. The next
coalition is for {a, d}, and this causes b and
c to be eliminated, so that a is elected.
Election 5 Largest Acquiescing Coalitions
acbd 6 {a, b, c, d} 25
adbc 3 {a, b, c} 14
adcb 3 {a} 12
bcad 4 {a, c} 10
cabd 4 {a, d} 6
dbca 5
It is not difficult to see that DAC satisfies majority, since if
more than half the voters put the same set of candidates (in various orders)
at the top of their preference listings, then every other candidate will be
eliminated before any candidate in that set. With slightly more difficulty,
it can be proved that DAC satisfies all the other properties ticked in
Table 1. However, it does not satisfy mono-raise-random or
mono-sub-top: if two of the four dabc ballots in Election 4
were replaced by acbd then c would be elected instead of
a. Also, it does not satisfy Condorcet: in Election 5, DAC
elects a, but c is the Condorcet winner. And it does not
satisfy later-no-harm: if the seven b voters in Election 3
had voted bc instead, then c would have been elected instead
of b. We shall see in the next section that there cannot exist any
election rule satisfying Condorcet or later-no-harm as well
as all the properties of DAC; but it is not clear whether there is any rule
that satisfies mono-raise-random or mono-sub-top as well as
everything that DAC does.
Theorem 1 says that if plurality and Condorcet hold then mono-add-top cannot hold; that is, there is no election rule that satisfies all three of these properties. This is easily seen by considering Election 3. Which candidate would such a rule elect? Since c has more first-preference votes than a has votes in total, a cannot be elected, by plurality. But adding two ba ballots would make a the Condorcet winner, and so b cannot be elected, by Condorcet and mono-add-top. And similarly c cannot be elected, because adding five cb ballots would make b the Condorcet winner. Thus, whichever candidate was elected, at least one of the three properties would be violated! (Of course, our rule could declare the result of Election 3 to be a tie; but this would lead to a contradiction in a similar way.)
It seems that most of the Condorcet-based properties discussed in the Social Choice literature would in fact elect a in Election 3, and so violate plurality (whereas AV elects c and DAC elects b). How seriously one regards the failure of plurality depends on how one interprets truncated preference listings, and that in turn may depend on the rubric on the ballot paper. If the 12 c voters are merely expressing indifference between a and b and not hostility to them, and so can be treated in exactly the same way as if half of them voted cab and half voted cba, then the violation is not too serious. But if, by plumping for c, these voters are not just saying that they prefer c to a, but that they want c and definitely do not want a (or b), and if the seven b voters also definitely do not want a (or c), then it is clear that c has more support than a and so a should not be elected.
abc 3 acb 2
Election 6: bca 3 bac 2
cab 3 cba 2
Theorem 2 says that if an election rule satisfies Condorcet's principle,
then it cannot possess any of the seven properties that are crossed in the
column headed 2 in Table 1. This is a lot to prove. Fortunately most of it
can be proved by considering variants of Election 6 above. The only bit
that cannot is the incompatibility of Condorcet with
participation; this is proved by Moulin, and I shall not
attempt to reproduce his proof here. The following proof of the rest of
Theorem 2 invokes the axioms of symmetry and discrimination, for a precise
statement of which see Woodall.
So suppose we have an election rule that satisfies Condorcet. By symmetry, the result of this rule applied to Election 6 above must be a 3-way tie. But by the axiom of discrimination, there must be a profile P very close to the one in Election 6 (in terms of the proportions of ballots of each type) that does not yield a tie. So our election rule, applied to profile P, elects one candidate unambiguously; and there is no loss of generality in supposing that this candidate is a. However, there are ways of modifying the profile P so that c becomes the Condorcet winner, so that our election rule must then elect c instead of a. This happens, for example, if all the bac ballots are replaced by a; and the fact that this causes c to be elected instead of a means that our election rule does not satisfy mono-raise-random, mono-raise-delete, mono-sub-top or mono-sub-plump. It also happens if all the abc ballots are replaced by a, and this shows that our election rule does not satisfy later-no-help.
To prove that our election rule does not satisfy later-no-harm, it is necessary to consider a slight modification of the profile in Election 6, in which the second and third choices are deleted from all the abc, bca and cab ballots. Again, our election rule, applied to this profile, must result in a 3-way tie. But again, there must be a profile P' very close to this (in terms of the proportions of ballots of each type) that does not give rise to a tie, and we may suppose that our election rule elects a when applied to profile P'. But if we replace the a ballots in P' by abc, then b becomes the Condorcet winner, and so must be elected by Condorcet's principle; and this shows that our election rule does not satisfy later-no-harm.
Together with the result of Moulin already mentioned, this completes the proof of Theorem 2, that an election rule that satisfies Condorcet cannot satisfy any of the seven properties crossed in the column headed 2 in Table 1.
Theorem 3 is a result that looks superficially similar to Theorem 2, and the proof is similar in character but much harder. The theorem says that if an election rule satisfies majority, later-no-help and later-no-harm then it cannot possess any of the seven properties crossed in the column headed 3 in Table 1. This is a substantial improvement on the result sometimes known as "Woodall's impossibility theorem", which asserts that there is no election rule that satisfies plurality, majority, later-no-help, later-no-harm and mono-sub-top. In obtaining the improvement, I have needed to adopt an axiom of discrimination that is somewhat stronger than the one stated in Woodall, although one that must surely still hold for any real election rule. I am also grateful for help from my research student, Ben Tarlow.
Because the proofs of the different parts of Theorem 3 are quite complicated, I shall just sketch the proof of the easiest part, which is that there is no election rule that satisfies majority, later-no-help, later-no-harm and mono-sub-plump (or mono-sub-top). Suppose, on the contrary, that we have a rule that satisfies these four properties. The first part of the proof is to show that it must elect a in election A1 and c in election A3 in the above table. This is not too difficult to prove, using symmetry and mono-sub-top, provided that neither of these elections results in a tie. However, although it may seem highly implausible that either of them should yield a tie, I cannot see any way of proving that this is impossible. Instead, I have used the strong form of the axiom of discrimination in order to show that, if it does happen, then one can vary the proportions 0.34, 0.33, 0.3 and 0.36 in these profiles by very small amounts in a consistent way so as to obtain very similar profiles in which it does not happen.
The rest of the proof is much easier to explain. Let us write X -> x to mean that x is definitely elected in Election X (that is, with probability 1), and X /-> x to mean that x is definitely not elected in Election X (that is, x does not even tie for election in Election X ). Also => is used to mean "implies that". Therefore
A1 -> a => A2 -> a by later-no-harm,
A2 -> a => A2 /-> b (clearly),
A2 /-> b => A4 /-> b by mono-sub-plump,
A3 -> c => A3 /-> a (clearly),
A3 /-> a => A4 /-> a by later-no-help,
A4 /-> a and A4 /-> b => A4 -> c,
A4 -> c => A5 -> c by mono-sub-plump,
A5 -> c => A5 /-> b (clearly),
A5 /-> b => A6 /-> b by later-no-help.
However, majority requires that A6 should result in the election of either a or b, and the axiom of symmetry therefore requires that a and b should tie for election in A6, each with probability ½. This contradiction shows that there can be no election rule satisfying the four properties described.
The details of this proof, and the proof of the rest of Theorem 3, can be found in Woodall, which is not yet published but is available from the author at the Department of Mathematics, University Park, Nottingham, NG7 2RD, email drw@maths.nott.ac.uk.
However, DAC only works for filling a single seat, and I have not so far found any sensible way of extending it to multi-seat elections. The major remaining problem seems to me to be to find a multi-seat preferential election rule that satisfies the Droop Proportionality Criterion and is generally monotonic. It is not clear whether one can do this by modifying DAC, or whether it will be necessary to start afresh with a new idea.
From the mathematical point of view, there is still a great deal of work to be done on single-seat elections. The general problem is to determine which sets of the properties listed in Table 1 are mutually compatible. The examples discussed in Section 3 and the impossibility theorems in Section 4 give some answers. For example, Theorems 2 and 3 show that both FPP and AV possess maximal compatible sets of these properties, and that moreover these are the only two maximal compatible sets of properties that include both later-no-help and later-no-harm. Surprisingly, I have not been able to prove that the properties possessed by DAC form a maximal compatible set; Theorems 2 and 3 show that one cannot add either Condorcet or later-no-harm to these properties, but I cannot prove that one cannot add mono-raise-random or mono-sub-top (although this seems unlikely, since these last two are extremely strong properties, which hardly any election rules seem to possess). Another problem of this type is to determine whether there is any rule that satisfies majority, Condorcet and either mono-add-top or mono-remove-bottom. While problems of this type may seem to have little direct relevance to STV, the ideas generated by attempts to solve them may turn out to be more relevant than at first appears, and in any case we cannot afford to know less about such questions than our opponents do.