Up: Issue 6 Previous: Paper 3 Next: Paper 5

# Voting matters - Issue 6, May 1996

## Monotonicity and Single-Seat Election Rules

#### D R Woodall

Douglas Woodall is Reader in Pure Mathematics at Nottingham University.

### 1. Introduction

This article investigates the monotonicity properties of preferential election rules for filling a single seat. Section 2 lists the properties of interest, which form a subset of those introduced in Woodall. Section 3 describes several known election rules and two new ones (QLTD and DAC), whose properties are tabulated in Table 1. Section 4 describes a number of impossibility theorems, which are also represented symbolically in Table 1. These theorems say that certain combinations of properties cannot hold simultaneously, because the properties in question are mutually incompatible. In Section 5 I attempt to summarize the current state of knowledge and indicate what remains to be done.

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.

### 2. The properties

These properties were all introduced in Woodall, where they were discussed in more detail, and so I shall only state them briefly here. Of the seven global or absolute properties mentioned there, three are of interest to us now:
• 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.
Of these three properties, majority is by far and away the most important. Plurality is also important, but it is much less likely to be violated: every reasonable electoral system seems to satisfy it, whereas many systems proposed or actually used, such as first-past-the-post, point-scoring systems and approval voting, fail majority. Condorcet is a very attractive property, but, as we shall see in Section 4, it leads to problems with monotonicity. My aim is to find a system that satisfies majority and as many of the monotonicity properties as possible.

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.

### 3. Examples of election rules

First-Preference Plurality (FPP), or First-Past-the-Post, elects the candidate with the largest number of first-preference votes. This rule behaves extremely well with regard to all the local properties (although it satisfies later-no-harm only if second and subsequent preferences are ignored totally, and are not used to separate ties). However, it does not satisfy majority or Condorcet: in Election 1 below, FPP elects c, but majority requires that a or b should be elected, and a is the Condorcet winner.
```              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.

The thick box(note shown here: Majority to Mono-sub-top in table) delimits those properties that make sense even if truncated preference listings are not allowed. The top three properties are global while the others are local or relative.

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
def        27
```
```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
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.

### 4. Impossibility theorems

Of the three theorems summarized symbolically in Table 1, the one of greatest interest in the present context is Theorem 3. However, it is also the most difficult to prove, and so I shall discuss the two simpler theorems first.

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.

### 5. Conclusions

In attempting to find a single-seat preferential election rule that satisfies majority and is generally monotonic, I have come up with only one rule, DAC, that I would be prepared to recommend as preferable to the Alternative Vote, and then only when the count is carried out by computer. DAC is much more complicated than AV, and I have not given great thought to how one would implement it on a computer, but I do not think there would be any great difficulty unless the number of candidates was unrealistically large. DAC admittedly 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 monotonicity properties that AV does not possess, including the very strong participation property, and so I would regard it as preferable.

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.

### References

Up: Issue 6 Previous: Paper 3 Next: Paper 5