Up: Issue 3 Previous: Paper 4

Voting matters - Issue 3, December 1994

Properties of Preferential Election Rules

D R Woodall

Douglas Woodall is Reader in Pure Mathematics at Nottingham University.

In this article, he argues that more attention should be paid to properties of electoral systems, and less to procedures. He lists many properties that a preferential election rule may or may not have, and discusses them with reference to STV.

1. Introduction

I have often been struck-and never more than in the last year-by how much the types of argument used by the supporters of the Single Transferable Vote (STV) differ from those used by its opponents. When it comes to the details of the count, the supporters of STV almost invariably try to defend its procedures directly, on the grounds that they follow certain principles, or that they do with each vote exactly what the voter would want done with it, if the voter were able to be present at the count and to express an opinion. Unfortunately, there is no guarantee that adopting sensible procedures, at each stage of the count, will lead to a system with sensible properties, and the opponents of STV often emphasize its less desirable properties. In particular, it is now well known that STV is not monotonic: that is, that increased support, for a candidate who would otherwise have been elected, can prevent that candidate from being elected. It was ostensibly because of this and related anomalies that the Plant Report rejected STV.

Properties of electoral systems can be thought of as "performance indicators", and like any other performance indicators they need to be used with care. If one chooses a set of performance indicators in advance, it may well be possible to manufacture a high score on those indicators in an artificial way, which does not represent good performance in any real sense. Nevertheless, it seems to me that the Electoral Reform Society needs to pay more attention to properties if it is not to be sidelined in the electoral debate. In particular, since different desirable properties often turn out to be mutually incompatible, it is important to discover which sets of properties can hold simultaneously in an electoral system. Only then will it be possible to decide whether there are electoral systems that retain what is essential in STV while avoiding some of the pitfalls.

The purpose of this article is to introduce a long list of technical properties that an election rule may or may not have, to invent snappy descriptive names for them all, and to discuss them with special reference to STV. Except where otherwise indicated, statements made about STV apply equally well to the Newland-Britton and Meek versions of STV. In a later article I hope to address the question of monotonicity in more detail.

2. Notation and terminology

As is usual in the Social Choice literature, I shall use lower-case letters a, b, c,... to denote candidates (or choices). Each voter casts a ballot containing a preference listing of the candidates, which is written as (for example) abc, to denote that the voter places a first, b second and c third, with no fourth choice being expressed. A preference listing is complete if all candidates are included in it and truncated if some are left out. (A preference listing that leaves out just one candidate will be treated by most election rules, including STV, as if it were complete; but one should not call it complete, since some election rules may not treat it as such.) A profile is a set of preference listings, such as might represent the ballots cast in an election. Profiles may be represented in either of the forms shown for Elections 1 and 2 below, indicating either the proportion, or the absolute number, of ballots of each type cast.

The term outcome will be used in the sense of "possible outcome" (assuming there are no ties). Thus in an election to fill two seats from four candidates a, b, c, d, there are six outcomes, corresponding to the six possible ways of choosing the two candidates to be elected: {a, b}, {a, c}, {a, d}, {b, c}, {b, d} and {c, d}.

Election 1        Election 2
  (1 seat)          (2 seats)
ab   0.17         a   9    ea   4
ac   0.16         b   9    eb   4
bac  0.33         c  10    fc   1
cb   0.34         d  10    fd   1
                           fe   6
An election rule is usually thought of as a method that, given a profile, chooses a corresponding outcome-or, in the event of a tie, chooses two or more outcomes, one of which must then be selected in some other way (such as by tossing a coin). However, this description is not quite adequate to deal with the complexities of ties. Consider Election 1 above, with the votes counted by STV (or, rather, by the Alternative Vote (AV), which is the rule to which STV reduces in a single-seat election). No candidate reaches the quota of 0.5, and there is an initial tie for exclusion between a and b. If b is excluded then a is immediately elected, whereas if a is excluded then b and c tie for election. Thus a is elected with probability ½, and b and c are elected with probability ¼ each.

A similar situation arises in Election 2, again under STV. There are 54 votes cast, so the quota is 18, and there is an initial tie for exclusion between e and f. If e is excluded then f, c and d must also be excluded, and a and b are elected; whereas, if f is excluded, then a and b must also be excluded, and then e is elected and c and d tie for second place. Thus the outcome {a, b} is chosen with probability 1/4, and the outcomes {c, e} and {d, e} are chosen with probability ½ each.

Because of examples like these, I define a (preferential) election rule to be a procedure that, given a profile, associates a corresponding non-negative probability with each outcome, in such a way that the probabilities associated with all possible outcomes add up to 1. The "normal" situation is that all the outcomes are given probability 0 except for one, which has probability 1 (meaning that that outcome is chosen unequivocally). If anything else happens, then we say that the result is a tie between all the outcomes that have non-zero probability.

3. Axioms

There are so many properties that an election rule may have, that it is useful to categorize them in some way. Four in particular seem sufficiently basic to deserve to be called axioms. The first is more or less implicit in the above definition of an election rule; but it has a name, and so for completeness I include it here.

Anonymity. The result should depend only on the number of ballots of each possible type in the profile (and not, for example, on the order in which they are cast, or on extraneous information such as the heights of the candidates).

Neutrality. If some permutation is applied to the names of all the candidates on all the ballots in the profile, then the same permutation should be applied to the result. For example, since STV is neutral, if a is replaced by c and c by a on every ballot in Election 2 above, then STV would choose {b, c} with probability ½ and {a, e} and {d, e} with probability 1/4 each. One consequence of neutrality is that a tie in a single-seat election cannot be resolved simply by electing the first in alphabetical order among the tied candidates.

A rule that is both anonymous and neutral is called symmetric.

Homogeneity. The result should depend only on the proportion of ballots of each possible type. In particular, if every ballot is replicated the same number of times, then the result should not change. It is this property that enables us to describe profiles as in Election 1 above, showing the proportion, rather than the absolute number, of ballots of each type cast.

Discrimination. If a particular profile P0 gives rise to a tie, then it should be possible to find a profile P that does not give rise to a tie and in which the proportion of ballots of each type differs from its value in P0 by an arbitrarily small amount. This rules out, for example, the following method of electing one candidate from three: elect the candidate who beats both of the others in pairwise comparisons, if there is such a candidate, and otherwise declare the result a three-way tie. For in that case, not only would the profile in Election 3 below give rise to a tie, but anything at all close to it would also give a tie, contrary to the axiom of discrimination.

                abc  1/3
Election 3:     bca  1/3
(1 seat)        cab  1/3
A proper election rule is one that satisfies the above four axioms; that is, one that is anonymous, neutral, homogeneous and discriminating. The term "axiom" is used rather freely in the literature as a synonym for "property", but I shall restrict its use to these four, which I regard as genuinely axiomatic, in the sense that I am not interested in any rule that does not satisfy them.

A word of warning is needed about homogeneity. In any practical election where the count is carried out by computer, there will be a limit to the number of decimal places that the computer can hold accurately. Thus there are bound to be situations in which two numbers that are not really equal are regarded as equal by the computer program, because they become equal when rounded to the appropriate number of decimal places. In this case, if every ballot were replicated the same, sufficiently large, number of times, then the difference between the two numbers of votes would become significant, and the computer might give a different result. However, this is a minor problem, introduced by the practical need to round numbers; the axiom of homogeneity should be applied to the underlying theoretical rule, with no rounding.

With this interpretation, STV is a proper election rule.

4. Global or absolute properties

It is convenient to divide properties into global or absolute properties on the one hand, and local or relative properties on the other. The former say something about the result of applying an election rule to a single profile, whereas the latter say something about how the result should (or should not) change when certain changes are made to the profile. Not all properties fall unambiguously into one of these two classes, but sufficiently many do for the distinction to be useful.

The most important single property of STV is what I call the Droop proportionality criterion or DPC. Recall that if v votes are cast in an election to fill s seats, then the quantity v/(s + 1) is called the Droop quota.

In statements of properties, the word "should" indicates that the property says that something should happen, not necessarily that I personally agree. However, in this case I certainly do: DPC seems to me to be a sine qua non for a fair election rule. I suggest that any system that satisfies DPC deserves to be called a quota-preferential system and to be regarded as a system of proportional representation (within each constituency)-an STV-lookalike. Conversely, I assume that no member of the Electoral Reform Society will be satisfied with anything that does not satisfy DPC.

The property to which DPC reduces in a single-seat election should hold (as a consequence of DPC) even in a multi-seat election, and it deserves a special name.

The following rather weak property was formulated with single-seat elections in mind, but it makes sense also for multi-seat elections and, again, it clearly holds for STV.

The next property has been suggested to me by Brian Wichmann in the light of his experiences reported in the last issue of Voting matters[6]. This is not satisfied by STV with the Newland-Britton rules. For example, if x receives no support at all, and the only support that y receives is on ballots marked ay, where a reaches the quota as a result of transfers from other candidates, then x and y will both be recorded throughout as having no votes (since the ay ballots are not re-examined when a reaches the quota), and so y is as likely to be excluded as x. It seems that no-support is satisfied by Meek's version of STV, although I do not have a formal proof of this.

The remaining three global properties consist of Condorcet's principle, which was proposed by M. J. A. N. Caritat, Marquis de Condorcet (1743-1794), and two modern strengthenings of it. We say that a voter, ballot or preference listing prefers a to b if he, she or it lists a above (before) b, or lists a but not b. Let p(a, b) denote the number of voters who prefer a to b. We say that a beats b (in pairwise comparisons) if p(a, b) > p(b, a); that is, if the number of voters who prefer a to b is greater than the number who prefer b to a. We say that a ties with b (in pairwise comparisons) if p(a, b) = p(b, a). A Condorcet winner is a candidate who beats every other candidate in pairwise comparisons. A Condorcet non-loser is a candidate who beats or ties with every other candidate in pairwise comparisons; note that if there is more than one Condorcet non-loser then all the Condorcet non-losers must tie with each other.

Note that there need not be a Condorcet winner, or even a Condorcet non-loser. In the profile shown in Election 3 above, a beats b, b beats c and c beats a, all by the same margin of 2/3 to 1/3. This is the so-called Condorcet paradox or paradox of voting: even though each voter provides a linear ordering of the candidates, the result when the votes are totalled can be a cyclical ordering. The Condorcet top tier is the smallest nonempty set of candidates such that every candidate in that set beats every candidate (if any) outside that set. In Election 3, the Condorcet top tier consists of all three candidates. If there is a Condorcet winner, then the Condorcet top tier consists just of the Condorcet winner. If there is a Condorcet non-loser, then the Condorcet top tier contains all the Condorcet non-losers, but it may possibly contain other candidates as well.

Condorcet's principle and the two strengthenings of it given below were formulated originally for single-seat elections in which every voter provides a complete preference listing; but I have reworded them here so that they make sense (although they are not necessarily sensible) for all preferential elections.

Note that Smith-Condorcet and exclusive-Condorcet both imply Condorcet, and Smith-Condorcet also implies majority. Smith-Condorcet seems a very natural extension of Condorcet. Exclusive-Condorcet is also very natural, but it is of much less importance since it differs from Condorcet only when there is a "tie" for first place under pairwise comparisons, and that will not happen very often.
Election 4      Election 5
(1 seat)        (2 seats)
abc     0.30    ad      0.36
bac     0.25    bd      0.34
cab     0.15    cd      0.30
cba     0.30
STV does not satisfy Condorcet, and so it certainly does not satisfy either of the above two extensions of it. This can be seen in Election 4 above. Under STV (AV), b is excluded and a is elected. However, b is the Condorcet winner, beating both a and c by the same margin of 0.55 to 0.45. This example highlights a fundamental difference in philosophy between STV and Condorcet-based rules. Loosely speaking, STV tries to keep votes near the tops of the ballots. Thus the preferences of the cba voters for b over a will not even be considered under STV until c is excluded, which means that in this example they are not considered at all, since b is excluded before c. In contrast, Condorcet's principle requires that, right from the outset, the preferences of the cba voters for b over a should be given equal weight with the similar preferences of the bac voters. However, despite this difference in philosophy, Condorcet and majority are not actually incompatible in single-seat elections: if one wishes, one can use AV (or any other system of one's choice) to select a candidate from the Condorcet top tier. Any such rule clearly satisfies Smith-Condorcet, and hence satisfies both majority and Condorcet, although it is a moot point whether it is really any better than AV on its own. In multi-seat elections, Condorcet is undesirable, in my opinion, because it is incompatible with DPC, as shown by Election 5 above. Here the quota is 0.333...., and so DPC requires that a and b should be elected, whereas d is the Condorcet winner.

5. Local or relative properties: monotonicity

Local or relative properties are concerned with what happens when a profile is changed in some way. We shall say that a candidate is helped or harmed by a change in the profile if the result is, respectively, to increase or to decrease the probability of that candidate being elected.

As we saw in Election 4, under STV the later preferences on a ballot are not even considered until the fates of all candidates of earlier preference have been decided. Thus a voter can be certain that adding extra preferences to his or her preference listing can neither help nor harm any candidate already listed. Supporters of STV usually regard this as a very important property, although it has to be said that not everyone agrees; the property has been described (by Michael Dummett, in a letter to Robert Newland) as "quite unreasonable", and (by an anonymous referee) as "unpalatable". There are really two properties here, which we can state as follows.

We come now to the different versions of monotonicity. The basic theme is that a candidate x should not be harmed by a change in the profile that appears to give more support to x; but one gets different flavours of monotonicity if one specifies different ways in which the profile might be changed.

Monotonicity. A candidate x should not be harmed if:

There is also the following property, which is not strictly a form of monotonicity but is very close to it. It is an extension to multi-seat elections of a property proposed by Moulin[3] for single-seat elections. These properties are not all independent. For example, Moreover, in single-seat elections, Also, if truncated preference listings are not allowed, then mono-raise-random implies mono-sub-top.
                      ab     10
    Election 6:       bca     8
      (1 seat)        ca      7
STV satisfies mono-append but none of the other properties, although in single-seat elections AV satisfies mono-add-plump and mono-add-top. To see that AV does not satisfy mono-raise, mono-raise-delete, mono-raise-random, mono-sub-plump, mono-sub-top or mono-remove-bottom, consider its effect in Election 6 above. As it stands, c is excluded and a is elected. But if two of the bca ballots are removed, or replaced by a or by abc or by anything else starting with a, then b is excluded and c is elected instead of a.
     Election 7      Election 8
     (2 seats)       (2 seats)
     ab      30      ac      207
     ac      90      bd      198
     bd      59      bdac     12
     cb      51      cd      105
     d       70      dc      105
To see that STV does not satisfy mono-add-plump or mono-add-top, consider Election 7. The quota is 300/3 = 100, so that a is elected with a surplus of 20. This is divided 5 to b, 15 to c, and so b has 64 votes to c's 66, b is excluded, and d is elected. Suppose now that we add a further 24 ballots with d top. The quota is now 324/3 = 108, so that a's surplus is now only 12. This is divided 3 to b, 9 to c, and so b has 62 votes to c's 60, c is excluded, and b is elected instead of d.

Although all the monotonicity properties look attractive, I do not think that mono-remove-bottom is desirable in multi-seat elections. Consider Election 8. The quota is 627/3 = 209, and so DPC requires that we elect b and either c or d. It seems to me that {b, c} is clearly the better result (although STV gives {b, d}). But if we now remove the 12 bdac ballots, then the quota drops to 205, so that we must elect a and either c or d. It seems to me that now {a, d} is the better result (although STV gives {a, c}). Thus the removal of the 12 ballots that have c bottom should, in my opinion, harm c.

All the monotonicity properties seem desirable in single-seat elections. However, I proved[7] that no rule simultaneously satisfies mono-sub-plump, later-no-help, later-no-harm, majority and plurality. Since I do not think anyone would seriously consider a rule that did not satisfy both majority and plurality, this shows that in order to have mono-sub-plump one must sacrifice either later-no-help or later-no-harm (or both). Whether or not this is desirable may depend on what other properties one can gain at the same time.

Mono-raise-random, mono-sub-top and participation are very strong properties, and it is possible that they are incompatible with DPC. If one could find a reasonable-looking "STV-lookalike" rule that satisfied all the other monotonicity properties (except for mono-remove-bottom when there is more than one seat), then I personally might well prefer it to STV itself. But we are a long way from finding such a rule at the moment.

While on the subject of monotonicity, I should mention one other monotonicity property, if only to dismiss it immediately.

This seems to me to be plain wrong. Consider the profile in Election 5, for example, which is a very slight modification of one suggested to me by David Hill. If one were using this profile to fill a single seat, then clearly d should be elected (although that is not the result achieved by AV). But if this same profile were used to fill three seats, then clearly a, b and c should be elected; thus d is harmed by the increase in the number of seats.

Another property that is related to monotonicity is known in the literature as consistency[8] or reinforcement[3], but I prefer to call it by its mathematical name:

                    (a)    (b)   (a)+(b)
              ab     6      3      9
Election 9:   bc     4      4      8
(1 seat)      cb     3      6      9
STV does not satisfy convexity. Again, I cannot do better than to quote an example of David Hill's (Election 9). In district (a), c is excluded and b is elected. In district (b), a is excluded and b is elected. But when the ballots from the two districts are processed together, b is excluded and c is elected.

Convexity is one of the best-understood of all properties. Young[8] proved that a symmetric preferential election rule for single-seat elections satisfies convexity if and only if it is equivalent to a point scoring rule (in which one gives each candidate so many points for every voter who puts them first, so many for every voter who puts them second, and so on, and elects the candidate with the largest number of points). Since no point scoring rule can possibly satisfy DPC, it follows that convexity and DPC are mutually incompatible. This is a pity, because convexity implies several of the monotonicity properties; but, sadly, it is of no use to us.

Of course, the absence of convexity will hardly ever be noticed in practice, since elections are not counted both in separate districts and together as a whole. But it is worrying inasmuch as it may suggest that something odd is going on.

6. Further properties

A question that is sometimes asked about STV is, is a truncated preference listing treated as if all the remaining candidates were placed equal last? Since STV (in its usual formulation) does not allow for equality of preference, the question does not really make sense. But one can make sense of it as follows. The symmetric completion of a truncated preference listing is obtained by taking all possible completions of it with equal weight, chosen so that the total weight is 1. For example, suppose that there are five candidates, a, b, c, d, e. Then

It is not difficult to see that AV satisfies symmetric-completion. Although AV is usually described in terms of a quota, it can alternatively be described as follows: repeatedly exclude the candidate with the smallest number of votes, until there is only one candidate left. The effect of replacing truncated preference listings by their symmetric completions is simply that, at each stage in the count, the votes of all non-excluded candidates are increased by the same amount. It follows that the order of exclusions is not affected, nor therefore is the eventual winner.

                a       60
Election 10:    ab      60
(2 seats)       b       14
                c       46
To see that STV does not satisfy symmetric-completion in general, consider Election 10. The quota is 180/3 = 60, so that a is elected with a surplus of 60. Under the Newland-Britton rules, the whole of a's surplus goes to b, who is elected. Under Meek's method, the transfer of a's surplus ends with the quota reduced to (180 - 36)/3 = 48, with 36 non-transferable votes going to 'excess', and 36 votes transferred to b. Either way, a and b are elected. However, if each ballot is replaced by its symmetric completion, then, of a's surplus of 60 votes, 45 go to b and 15 to c, and c is elected instead of b.
Election 11     Election 12
(2 seat)        (3 seats)
ab      40      ab      40
ba       2      ba       2
cd      12      cd      12
dc       6      dc       6
                e      180
David Hill has sent me an example, which I have modified slightly above, to show that quota reduction is preferable to symmetric completion in STV. In Election 11 the quota is 60/3 = 20, and so a and b are elected. In Election 12 the quota is 240/4 = 60, so that e is elected with a surplus of 120. Under symmetric completion, this would be used to increase the votes of the remaining candidates by 30 each, so that a would be elected first, after which d would be excluded and c would be elected. However, if the quota is reduced to 20 after the election of e then a and b are elected as in Election 11. To paraphrase David's comments slightly, "Election 12 has one extra candidate, one extra seat, and a large number of extra voters whose sole wish (apparently) is to put that extra candidate into that extra seat. It is nonsense that the original 60 voters should get a and c elected in Election 12 instead of the a and b they would have got from Election 11."

The remaining properties are all concerned with the avoidance of "wrecking candidates". A "wrecking candidate" is a candidate who is not elected but who, by standing for election and so "splitting the vote", prevents someone else from being elected. One might naively hope to avoid wrecking candidates altogether, which would result in the Independence of Irrelevant Alternatives, or IIA:

However, it is easy to see that no discriminating election rule can satisfy both IIA and majority. For, consider Election 3 above. By the axiom of discrimination, there must be a profile arbitrarily close to this one that does not give rise to a tie. If this profile results in the election of a, then b is a wrecking candidate: for, if b had not stood for election, then c would have been elected (by majority, since roughly two thirds of the voters prefer c to a); thus the result of the election is not as if b had not stood. In a similar way, if b is elected then c is a wrecking candidate, and if c is elected then a is a wrecking candidate.

In an attempt to find a property weaker than IIA but expressing a similar idea, I came up with the following.

Unfortunately I do not know of any sensible election rule that satisfies even this. Certainly STV does not. For example, if there are 15 ballots marked x and 14 marked z, then AV (and any sensible rule) will elect x; but if 10 of the 15 x ballots are now changed to read yx, then AV will exclude x and elect z instead.

An alternative weakening of IIA has been proposed by Tideman [5]. In his terminology, a number of candidates form a set of clones if every preference listing that contains one of them contains all of them, in consecutive positions (but not necessarily always in the same order). He says that a single-seat election rule is independent of clones if it satisfies the following properties, which I have reformulated here so that they make sense for multi-seat elections as well.

                xx'a    13
                x'xa    11
Election 13:    abc     10
(2 seats)       bc      12
                c       14
It is not difficult to see that AV satisfies all the clone properties. I am fairly sure that STV also satisfies clone-in in multi-seat elections, although I do not have a formal proof of this. To see that STV does not satisfy the other two clone properties, consider Election 13. The quota is 60/3 = 20. Nobody having reached the quota, a is excluded and b is elected; then x' is excluded and x is elected. However, if the clones x and x' are replaced by a single candidate x, then x has 24 votes initially and so is elected, and the surplus of 4 votes goes to a; therefore b is excluded, and c is elected instead of b. So replacing x by a pair of clones helps b and harms c.

Clone-no-harm is actually incompatible with DPC. To see this, note that if only two candidates stand in a 2-seat election, where the voting is (say) x 70, y 30, then both must be elected. But if x is replaced by a pair of clones and the voting is now xx' 35, x'x 35, y 30, then DPC requires that x and x' should both be elected. This suggests that clone-no-harm is not a desirable property for multi-seat elections-and Tideman never suggested that it was. But clone-in and clone-no-help both look sensible to me, even for multi-seat elections.

References

  1. Marquis de Condorcet, Essai sur l'Application de l'Analyse à la Probabilité des Décisions Rendues à la Pluralité des Voix, Paris, 1785.
  2. P. C. Fishburn, Condorcet social choice functions, SIAM Journal on Applied Mathematics 33 (1977), 469-489.
  3. H. Moulin, Condorcet's principle implies the no show paradox, Journal of Economic Theory 45 (1988), 53-64.
  4. J. H. Smith, Aggregation of preferences with variable electorate, Econometrica 41 (1973), 1027-1041.
  5. T. N. Tideman, Independence of clones as a criterion for voting rules, Social Choice and Welfare 4 (1987), 185-206.
  6. B. A. Wichmann, Two STV Elections, Voting matters (The Electoral Reform Society) 2 (1994), 7-9.
  7. D. R. Woodall, An impossibility theorem for electoral systems, Discrete Mathematics 66 (1987), 209-211.
  8. H. P. Young, Social choice scoring functions, SIAM Journal on Applied Mathematics 28 (1975), 824-838.

Up: Issue 3 Previous: Paper 4