Evaluating Voting Methods

Matt Corks, <mvcorks [AT] alumni [dot] uwaterloo [dot] ca>

Introduction

A voting method is a mapping from a set of voter preferences to an election outcome. If there are only two alternatives, it suffices to choose the alternative preferred by the majority of voters. There are no problems unless the vote results in a tie.

When selecting between more than two alternatives, however, several paradoxes arise. Highly counter-intuitive situations can result from most voting methods, leaving the political theorist to answer the question: which voting method will best reflect the wishes of the electorate? To answer this question, various fairness criteria are used to evaluate the methods which exist for voting between N alternatives.

Fairness Criteria

To begin with, we list four criteria which intuitively seem necessary to hold a meaningful election.

Pareto Criterion:

If every voter prefers alternative a over alternative b, then b should not be declared the winner.

The next condition is due to the Marquis of Condorcet, an eighteenth century French mathematician.

Condorcet Winner Criterion:

If there exists an alternative a which would win in pairwise votes against each other alternative, then a should be declared the winner of the election.

Note that there is not necessarily such an alternative a. This alternative is called the Condorcet winner.

Condorcet Loser Criterion:

If there exists an alternative a which would loose in pairwise votes against each other alternative, then a should not be declared the winner of the election.

Monotonicity Criterion:

If alternative a is declared the winner under a voting method, and one or more voters change their preferences in a way favour to a (making no other changes), then a should still win.

Preferential Voting Methods

There are two fundamentally different types of voting methods. They differ in whether they ask a voter to state a preference between two given alternatives. Those systems which do are called preferential voting methods. There also exist non-preferential voting methods, which will be discussed later.

Plurality Method:

Each voter picks one alternative, and whichever has the most votes wins.

The opinions of a given voter can be thought of as a preference ballot, which lists each alternative in order. With this model, we see that the Plurality Method considers only the first-place rankings, ignoring the rest of information in preference ballot. There are examples which show that this system doesn’t satisfy either Condorcet criteria. It does, however, satisfy Pareto.

Perhaps a more serious problem with this system is that it encourages insincerity. A voter can obtain a more preferred outcome by voting for their favourite among the top-rank alternatives, as opposed to their favourite overall. This strategy is quite well-known. With the Plurality Method, people are unwilling to support an unpopular candidate they greatly prefer, fearing that they will “throw their vote away,” to quote Kang from the Simpsons episode ‘Treehouse of Horror VII’.

In the following example, alternative c is the Condorcet loser, yet wins the election under the Plurality Method.

There is a slight modification to this voting method which does satisfy the Condorcet winner criterion:

Plurality with Runoff:

Perform a plurality election, and then select the winner of pairwise runoff between top two options.

This method still fails the Condorcet loser criterion. However, this slight improvement introduces a serious flaw. The following example shows that this modification to the Plurality method causes it to fail the Monotonicity criterion:

Here, alternatives a and b receive the most votes, and a beats b 11:6 in a pairwise election. But suppose that two voters decide they prefer a to b:

Now, a and c receive the most votes, and a loses the runoff to c by 8:9.

In general, voting schemes which use a runoff procedure fail the Monotonicity criterion. Nevertheless, several have been suggested, such as the following:

Plurality with Elimination:

Perform a plurality election, eliminate an undesired alternative, and repeat until only one alternative is left.

(Practically speaking, this would be implemented by having voters complete a preference ballot, listing all alternatives in order of preference, so they only need to register their opinions once. Another reason for doing this is that if a voter is allowed to reconsider their choice, with knowledge of the first outcome, the game theoretic analysis of the vote changes completely.)

In each round, the method can either eliminate the alternative with the least first-place votes or most last-place votes. The first, and most widely used, method was devised by the mathematician Thomas Hare, who actually generalized this to a complicated method for electing N alternatives. The second was proposed by the psychologist Clyde Coombs.

These methods use only the first-place or last-place rankings in each round, but lower ranked alternatives can move up later. This would seem to be an improvement over the Plurality method, since more information used. However, it can be shown that neither method satisfies the Condorcet winner or Monotonicity criteria.

Consider, for example, the following voter preferences:

In this case, the Hare system first eliminates alternative b, the Condorcet winner, and eventually elects alternative c. It is worth noting that the Coombs system does elect alternative b in this case. However, consider the following example:

Alternative a is the Condorcet winner, and by Coombs’ method, it is eliminated first. Alternative b is declared the winner. Although this system uses most of the information in the preference ballot, it still fails the Monotonicity criterion, since it is held in several rounds with elimination in between.

Sequential Pairwise Voting:

Vote between one pair of alternatives, and eliminate the loser. Pair the winner off with another alternative, and repeat. Continue until only one is left.

This system uses all the information from preference table, but not all at once. It clearly meets the Condorcet criteria, but in the absence of a Condorcet winner, the election outcome is highly dependent on the agenda of the vote. In general, the later an alternative is introduced, the better its chances of winner. (That the order of the comparisons is important is shown in Olympic single elimination tournaments, in which the players expected to perform the best are ‘seeded’ so that they meet each other as late as possible. Clearly it is unreasonable to attempt to rig a political election in this fashion.)

Suppose we had a set of voter preferences as follows:

It is possible to devise an agendas which result in each of the alternatives winning:

Voter insincerity is also rewarded with this method. Robin Farquharson shows that by helping to defeat their preferred alternative’s main opponents, a voter can cause a more favorable election outcome, regardless of whether voting in this way accurately reflects their preferences or not.

We have seen that elimination methods tend to throw out alternatives too early, on the basis of too little information. What is needed is a method which considers all preference information simultaneously. Such a system was proposed by Jean-Charles de Borda in 1781, and is now known as the Borda Count method.

Borda Count:

To choose between N alternatives, assign each N-1 points for every first-place ranking from a voter, N-2 for each second-place ranking, and so on. The count of each alternative is the sum of these points, and the winner is the alternative with the highest count.

This method uses all the information from the preference ballot simultaneously. It chooses the alternative which has the highest ranking on average, since the rank of alternative a, divided by number of voters, is the average number of alternatives ranked under a.

This system satisfies the Pareto, Condorcet loser, and Monotonicity criteria. It does not, however, satisfy the Condorcet winner criterion, as Condorcet himself pointed out. This is shown in the following example:

The three alternatives receive Borda counts as follows: a = 6, b = 7, and c = 2. Hence, b wins the election, even though a is the Condorcet winner.

As well, like Plurality voting, this system rewards voter insincerity, and thus would lead to stratagizing. Assume that a given voter most strongly favours alternative a, and believes that alternative b is the strongest competitor to a. Our voter can lower the risk that b will beat a by giving b a lower ranking than they otherwise would. When this fact was pointed out to Borda, he replied, “My scheme is only intended for honest men.” However, this is probably an unreasonable assumption, given the general problem of finding a voting method for everyday use.

At this point, you’re probably thinking, “Okay, so you can pull a counter-example out of your ass for any voting scheme I throw at you. But really, how likely are these paradoxes? Are these voting methods all equally bad?” Good question.

In 1978, Chamberlin & Cohen analyzed several voting methods by calculating the number of times they would pick a Condorcet winner when one existed. For example, given every possible set of voter preference ballots for 4 alternatives and 21 voters, we see that these voting methods elect the Condorcet winner with the following frequency:

As the number of voters increases, the Coombs and Borda methods elect the Condorcet winner with increasing frequency, but the Plurality and Hare methods do so with decreasing frequency.

We will look at three more preferential voting methods of interest. The first is due to Duncan Black, in 1958.

Black:

If there is a Condorcet winner, choose it. Otherwise, take the Borda Count winner.

This method clearly satisfies the Condorcet winner criterion. However, it fails a more generalized statement, due to John Smith, in 1973:

Smith’s Generalized Condorcet Winner Criterion:

If the set of alternatives can be partitioned into two sets A and B, such that each alternative in A would beat every alternative in B in a pairwise vote, then a voting method should not elect a member of B.

As expected, Black’s system fails this criterion. An example follows:

There is no Condorcet winner in this case. The Borda counts are as follows:

So, alternative x wins. Now, let set A = {a, b, c}, and let B = {x, y, z, w}. Every member of A beats every member of B in a pairwise election by 2:1. However, this example seems somewhat contrived, and probably would not arise very often.

In 1907, E. J. Nanson devised another voting method, using the fact that if there is a Condorcet winner, it will win more than half the votes in pairwise contests, and hence has a higher than average Borda Count.

Nanson:

Eliminate those choices from a Borda count tally that are at or below the average Borda count score, then the ballots are retallied as if the remaining candidates were exclusively on the ballot. Repeat if necessary until a single winner remains.

Based on Nanson's work, a closely related system was proposed by J. M. Baldwin:

Baldwin:

Recursively eliminate the alternative with the lowest Borda count until only one alternative (or a collection of tied alternatives) remain.

This does indeed satisfy the Condorcet criteria, and even satisfies Smith’s generalized Condorcet criterion. Like other elimination schemes, however, these fail to satisfy the Monotonicity criterion, as shown here:

The alternatives receive the following Borda counts: a = 21, b = 20, c = 19. Using the Baldwin method, since c has the lowest count, we eliminate it, and a beats b 13:7 to win the election. But if the last 2 voters change their mind in favour of a, the preference ballots become:

This gives the Borda counts as: a = 23, b = 18, c = 19. So, b is eliminated, and a loses to c, 8:12.

The last system uses the Condorcet style of pairwise comparison. It was proposed by A. H. Copeland in 1950.

Copeland:

Hold pairwise votes between every pair of alternatives. Assign 1 points to an alternative for winning, and
-1 for losing. The winner is the alternative with the highest score.

This Condorcet-style system disregards the intensity of a voter’s preference between two alternatives (unlike, for example, the Borda count), and so leads to many ties. In practice, this would only be a problem with a small number of alternatives and voters. Copeland’s method satisfies all of the above criteria. Before assuming that we have found the ideal voting method, however, consider the following set of preference ballots, evaluated under the Copeland and Borda voting methods:

There is no Condorcet winner for these preferences. The alternatives rank as follows:

Under the Copeland method, a wins, and using the Borda Count, e wins. Note, however, that fully 8 of the 9 voters prefer alternative e to a. So, despite passing all of our original criteria, there are cases where the Copeland method seems to elect the wrong alternative. Apparently, more criteria are required before we can approve of a voting method.

Adding criteria results in other problems, however. In 1952, Kenneth Arrow published his famous Impossibility Theorem. This states that, for a given set of criteria, it is impossible for a voting method to satisfy all simultaneously. In our context, his theorem means that no voting method can satisfy all of our previous conditions without violating the following criterion:

Independence of Irrelevant Alternatives Criterion:

If an election results in an alternative a being declared the winner, then a should also win an election with the same voter preferences, but with one or more losing alternatives are removed.

Non-Preferential Voting Methods

Many of the problems faced with preferential voting methods simply don’t apply to non-preferential systems. For example, the statement of the Condorcet criteria requires a preferential voting method. With this in mind, consider the following method:

Approval Voting:

Voters can cast either 0 or 1 votes for each alternative. The alternative with the greatest number of votes is declared the winner.

This method was independently proposed by several people in the 1970s. Since then, it has been adopted by various governments and organizations around the world, most notably by the United Nations to elect Secretary-General. Motions to adopt it have also been tabled in several states.

Approval voting does pass the Independence of Irrelevant Alternatives criterion. It can’t directly be evaluated using some of the other criteria listed above, however, since their statement is specific to preferential voting methods. However, various counter-intuitive situations can stil arise. For example, take the following preference ballots.

We (arbitrarily) claim that an alternative is approved if it did not receive a last-place ranking. So, the scores are a = 5, b = 4, c = 1; a is the winner. Now, suppose two voters dishonestly claim to prefer alternative c to a:

The scores are now a = 3, b = 4, and c = 3. Alternative b wins, and the dishonest voters have achieved a preferred outcome.

Another problem is that the mapping from a voter preference ballot to a set of approved voters is poorly defined. For example, if the last two voters had been honest, but only ‘approved’ of their top-ranked alternative, the vote would have been:

The scores would now be: a = 3, b = 4, c = 1. In this case, alternative b wins, and this change has affected the outcome.

Summary

Bibliography

Philip D. Straffin, Jr. Topics in the Theory of Voting. Boston: Birkhäuser, 1980.

Matt Corks | mvcorksalumniuwaterlooca | Public Key
HTML 4.01 validated