When there are only two candidates in an election, it is a simple matter to determine the winner--the candidate with the majority of votes. However, when there are three candidates, the situation is much more complicated. We will discuss various ways to determine the winner of an election with three candidates, using interactive mathlets to illustrate some of the ideas developed by Don Saari. While all of these methods are reasonable ways to determine the winner, they will often give conflicting answers. We will also discuss methods for constructing some of these "paradoxical" examples.
This article has several mathlets that use Macromedia Shockwave. Click on the link to download the plug-in.
Published July, 2006. Article ID 1195
Copyright © 2006 by James E. Hamblin
When there are only two candidates in an election, it is a simple matter to determine the winner--the candidate with the majority of votes. However, when there are three candidates, the situation is much more complicated. We will discuss various ways to determine the winner of an election with three candidates, using interactive mathlets to illustrate some of the ideas developed by Don Saari. While all of these methods are reasonable ways to determine the winner, they will often give conflicting answers. We will also discuss methods for constructing some of these "paradoxical" examples.
This article has several mathlets that use Macromedia Shockwave. Click on the link to download the plug-in.
Published July, 2006. Article ID 1195
Copyright © 2006 by James E. Hamblin
Suppose that we have an election with three candidates: A, B, and C. On a standard ballot (like those used in most elections around the world) the three candidates would be listed and each voter would have to choose one. While the voter in this situation has only three choices, there are really six possible preferences that the voter can have. For example, the preference "A>B>C" means that the voter prefers A to B and B to C. In this case the voter would select "A" on the ballot. However, this voter would be unable to distinguish herself from a voter whose preference is "A>C>B."
Why does it matter that voters in these situations cannot express their full preferences? It is especially important in elections where no candidate receives a majority of the votes. For example, in the 1998 Minnesota gubernatorial election, Reform Party candidate Jesse Ventura received 37% of the votes, with the candidates from the other two parties getting 34% and 28%. Even though no candidate received a majority, Ventura received a plurality -- more votes than any other candidate -- and was declared the winner. Should Ventura have won the election? It can be argued that most of the people who did not vote for Ventura would have had him as their third choice. If that were really true, then as many as 63% of the voters had Ventura as their last-place choice. Perhaps if voters in this election had been able to express their full preference, the outcome would have been different.
When we want to describe how many voters have each of the six possible preference orders, we use a diagram developed by Donald Saari [1] called the representation triangle. Each vertex of the triangle is labeled by a candidate, and the six regions of the triangle each represent one of the six preference orders. For example, the region labeled "A>B>C" is the region of points that are closest to A, second-closest to B, and farthest from C. A good way to remember this is that "closer is better": the regions closest to A represent the voters that have A as their top choice, and the regions second-closest to A represent the voters whose second choice is A.
Let's illustrate how the triangle works using an example from [4]. Suppose that the children in a class are trying to decide what kind of drinks they should have during lunch: soda, milk, or juice. The teacher asks the students to rank their preferences in order, and the results are as follows:
Votes | Preference |
---|---|
6 | Milk > Soda > Juice |
5 | Soda > Juice > Milk |
4 | Juice > Soda > Milk |
This voter profile would be represented by the diagram below.
We put a zero in a region whenever the corresponding preference is held by zero voters. In this example, only 3 of the 6 possible preference orders were actually expressed by the students.
The most common method for determining the winner of an election is the one we have already discussed: the plurality method. Voters simply cast a vote for their top preference. The candidate, if any, who receives more votes than any other is the winner. In the diagram below, the plurality totals can be determined by adding up the numbers in the regions corresponding to each candidate. The red regions correspond to A, the blue regions to B, and the green regions to C.
In the interactive mathlet below, you can explore the plurality method by adding and subtracting voters from each of the six regions. In all of the interactive diagrams, left-clicking adds voters and right-clicking subtracts voters.
To see one of the disadvantages of the plurality method, consider the "milk, soda, juice" example above. Milk is the plurality winner because it receives 6 votes, more than any other candidate. But while milk is top-ranked by more children than any other candidate, it is bottom-ranked by all other children. If 9 out of the 15 voters (a clear majority) ranked milk last, should it really be the winner? Perhaps we need a new way to determine the winner in situations like this.
The main disadvantage of the plurality method is that it does not allow each voter to express her full preference order: the top-ranked candidate receives 1 "point" and all other candidates receive 0. In the positional method, the second-ranked candidate receives a fractional amount of votes. We have a parameter s that is between 0 and 1, inclusive, and each voter's three candidates receives 1, s, and 0 points, in order of preference.
When s = 0, the positional method reduces to the plurality method that we have already discussed.
When s = 1, the voter's first and second place candidates both receive an equal vote, and the third place receives zero. In effect, a vote has been placed against the third-place candidate. This method is called antiplurality.
When s = 0.5, the positional method reduces to the Borda count, a method developed by Jean-Charles de Borda in 1770. An equivalent way to perform the Borda count is to assign 2 points for each first-place vote, 1 point for each second-place vote, and 0 points for third-place votes.
In the interactive mathlet below, experiment with changing the value of s. Can you construct profiles where you can change the winner of the election, not by adding or removing voters, but by simply changing the value of s?
Consider another voter profile:
Votes | Preference |
---|---|
6 | A > B > C |
4 | A > C > B |
0 | B > A > C |
8 | B > C > A |
3 | C > A > B |
4 | C > B > A |
Who should win this election? We will analyze this election using the positional method, but we will not choose a value of s right away.
Preference | A | B | C |
---|---|---|---|
A > B > C | 6 | 6s | 0 |
A > C > B | 4 | 0 | 4s |
B > A > C | 0 | 0 | 0 |
B > C > A | 0 | 8 | 8s |
C > A > B | 3s | 0 | 3 |
C > B > A | 0 | 4s | 4 |
Totals | 10 + 3s | 8 + 10s | 7 + 12s |
Performing the calculations this way allows us to easily change the value of s and determine if the winner of the election changes. In this example, for different values of s, any of the three candidates could win this election:
s | A | B | C |
---|---|---|---|
0.1 | 10.3 | 9 | 8.2 |
0.4 | 11.2 | 12 | 11.8 |
0.8 | 12.4 | 16 | 16.6 |
So which candidate should win? In this case there is no easy answer.
In the late 1700's, the Marquis de Condorcet proposed an alternative to the voting method put forth by Jean-Charles de Borda. Since there can be no confusion as to the winner of a two-way election, Condorcet's idea was to consider all possible pairwise elections among the candidates.
Recall the "milk, soda, juice" example. If we hold an election between just milk and soda, the 6 voters that have milk top-ranked vote for milk and the 5 voters that have soda top-ranked vote for soda. The 4 remaining voters have juice top-ranked, but they can't vote for juice. Instead they have to vote for their second choice, soda. Thus soda wins the milk versus soda election by a score of 9 to 6. The other pairwise elections are shown below.
Milk versus Soda | Milk versus Juice | Soda versus Juice |
Soda wins 9-6 | Juice wins 9-6 | Soda wins 11-4 |
---|
Notice that, using the representation triangle, it is easy to add up a candidate's score in a pairwise election. Simply divide the triangle in half between the two candidates and add up the numbers on each side.
If one candidate wins all of the pairwise elections he is involved in, we call that candidate the Condorcet winner. If a candidate loses all of the pairwise elections he is involved in, that candidate is the Condorcet loser. In our example, soda wins both of its pairwise elections, so soda is the Condorcet winner. Since milk loses both of its pairwise elections, milk is the Condorcet loser.
Unfortunately, sometimes pairwise elections do not give us a decisive winner. Consider the following profile:
Votes | Preference Order |
---|---|
12 | B > C > A |
11 | A > B > C |
5 | C > B> A |
4 | A > C > B |
4 | C > A > B |
0 | B > A > C |
If we look at pairwise elections in this profile, we find that A beats B (19-17), B beats C (23-13), and C beats A (21-15). So in this example there is no Condorcet winner or Condorcet loser. We say that instead there is a Condorcet cycle.
In the interactive mathlet below, explore pairwise elections and the Condorcet winner. Although it seems natural to look at pairwise elections when there are more than two candidates, these elections can often yield no result, forcing us to consider an alternative way to determine a winner.
Instead of adding voters one at a time to the six regions of the representation triangle, we can make many interesting observations by adding voters as a group, or shifting voters' preferences in specific ways. We can think of this as adding two six-dimensional vectors:
Adding a negative numbers reduces the number of voters with that preference, whereas adding a positive numbers increases the number of voters with that preference. Naturally, adding or subtracting voters in this way can change the winner of the election. For the original triangle in the example above, the Condorcet winner was B, but after applying the changes the Condorcet winner is now A.
The triangle below is represented by the vector (u, v, w, x, y, z).
We want to think about ways that we can add or shift voters that are not just random. For example, if a vector represents a "tied" vote in some way, then adding this vector to a profile vector should not change the outcome corresponding to the profile. In addition, we are interested in a basis for the vector space of all voter profiles, since this will give us a way to decompose profiles and understand how the various methods for selecting a winner apply.
In this section we present a basis for this vector space from [1]. Each vector is given as a representation triangle, and the effects on the positional and Condorcet methods of adding this vector are discussed.
The kernel vector is K = (1, 1, 1, 1, 1, 1). Adding K to a profile adds one voter to each of the six preference orders.
The Condorcet vector is C = (1, −1, 1, −1, 1, −1). Adding C to a profile adds a voter to preferences A > B > C, B > C > A, and C > A > B, and deducts a voter from the reverse preferences C > B > A, A > C > B, and B > A > C.
The vectors Reversal A, Reversal B,and Reversal C are defined by RA = (1, 1, −2, 1, 1, −2), RB = (−2, 1, 1, −2, 1, 1), and RC = (1, −2, 1, 1, −2, 1).
The reversal vector for a candidate corresponds to splitting two second-place votes for the candidate into a first and third-place vote. For example, adding RA to a profile deducts 2 votes each from the two preferences where A is second-ranked, and adds one vote each to the remaining four preference orders.
Note that RC = −(RA + RB). So we need only include RA and RB in our basis.
The vectors Basic A, Basic B, and Basic C are defined by BA = (1, 1, 0, −1, −1, 0), BB = (0, −1, −1, 0, 1, 1), and BC = (−1, 0, 1, 1, 0, −1).
Addition of a candidate's basic vector to a profile shifts one vote each from the two preference orders where the candidate is lowest-ranked to those in which she is highest ranked.
Note that BC = −(BA + BB). So we need only include BA and BB in our basis.
The set {K, C, RA, RB, BA, BB} forms a basis for the six-dimensional vector space of voter profiles. Note that with the exception of the kernel vector, the entries of all of these vectors sum to zero. Hence we can think of these vectors as representing a shift in voter preference that does not change the total number of votes.
In the interactive mathlet below, experiment with creating profiles by adding or subtracting these basis vectors. Notice that repeatedly adding K or any of the reversal vectors does not change the Condorcet winner. Notice that repeatedly adding K or C does not change the positional outcome. Finally note that repeatedly adding a basic vector will eventually make that candidate the winner of both methods.
Many interesting examples come from voter profiles where one candidate wins using one method, but loses using a different method. How can we use these vector ideas to construct such examples?
Suppose that you want to construct an example in which A wins the positional method with s = 0.7, but B is the Condorcet winner.
In general, there are two ways to make A win the positional method with s = 0.7: add copies of Basic A or subtract copies of Reversal A (since s > 0.5). Since copies of Basic A would also make A the Condorcet winner, we will choose to subtract Reversal A. Follow these steps to construct the example.
By understanding the effect that each vector has on each election method, we can easily construct many examples of "paradoxical" elections. We can also use linear algebra techniques to decompose a given profile relative to the six basis vectors. Profiles with Condorcet cycles will have a large C component. Profiles with candidate B winning all of the election methods will have a large BB component, and so on.
When there are more than three candidates, we can still use many of the methods we have described.
As with three candidates, all of these methods can yield ambiguous results. We typically focus on three candidates because this case is sufficient to illustrate the voting "paradoxes" that we have seen.
The triangle diagram does not easily generalize beyond three candidates. With four candidates, for example, it is natural to start with a tetrahedron and slice it up into 24 solid regions: one for each possible preference order.
However, this three-dimensional diagram would be very difficult to interpret, so it would be nice to find a two-dimensional representation. In [2], Saari explains how to "unfold" this tetrahedron, obtaining the diagram shown below.
In this diagram, we still use the rule of thumb that "closer is better": the regions that are closest to the point labeled A represent the voters who have A as their top choice. For example, the region marked with an "x" in the diagram above consists of points that are closest to A, second closest to B, next closest to D, and farthest from C. So this region represents the preference A > B > D > C.
To compute the plurality winner using this diagram, we simply need to add up numbers in the appropriate regions. In the diagram below, each region is marked with a dot indicating which candidate is top-ranked by the voters in that region.
Similarly we can locate the regions where each candidate is ranked second and third and use this to compute the positional winner, as described above.
There are many ways to determine a winner in an election with three candidates. These methods include the standard plurality method and the Borda and Condorcet methods developed in the late 18th Century. Representing the information in voter profiles graphically allows us to understand these methods in an intuitive way. In addition, we can use ideas from linear algebra and vectors to construct interesting examples that illustrate situations where these methods give conflicting results. For more information on the mathematics of voting and elections, please see the references.