t Up: Issue 15 Previous: Paper 1 Next: Paper 3

Voting matters - Issue 15, June 2002

Nonmonotonicity in AV

E Stensholt

Eivind Stensholt is from the Norwegian School of Economics and Business Administration

Introduction

Nonmonotonicity arises with STV when apparent additional support for a candidate, A, at the expense of another candidate, C, causes a third candidate, B, to be elected. Without the additional support, A would be elected. Thus the additional support actually costs A the election. This unfortunate property in the standard variations of STV is linked to the elimination of candidates in the counting process[6], and it is unavoidable unless some compromise is made with the principle that a voter's later preferences cannot influence the fate of the voter's earlier preferences.

How frequently will it happen that a candidate is not elected, but might have been elected if some of his or her support had gone to another candidate instead? That depends on the voters' behaviour. Based on standard assumptions on the distribution of voter preference, modified by empirical evidence of voter behaviour, the frequency is estimated for elections in which 1 candidate is elected from 3. This is the Alternative Vote (AV), a single-seat version of STV.

It is also shown how the nonmonotonicity is related to the Condorcet paradox in which one majority prefers B to A, another majority prefers A to C, and a third majority prefers C to B. In all elections considered, each voter is assumed to give a complete preference list.

For example, consider an election (from a simulation with 10000 voters) with

 475 ABC
3719 ACB
 390 CAB
2110 CBA
  41 BCA
3265 BAC
No candidate has 50% of the first preference votes. C, with only 2500 first preference votes is eliminated, and finally B defeats A with 5416 votes to 4584. However, if x of the ACB-voters vote 'strategically' CAB instead, the election may turn out differently. Then the profile is
 475   ABC
3719-x ACB
 390+x CAB
2110   CBA
  41   BCA
3265   BAC
If x > 806, C with 2500+x overtakes B with 3306, and if x<888, A is still ahead of B with 4194–x to 3306. Thus, with 806 < x < 888, B gets eliminated, and finally A defeats C with 7459–x votes to 2541+x.

The example also shows the Condorcet paradox of cyclic majorities. In pair-wise encounters A defeats C with 7459–x to 2541+x, C defeats B with 6219 votes to 3781, and B defeats A with 5416 votes to 4584. However, in real elections with 3 candidates cyclic majorities become very rare as the number of voters increases. One indicator of unrealism is that the cyclic order ABCA receives only 475+390+41+x = 906+x votes while ACBA receives 3719+2110+3265–x = 9094–x votes. In real elections the votes are distributed in the 6 categories in a more harmonious way.

If nonmonotonicity occurs in a real election, the scenario is most likely that there is a plurality winner, A (with the largest number of first preference votes), another Condorcet winner, B (who defeats each other candidate in pair-wise encounters), and a third candidate, C (who is last in first preference votes). Such an example, from the same simulation, is

2996 ABC
1122 ACB
 875 CAB
2046 CBA
1431 BCA
1530 BAC
Here C is eliminated and B wins the AV-election. If x voters switch from ACB to CAB, and 40 < x < 648, then B is eliminated and A wins. It turns out that if AV is modified and A declared winner in the few cases like this, nonmonotonicity is eliminated. Instead, however, another principle will be violated: B may win by a suitable vote transfer from BAC to BCA.

3-candidate elections may be classified according to how well the 'electoral cake model' in Stensholt[5] may be fitted; the figure below shows a good fit. The model may be fitted quite well to most real elections. When simulated elections are classified, election P is considered more 'realistic' than election Q if the model fits P better than Q. When better fit, i.e. more 'realism', is demanded, the frequency of the Condorcet paradox will approach 0. Nonmonotonicity, however, occurs in about 0.90% of all simulated 'realistic' elections. Two real elections (37 candidates, 63 voters) and (14 candidates, 115 voters) have been checked, with nonmonotonicity in, respectively, 0.66% and 1.10% of the candidate triples.

A description of nonmonotonicity by means of inequalities

A possible preference distribution P in an election with 3 candidates, A, B, and C (a profile in the social choice vernacular), consists of a sequence of 6 non-negative numbers.

P = (p q r s t u),

These are the numbers (absolute or relative) of voters with preference ranking respectively: ABC, ACB, CAB, CBA, BCA, BAC.

If x of the ABC-voters and y of the ACB-voters change to vote CAB, there is a new profile Q:

Q = (p–x q–y r+x+y s t u).

Nonmonotonicity occurs if B is AV-winner in P and A in Q despite the natural expectation that the candidate A is weaker in Q than in P. The story is told in 9 inequalities.

r+s+t+u > p+q (1)

p+q+r+s > t+u (2)

p+q > r+s (3)

t+u > r+s (4)

s+t+u > p+q+r (5)

p+q+t+u–(x+y) > r+s+(x+y) (6)

r+s + (x+y) > t+u (7)

p+q–(x+y) > t+u (8)

u+p+q–(x+y) > r+s+t + (x+y) (9)

A translation to non-mathematical language links the inequalities to the AV rules. (1, 2): In P, neither A nor B have 50% of the first preference votes. (3, 4): In P, C has the lowest number of first preference votes. (5): In P, B wins over A (after elimination of C). (6): In Q, C does not reach 50% first preference votes. (7): In Q, C passes B in first preference votes. (8): In Q, A keeps more first preference votes than B. (9): In Q, A wins over C (after elimination of B).

However, the mathematical version (1-9) is easier to analyse. Write (7, 8, 9) equivalently as

min[p+q–t–u, (u+p+q–r–s–t)/2] > x+y > t+u–r–s (10)

Thus numbers x and y satisfying (7, 8, 9) exist if and only if (11) and (12) hold:

p+q+r+s > 2t+2u (11)

p+q+r+s > 3t+u (12)

Moreover, (1), (2), (3), and (6) are redundant because of (5), (11), (4 and 8), and (9), respectively. Therefore the p+q supporters of candidate A can turn defeat in P to victory in Q if and only if (4, 5, 11, 12) all hold. Then x+y of them vote 'strategically' CAB, with x+y as in ( 10).

A profile where a candidate may be helped by being ranked lower in some ballots without any other change in any ballot will be called a nonmonotonic profile for the election method considered. In discussing various election rules, it is also useful to have an 'absolute' definition: A profile is then nonmonotonic if it is so for AV. A monotonic election method is one without nonmonotonic profiles. AV, and the usual STV-variations are nonmonotonic because of the elimination rules. By the criteria (4, 5, 11, 12)

p+q > t+u > r+s (13)

Thus, in P, A is plurality winner (first past the post), while B beats A and A beats C in pair-wise comparisons by (5) and (9). This we will call nonmonotonicity of type ABC. There are six types of nonmonotonic profiles: ABC, ACB, CAB, CBA, BCA, and BAC.

Connection to the Condorcet paradox; a geometric description

The Condorcet paradox occurs together with ABC-type nonmonotonicity when also C beats B in pair-wise comparison, i.e.

q+r+s > t+u+p (14)

Otherwise B is the Condorcet winner, i.e. B defeats each opponent in a pair-wise contest. The strategic voting of the x+y voters who honestly support A is then designed to take the AV victory away from Condorcet winner B to plurality winner A. Define E, F, G, H, K as functions of the profile:

E=–r–s+t+u

F=–p–q–r+s+t+u

G= p+q+r+s–2t–2u (15)

H= p+q+r+s–3t–u

K=–p+q+r+s–t–u

When all possible profiles are standardized, e.g. to p+q+r+s+t+u=12, as in the table below, they form a 5- dimensional simplex with 6 corners — a higher dimensional analogue of the familiar 3-dimensional simplex (tetrahedron) with 4 corners and 4 triangular sides. By (4, 5, 11, 12) the nonmonotonic profiles of ABC-type form a convex subset S of this simplex, given by

E > 0, F > 0, G > 0, H > 0 (16)

The Condorcet paradox occurs if K > 0 too. The profiles in the table are the corners of the closure of S and have non-negative E, F, G, H.

In the right hand column, e = e(P) is a continuous function of the profile P, defined in Stensholt[5]. By its definition, 0 < e < 3sqrt(3)/4pie is about 0.4135. Generally e is well below 0.01 in profiles from real elections with many voters. Any profile P satisfying (16) may be written as

P = k0l·P01 + k02·P02 + k03·P03 + ... + kl6·Pl6 (17)

with non-negative kj and k01 + k02 + k03 +... + kl6 = 1.

To a profile P = (p q r s t u) we may assign a twin profile P* = (q p r s t u). Thus P**=P and Pi* = Pi+8, i=1, 2,.., 8. If P is a nonmonotonicity profile of type ABC, so is P*. With P as in (17), then

P*=k09·P01+k10·P02+.. +k16·P08+ k01·P09+k02·P10+..+k08·P16, (18)

K(0.5·[P + P*]) = 0.5·[K(P) + K(P*)] = –2·(k07 + k08 + kl5 + kl6) <= 0 (19)

Thus the profile 0.5 [P + P*], midway between P and P*, will never give the Condorcet paradox, but it is on the borderline if and only if k07 = k08 = kl5 = kl6 = 0 Somewhere between 1/3 and 2/3 along the line segment from P to P*, K = 0. From the K-column in Table 1 it is clear that, with many voters, somewhere between 33% and 50% of all nonmonotonicity profiles also have a Condorcet cycle. However, they are not all equally likely to occur in real elections.

Simulation and reality

One million random 3-candidate profiles were generated with uniform probability in the simplex. The distribution is known as the Impartial Anonymous Culture (IAC). The IAC also depends on the number of voters, but the simulation corresponds to the limit case of infinitely many voters. Actually about 100 voters would give quite similar results.

In 3621 of the IAC-generated profiles were E>0, F>0, G>0, H>0. As there are six nonmonotonicity types, about 6×0.3621% = 2.17% of the profiles are nonmonotonic. Among these 3621, 1602, i.e. = 44.24% also had K>0, indicating a Condorcet cycle in the profile: A beats C beats B beats A. For comparison, 6.25% of all IAC-profiles have a Condorcet cycle [2][5].

In real elections the cycle frequency is much lower. That is due to a structure in the profiles, which may come from the voters having some common perception of the 'political landscape' although they have placed themselves in different positions and rank the candidates accordingly [5].

Imagine that the voters are distributed with uniform density in a circular disc, that candidates A, B and C are among them, and that a voter ranks the candidates according to their distance from the voter's position. In a pair-wise comparison between A and B, B wins if and only if B is closer than A to the circle centre. A and B divide the voters between them with the mid-normal to the line segment AB as dividing line. Similarly the mid-normals for BC and AC divide the disc. The three candidates split the 'voter cake' in six pieces by three straight cuts through one common point, each piece getting an area proportional to the number of votes with the corresponding ranking of the candidates. In a model like this, the Condorcet paradox can never occur except in a degenerate form with all cuts through the circle center, and p=s, q=t, r=u.

Empirically, the electoral cake model fits reasonably well for 3-candidate profiles from real elections with a large number of voters. That is why the Condorcet paradox is rare. The function e(P) measures the deviation of P from the model. For the examples in the introduction,

e(0475, 3719, 0390, 2110, 0041, 3265) = .174035768

e(2996, 1122, 0875, 2046, 1431, 1530) = .000000108 (see figure).

Among the simulation profiles with small e(P), about 0.15% were nonmonotonic of ABC-type. This suggests an estimate of 0.90% for the probability for nonmonotonicity in a candidate triple in real elections with many voters.

In an election with 63 voters and 37 candidates at the author's institution, 51 of the 37×36×35/6 = 7770 triples were nonmonotonic, a fraction of 0.66%. In these 51 triples, the Condorcet paradox occurred only 7 times, i.e. much less than the 44.24% in the full IAC-simulation. In another election in the same place, with 115 voters and 14 candidates there were 4 nonmonotonicity triples out of 14×13×12/6 = 364, i.e. 1.10% and the Condorcet paradox occurred in none of them. Comparison with the simulation requires some caution since the triple profiles in an election with many candidates cannot be assumed stochastically independent.

Conclusion

In an election with 3 candidates, A, B and C, let A be plurality winner. In the vast majority of elections, there will also be a unique Condorcet winner. If A also happens to be Condorcet winner, A wins the AV-election. That cannot be very controversial.

So assume B is Condorcet winner, which means that B wins if A or C is eliminated. B may win with very few first preference votes in the ballots, but electing B means that there are no 'wasted votes'. The 'plurality ideology' may also be modified to avoid wasting votes by eliminating B; then the supporters of B are allowed to influence the choice between A and C. An election method that always eliminates a Condorcet winner who is not also a plurality winner, may seem strange. However, it would, arguably, be a democratic improvement of the plurality method that is in wide use today. It preserves the 'plurality ideology' as well as possible, preferring to let centre voters decide between 'right' and 'left' rather than filling an assembly with centre politicians.

AV can be seen as a compromise between the 'plurality ideology' and the 'Condorcet ideology'. There are two possibilities.

Nonmonotonicity occurs in (II) if A has a number of surplus first preference votes that could be transferred to C in a way that benefits A. Such transfer is not a part of AV, but this can be remedied in the spirit of STV if the transfer rule is extended. When (16) holds, let the necessary number of surplus votes be transferred from voter categories ABC and ACB to CAB if this lets C become number 2 in terms of first preference votes, and still lets A win against C after elimination of B. This transfer of first preference votes from A to C involves only voters who prefer A to B (categories ABC, ACB, CAB), and it may be implemented in the counting process when it helps A to win instead of B.

An obvious argument against such a procedure is that it occasionally may violate the cherished principle that my second preference should never hurt my first preference. To see this, consider first standard AV. Then C is eliminated after examination of first preferences only. The second preferences of C's supporters become available, and either A (plurality winner) wins or B (Condorcet winner if one exists) wins. Among the conditions in (16) for an extra transfer of votes from A to C, the three first only involve first preference votes: p+q, r+s, t+u. The inequality H > 0 requires information about t and u, i.e. about the second preferences of B's supporters. This allows for strategic voting on behalf of B. Let z voters move from BAC to BCA. Then according to (15) the requirement H > 0 is sharpened to

p+q+r+s–3tu–2z>0.

The strategy is to break this condition, which is achieved if and only if

p+q+r+s–3tu <= 2z <= 2u

Such strategy is possible if and only if

p+q+r+s+t+u <= 4(t+u),

i.e. if and only if B has at least 25% of the first preference votes. This will, however, always be the case when the extra transfer rule is invoked, because by (1) A has less than 50% of the first preference votes and by (4) B has more first preference votes than C. AV with extra transfer violates the principle exactly when standard AV violates monotonicity.

In 3-candidate elections, voters may be offered one of two guarantees:

  1. You can never hurt a candidate by an upwards move;

  2. You can never hurt a candidate by a change in the subsequent ranking.
In about 99% of the elections, the profile is monotonic. Then AV and AV with extra transfer satisfy both 1) and 2), as no extra transfer is done. In the remaining cases, standard AV picks the Condorcet winner and violates 1) but not 2), while AV with extra transfer picks the plurality winner and violates 2) but not 1). Which of the two guarantees is then most important?

With more candidates, it becomes more complicated to study nonmonotonicity in AV. With 5 candidates, A, B, C, D, and E, there are 10 triples, and each candidate takes part in 6 triples:

{A,B,C}, {A,B,D}, {A,B,E}, {A,C,D}, {A,C,E},

{A,D,E}, {B,C,D}, {B,C,E}, {B,D,E}, {C,D,E}.

After all but 3 candidates are eliminated, there is a final triple, say {A,B,C}. If AV is adopted in more than 600 constituencies, as in a Westminster election, there will generally be some with nonmonotonicity in {A,B,C}. How bad will criticism from frustrated supporters of a non-elected plurality winner in such cases be for people's trust in standard AV?

If A, B and C are much stronger than all other candidates, it may be enough to implement the extra vote transfer in {A,B,C} in order to cope with most nonmonotonic profiles. Nonmonotonicity is reduced, at a price: How bad will criticism from frustrated supporters of a non-elected Condorcet winner in such cases be for people's trust in AV with extra transfer?

The purpose of elimination is to find the opponent for A in the final pair, so B or C must be eliminated. The extended transfer rule only adjusts the border between elimination of B and elimination of C. Is an election of B due to honest first priority from A's supporters more tolerable than election of A due to honest subsequent ranking from B's supporters?

Can we achieve monotonicity with more than 3 candidates, at a reasonable price? Perhaps a recursive idea may work. Assume that the set of profiles S with n candidates has been subdivided into n subsets S = Sl union S2 union ... union Sn, so that candidate i wins with profile in Si and that this election method is monotonic. With n+1 candidates left, eliminate Z with the lowest number of first preference votes. If that leads to a profile in SY and X /= Y, then allow an extra transfer of first votes from X to Z or even to more candidates in order to eliminate another candidate and obtain an n-candidate profile i Sx. The possibility of saving more candidates than Z from elimination by an extra transfer raises the question of whether X is uniquely defined.

A more radical measure is to count in each triple separately, implementing the extra transfer. 'Triple-AV' then gives a candidate one point for a triple victory, and achieves monotonicity. It is similar to Copeland's method[1][3][4], which gives one point for each victory in a pair-wise comparison and avoids Condorcet cycles. On the other hand, the price for monotonicity with triple-AV may well be too high in terms of violations of the principle.

An axiomatic study of election theory reveals some basic impossibilities. Certain combinations of nice properties cannot be realized simultaneously in one election method. To achieve monotonicity, one must sacrifice the principle. On the other hand, only in the few cases where (16) holds, will triple-AV find another triple winner than standard AV.

Three papers in Voting matters[6][7][8] deal with nonmonotonicity and related problems. One theme is the axiomatic understanding of election methods: which combinations of desirable properties are theoretically incompatible? That kind of knowledge is important for everyone concerned with 'how to choose how to choose'. An axiomatic approach, however, needs a clearly formulated and manageable conceptual frame. As part of this frame, it must be clearly stated what kind of preference relations the voters are allowed to express. One may restrict ballots to be complete, or to conform to a linear listing of the alternatives (single-peak condition), etc. Within this frame the axiomatic investigator must take into account all possible profiles without any extra screening against unrealistic profiles. Even a highly concocted profile may be a counter-example that kills a hypothesis; lack of realism is no objection if the profile formally is within the axiomatic frame. According to Stensholt[5] a bound on the function e(P) of the 3-candidate profile P is useful to screen off most of the unrealistic profiles generated in a simulation. However, a criterion like e(P) < 0.01 does not seem suitable for axiomatic treatment. Axiomatics must be followed up by other approaches, e.g. comparisons of election methods on simulated and empirical data.

Acknowledgements

It is a pleasure to recognize the many exchanges with the editor and the comments of an anonymous referee. The latter led to a complete rewriting of the conclusion section, where however, there still are viewpoints for which the author dares not presume full agreement.

References

  1. A.H. Copeland, A 'reasonable' social welfare function, Seminar on Mathematics in Social Sciences, University of Michigan, 1951.
  2. W. Gehrlein and P.C. Fishburn, Probabilities for election outcomes for large electorates, J. Econom. Theory, 19, (1978) pp. 38-49
  3. V.R. Merlin, and D.G. Saari, "Copeland Method. II. Manipulation, Monotonicity, and Paradoxes"; Journal of Economic Theory; Vol. 72, No. 1; January, 1997; 148-172.
  4. D.G. Saari. and V.R. Merlin, 'The Copeland Method. I. Relationships and the Dictionary'; Economic Theory; Vol. 8, No. l; June, 1996; 51-76.
  5. E. Stensholt(1996) Circle pictograms for vote vectors, SIAM Review Vol 38 No 1, pp.96-119.
  6. D.R. Woodall (1994) 'Properties of Preferential Election Rules', Voting matters, Issue 3, 8-15;
  7. D.R. Woodall (1995) 'Monotonicity — An In-Depth Study of One Example', Voting matters, Issue 4, 5-7;
  8. D.R. Woodall (1996) 'Monotonicity and Single-Seat Election Rules', Voting matters, Issue 6, 9-14.

Up: Issue 15 Previous: Paper 1 Next: Paper 3