Mathematics of voting

Summary: Social choice theory concerns itself with the mechanics of group decisions such as elections and the impact methodology can have.

Voting theory (also known as “social choice theory”) is concerned with how group decisions are made when there are a number of alternatives from which to choose (for example, finding the winner of an election). When there are only two options, voting is straightforward—the winning alternative (also called the “social choice”) should be the one that receives the most votes. However, when the choice is among three or more alternatives, determining the social choice is significantly more complex. There are many reasonable methods for selecting a winner and the methods can produce different winners even when given the same sets of votes. All voting methods have inherent flaws and, regardless of the method used, strange and paradoxical situations can occur. For example, in the 2000 U.S. presidential election, George W. Bush and Al Gore were major party candidates, while Ralph Nader, representing the Green Party, had much less support. Although Bush won the election, exit polls at the time indicate that had Nader not been on the ballot in some states, Gore almost surely would have won the election. In other words, in the U.S. electoral system, the presence (or lack thereof) of an “also-ran” candidate can have a profound outcome on the winner. This disturbing property is one of many that interests mathematicians, economists, and political scientists who study voting theory.

Preference Ballots

Preference ballots, where voters rank the alternatives in order of preference, are among the most useful ways of gathering information from voters. A voting method aggregates these preferences in some way and determines a social choice (or choices, in the case of ties). In this way, a voting method can be thought of as a function whose typical input is a set of individual ballots and whose output is the winning alternative, or—in the case of a social welfare function—a ranking of the alternatives, perhaps with ties. Many such functions are possible:

• Plurality method: A procedure that returns as the social choice the alternative that is the top preference on the most ballots (the candidate with the most first place votes).
• Weighted voting method: Also called the “positional method,” this process assigns points to an alternative based on its position on a ballot, with higher placings on a ballot earning more points. The winning alternative is the one having the most points.
• Borda count: A special positional method whereupon a voter’s lowest-ranked alternative earns zero points, the voter’s second lowest-ranked alternative earns one point, and so on, with the voter’s top choice earning n-1 points, assuming n candidates.
• Hare system: Also called “instant runoff voting” or “plurality with elimination,” this method arrives at the social choice by successively eliminating less desirable outcomes. In this procedure, ballot-counting proceeds in rounds, with the candidate having the fewest first-place votes eliminated at the end of each round. A ballot on which an eliminated candidate was the top choice has its vote transferred to the highest ranking remaining candidate on the ballot. The process of elimination continues until one candidate has more than half the first place votes (a “majority”), in which case that candidate is declared the winner.
• Dictatorship: In a dictatorship, one voter is specially designated so that the social choice is always the alternative that this voter has at the top of his or her ballot.

For example, suppose that there are 100 voters in an election, and three candidates (A, B, and C). Suppose that the voters express their votes as shown in the following table:

Note that 40 of the voters prefer A as their top choice, 35 prefer B as their top choice, and 25 prefer C as their top choice. If this election were decided using the plurality method, then candidate A would win with 40 first place votes (with B and C earning 35 and 25 first place votes, respectively). Using the Borda count, A would tally 40×2=80 points, B would earn (35×2)+25=95 points, and C would win with (25×2)+75=125 points. Using the Hare system, candidate C would be eliminated in Round 1, and C’s votes would transfer to candidate B, because B is second on all 25 ballots. In Round 2, B has 60 first place votes to A’s 40, so B is the winner.

This example demonstrates that different methods can yield different results. As Donald Saari writes, “Rather than reflecting the voters’ preferences, the outcome may more accurately reflect which election procedure was used.”

It should be noted that there are other methods of voting that do not require preference ballots. In a system called “approval voting,” a voter may vote for as many candidates as desired. The winner is the candidate receiving the most votes. No distinction is made among the candidates of which the voter “approves,” and the voter can vote for any combination of the candidates.

Fairness

By aggregating voters’ preferences and producing a social choice, an election method should reflect, in some way, the will of the people. Given the vast library of possible election methods, it is natural to ask whether there is a method that captures this will in an ideal way. Social choice experts have developed different ways of assessing the quality of voting methods, and the notion of “fairness” has emerged as a prime consideration. When there are two alternatives, it can be expected that any reasonable voting method will be anonymous (all voters are treated equally), neutral (the two candidates are treated equally), and monotonic (if a voter changes his vote from candidate A to candidate B, then that should not hurt candidate B). Mathematician Kenneth May proved in 1952 that if the number of voters is odd and ties are not allowed, then only one voting method is anonymous, neutral, and monotonic: “majority rule,” the procedure where the candidate with more than half the first place votes is declared the winner.

When there are three or more alternatives, there are many desirable properties for voting methods. The following list of criteria is far from exhaustive:

Majority criterion: This method requires that when some alternative is the first choice on more than half the ballots, that alternative should be the social choice. The plurality method satisfies this criterion, for if a candidate has a majority, no other candidate can have as many first place votes. On the other hand, the Borda count violates the majority criterion, for there are elections where a candidate can have a majority but still lose.

Condorcet winner criterion: This is a slightly weaker condition: if an alternative is preferred head-to-head over every other alternative in a one-on-one matchup that ignores the other alternatives, then that candidate should win the election. The example above shows that the plurality method violates this criterion. While candidate C is preferred over A on 60 of the ballots, and C is preferred over B on 65 of the ballots, C loses the plurality election to A. The Hare system and the Borda count fail the Condorcet winner criterion as well.

Pareto condition: This method asserts that for every pair x and y of candidates, if all voters prefer x to y, then y should not be a social choice. This is a relatively weak criterion, and all of the methods described above satisfy it.

Monotonicity criterion: According to this method, if x is a social choice and someone changes a ballot in such a way that x is moved up one spot (in other words, x exchanged with the alternative immediately above x on the ballot), then x should still be a social choice. In other words, making a change to a ballot that is favorable only to a winning candidate should not hurt the candidate. The plurality method and the positional voting methods satisfy monotonicity, but the Hare system does not.

Independence of Irrelevant Alternatives: Also called “binary independence,” this method states that if x is a social choice while y is not, and if a voter changes a ballot in a way that does not change the relative positions of x and y on the ballot, then y should still not be a social choice. In other words, changing the positions of other “irrelevant” candidates on a ballot should not affect the relative position of x over y or y over x in the outcome. This is precisely the difficulty that occurred in the 2000 U.S. presidential election, where Nader’s presence in the election affected the relative rankings of Bush and Gore.

Although each of these criteria is, in turn, a reasonable expectation of a voting method, Kenneth Arrow, in 1952, proved the mutual exclusivity of them. In his “impossibility theorem,” Arrow showed that if there are at least three alternatives and a finite number of voters, then the only social welfare function that satisfies both the Pareto condition and “independence of irrelevant alternatives” is a dictatorship. This profound result, which earned Arrow the Nobel Prize in Economics in 1972, argues against the possibility of a theoretically perfect democracy. Nevertheless, Arrow himself encourages continuing to search for voting methods that work well most of the time. He writes:

My theorem is not a completely destructive or negative feature any more than the second law of thermodynamics means that people don’t work on improving the efficiency of engines. We’re told that you’ll never get 100% efficient engines… It doesn’t mean you wouldn’t like to go from 40% to 50%.

Sincere and Strategic Voting

Strategic voting is the practice of voting against one’s true preferences in order to achieve a better outcome in an election. This contrasts with sincere voting, where one votes according to one’s true preferences. Strategic voting most often occurs in situations where a voter’s preferred candidate has little chance of winning, or where the voter’s top candidate is most threatened by his second or third candidate. While strategic voting can affect the outcome of an election, its effects can be disastrous. Election results should reflect the aggregate will of the people, and if voters do not express their individual preferences truthfully, then the voting method has little hope of determining the socially desired outcome. Therefore, voting methods that tend to encourage strategic voting are unattractive. It should be noted that for strategic voting to be at all effective, there must be at least three candidates in the election, and the voters need a thorough understanding of both the voting method being used and the preferences of other voters.

For example, in the 2000 election, exit polls in Florida indicated that Nader voters widely supported Gore as their second choice, far beyond both the margin of error of the polls and Bush’s margin of victory. Had these voters instead voted strategically for Gore, Gore would likely have carried Florida and its 25 electoral votes, thereby winning the presidency. The U.S. electoral college notwithstanding, this shows how powerfully the plurality method encourages strategic voting. Had the 2000 election been decided by the Borda count, one could imagine that a conservative voter might have Bush as the top choice, Gore as the second choice, and Nader last, but might insincerely rank the candidates in the sequence Bush, Nader, Gore in an attempt to maximize the point differential between Bush and Gore.

Some voting methods prove resistant to strategic voting. One of the major advantages of the Hare system is that it tends to encourage sincere voting. In the 2000 election, for example, a Nader supporter would have less reason to vote strategically for Gore if it is known that the vote will transfer to Gore should Nader be eliminated. Nevertheless, there are situations where even with the Hare system, strategic voting can prove beneficial to a voter.

In the 1970s, Allan Gibbard and Mark Satterthwaite proved that no voting method is completely immune to strategic voting. Any non-dictatorial system that uses preference ballots and allows at least the possibility of any candidate winning will necessarily lead to situations, however hypothetical, where strategic voting can be beneficial. This proof serves as a result analogous to Arrow’s, but in the realm of strategic voting. As with Arrow’s result in fairness, it is important to note that the degree to which a voting method encourages sincerity still serves as an important criterion for selection.

Bibliography

Brams, Steven. Mathematics and Democracy: Designing Better Voting and Fair-Division Procedures. Princeton, NJ: Princeton University Press, 2007.

Saari, Donald. Basic Geometry of Voting. New York: Springer, 2003.

Taylor, Alan, and Allison Pacelli. Mathematics and Politics: Strategy, Voting, Power and Proof. New York: Springer, 2008.