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.

**Plurality**. If some candidate*x*has strictly fewer votes in total than some other candidate*y*has first-preference votes, then*x*should not have greater probability than*y*of being elected.**Majority**. If more than half the voters put the same set of candidates (not necessarily in the same order) at the top of their preference listings, then at least one of those candidates should be elected.**Condorcet**. If there is a Condorcet winner (that is, a candidate who would beat every other candidate in pairwise comparisons), then the Condorcet winner should be elected.

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:

- (
**mono-raise**)*x*is raised on some ballots without changing the orders of the other candidates; - (
**mono-raise-delete**)*x*is raised on some ballots and all candidates now below*x*on those ballots are deleted from them; - (
**mono-raise-random**)*x*is raised on some ballots and the positions now below*x*on those ballots are filled (or left vacant) in any way that results in a valid ballot; - (
**mono-sub-plump**) some ballots that do not have*x*top are replaced by ballots that have*x*top with no second choice; - (
**mono-sub-top**) some ballots that do not have*x*top are replaced by ballots that have*x*top (and are otherwise arbitrary); - (
**mono-add-top**) further ballots are added that have*x*top (and are otherwise arbitrary); - (
**mono-remove-bottom**) some ballots are removed, all of which have*x*bottom, below all other candidates.

**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 45Point 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

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.

The thick box

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 27It is easy to see that this rule satisfies

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} 12My 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

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 8Sometimes several candidates can be eliminated at once. For example, in Election 4, the largest acquiescing coalition not containing all voters comprises 13 voters, for {

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 5It is not difficult to see that DAC satisfies

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 2Theorem 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

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.

- P C Fishburn, Condorcet social choice functions,
*SIAM Journal on Applied Mathematics*33 (1977), 469-489. - H Moulin, Condorcet's principle implies the no show
paradox,
*Journal of Economic Theory*45 (1988), 53-64. - D R Woodall, An impossibility theorem for electoral
systems,
*Discrete Mathematics*66 (1987), 209-211. - D R Woodall, Properties of preferential election rules,
*Voting matters*Issue 3 (1994), 8-15. - D R Woodall, Monotonic single-seat preferential election rules, submitted.