Mathematics of elections

Summary: Mathematics can help explain and predict elections.

Long the domain of economists, political scientists, and philosophers, systems of government has emerged as a field ripe for the application and study of mathematics. Elections are typically classified under an emerging branch of mathematics called “social choice theory,” though there are historical connections and applications in a number of areas, such as combinatorics and probability theory. Economist Duncan Black’s 1958 book The Theory of Committees and Elections is credited with helping to revive modern interest in using mathematics to study election questions.

In a democratic society, such as the United States, elections are the primary vehicle for providing citizens a fair and equal voice in the machinations of federal, state, and local governments. As such, it is fundamentally important that elections be conducted in a manner that is perceived to be fair by the citizenry; that is, a governing body derives its legitimacy from the equitable interpretation and application of the voting power of the public.

Beyond the widely known popular elections (electing the candidate with the most first-place votes) there are a number of alternative voting methods; many of these allow voters to express more information about their preferences of various candidates. Since it is possible for different methods to produce different winners given the same voter preferences, a number of voting properties have been postulated. Each property states a desired outcome or effect that a voting system should express. For example, a voting system should be “anonymous” in that individual voters should be able to exchange ballots without affecting the outcome; in other words, one person’s ballot should not have special significance. A more challenging property is “independence from irrelevant alternatives,” which requires the relative outcome of an election to remain unaffected if candidates are added or removed from consideration (provided this addition or removal does not change the relative way voters feel about the other candidates). Economist Kenneth Arrow demonstrated mathematically in his doctoral dissertation that no voting system can satisfy all the desired properties. Arrow’s Impossibility Theorem was later published in his 1951 book Social Choice and Individual Values.

A particular type of voting system, weighted voting, arises when voters are assigned different numbers of votes. This system is usually employed to reflect a situation where some voters should have greater say or representation than others. The Banzhaf Power Index, named after John Banzhaf, is a tool that elucidates the voting power enjoyed by the voters in a weighted voting scheme and reveals that voting power is not always commensurate with a voter’s number of votes. It is also sometimes called the Penrose-Banzhaf Power Index to include its original inventor, Lionel Penrose.

The U.S. Electoral College, an example of a weighted voting system, is used to elect a winner in U.S. presidential elections. The U.S. Electoral College illustrates a drawback of weighted voting in that a winning presidential candidate may not have received a majority of popular votes. This has sparked much interest in replacing the U.S. Electoral College in favor of the popular vote method but smaller states that enjoy more voting power with the U.S. Electoral College are likely to block attempts at Constitutional reform.

Exit polling, invented by statistician Warren Mitofsky, allows social demographers to understand the dynamics of an election and to predict the winner. Exit polling has become an increasingly important tool for media and news outlets as they scramble to retain and inform viewers on the eve of an important election. A number of studies have investigated the influence of exit polling while an election is taking place; for instance, polls broadcast in real time may influence voters who have yet to vote and hence possibly change the outcome of an election. Exit polling has also garnered interest in recent presidential elections when erroneous predictions caused media sources to prematurely, or incorrectly, identify a winning candidate.

The Ballot Box Problem is an interesting mathematical puzzle, proposed by Joseph Bertrand, which seeks answers about how an election may unfold as ballots are removed from the ballot box and counted. The solution to Bertrand’s theorem is a Catalan number, named for Eugène Catalan. An elegant proof was derived by Désiré André.

Types of Elections

Though most people are familiar with the plurality election (also known as “popular vote”) in which the candidate with the most votes (most first-place votes) wins, there are a number of alternative election methods. One of the most prominent is the Borda method, named for Jean-Charles de Borda, where voters are required to rank all candidates from their first choice to their last; points are then assigned to each candidate based on the candidate’s rank on the each ballot. The sum of a candidate’s total points is used to determine the winner. This method allows voters to specify more information about how they view the candidates, other than merely selecting their favorite.

In the Sequential Pairwise method, two of the candidates vie in a head-to-head competition (an imaginary election with only the two candidates) where the losing candidate is eliminated and the winner proceeds forward to battle another candidate. Again, voters rank candidates in preference listings, which are used to determine the winner between a particular pair of candidates. The winner can be inferred from the preference lists by assuming each voter would select the candidate that is higher on his or her list. A drawback of this method is that the order in which the candidates are selected for the individual competitions can change the ultimate outcome of the election.

A Condorcet Winner is a candidate who beats every other candidate in a head-to-head election. When one exists, a Condorcet Winner will obviously win the Sequential Pairwise election but not all sets of voter preference rankings produce a Condorcet Winner. The method is named for Marie Jean Antoine Nicolas de Caritat, Marquis de Condorcet.

In an Instant Run-off election, a plurality vote is taken and the candidate with the least number of first-place votes is eliminated. Then the election is repeated with the remaining candidates until only one winner remains. Again, voter preference rankings can be used to simulate the repeated elections in order to determine the winner without holding a series of actual elections.

Weighted Voting

Much of rationale behind the U.S. system of government is based on the principle of “one person, one vote” (each citizen should have equal say in the system of government). There are times, however, when it is appropriate to give certain individuals (or groups) more voting power than others. This type of voting system, often called “yes-no voting” or “weighted voting,” occurs when voters are assigned a different number of votes or “weights” to their votes. Elections are between two alternatives; the winner is selected if the vote total exceeds a predetermined threshold. Each voter must use all available votes toward the same candidate or choice votes cannot be split between the candidates or choices.

An example of a weighted voting system was the European Economic Community (EEC) established in 1958 as a precedent to the current European Union. The original six members were assigned votes in proportion to their population size:

A threshold is established to determine the number of total votes necessary to win an election. Though this threshold is often simple majority, in the EEC example, a threshold of 12 (of the total 17 votes) was established to pass certain types of legislation.

An interesting question arises as to the dynamics of weighted voting systems and, more specifically, an entity’s ability to influence the outcome of an election. Several theorists have shown that voting power is not necessarily proportional to an entity’s vote count. For example, it would be misleading to assume that France enjoys 23.5% (4/17) of the voting power in the EEC example.

Banzhaf applied a power index to argue a landmark case in Nassau County, New York, in 1965. His voting power calculations demonstrated the disenfranchisement of certain entities within weighted voting schemes and thus questioned the system’s constitutionality.

Banzhaf’s computation is based upon the notion of a winning coalition (a collection of voters whose vote total exceeds the threshold). Such a coalition (or “voting block”) can win an election by all voting the same way. A voter is critical to a winning coalition if by removing that voter, the coalition no longer exceeds the threshold. A voter’s Banzhaf Power Index (BPI) is related to the number of times that voter is a critical member of a winning coalition.

In the EEC example, France, Germany, Italy, and Belgium form a winning coalition since their vote total of 14 exceeds the threshold of 12. France, Germany, and Italy are all critical members because the coalition ceases to win without their votes. However, Belgium is not a critical member since France, Germany, and Italy together still form a winning coalition. The number of times each voter appears as a critical member of some winning coalition is computed as follows:

Each country’s BPI is the number of times it is critical compared to the total number of critical instances. Here, there are 42 total instances where an entity is critical; Belgium has 6 of them and thus 14.3% (6/42) of the voting power. Thus, Belgium commands 14.3% of the voting power even though it has 11.8% of the votes. In this scheme, Luxembourg has no voting power it is not able to influence the outcome of any possible election. It is common in weighted voting schemes of smaller size (20 or fewer members) for entities with a greater number of votes to possess greater voting power, while small entities (with a fewer number of votes) possess less voting power. As the number of voters increase, voting power tends to better approximate the proportion of votes. But such weighted voting systems are subject to arbitrary swings of voting power as new voters are added or removed, or as seemingly subtle changes to the weights are made.

An equally popular voting power computation was proposed by Lloyd Shapely and Martin Shubik in 1954. Instead of critical members in winning coalitions, their system identifies pivotal voters as the ones who enter a coalition and cast the deciding vote by doing so. A similar calculation ensues in which voting power is correlated with the percentage instances in which each entity plays the pivotal role.

U.S. Electoral College

The voting system responsible for electing the president of the United States, the U.S. Electoral College, is essentially a weighted voting scheme. A state’s electors (or “votes”) arise from the sum of their congressional representation: one vote for each of a state’s two senators and one vote for each representative to the House of Representatives. The District of Columbia receives three electors to form a total of 538 (100 senators, 435 representatives, and three from Washington, D.C.). A presidential candidate needs a majority of the electoral votes at least 270 to claim victory.

Under the electoral college, it is possible that the winning candidate need not garner a majority of first-place votes. In fact, U.S. presidential elections in 1824, 1876, 1888, and 2000 all produced a winner who lost the popular vote total.

Those elections and other issues have created an endless interest in reforming or removing the U.S. Electoral College and replacing it with a popular vote system. As recently as 2004, the Every Vote Counts Amendment proposed to replace the U.S. Electoral College with a popular vote initiative. Such a reform requires a Constitutional change and thus approval of 75% of the states.

It is unlikely such a measure would ever be adopted because small states enjoy significantly more voting power in the U.S. Electoral College than they would in a popular vote system. A state with few votes, such as South Dakota, would likely be ignored by campaigners since the voting population is too small to make a difference under a popular vote election.

The National Popular Vote Compact is an alternative attempt at election reform. In this compact, individual states would cast their electoral votes according to the national popular vote, not simply the tallies within the state. This has the effect of choosing a president elected by popular vote within the Electoral College system and thus bypassing the hurdle of constitutional reform. To date, this compact has been adopted by five states (61 electoral votes) with a number of others considering the compact in state legislature enough states to compile 270 electoral votes would have to sign on to the compact in order to have the intended effect of electing a president by popular vote.

Exit Polling

An important factor associated with elections is the attempt to predict election outcomes through the surveying of voters as they leave the voting areas, a procedure known as “exit polling.” This procedure contrasts with pre-election polls in that actual voters who have (presumably) just cast a vote are being sampled and thus results are typically more accurate than surveying people prior to an election who are “likely” to vote, or who may change their mind between being polled and actually casting a vote.

Although the science of predicting election outcomes has been around as long as elections themselves, it is at the beginning of the twenty-first century with widespread electronic media coverage and more sophisticated polling techniques that exit polling has garnered more national attention. A number of papers have been written about the effects of exit polling being broadcast in real time; the researchers hypothesize that exit polling influences voter behavior primarily by making an election seem closer or not closer than was previously perceived. This effect is especially true in the United States where, as a function of different time zones, voters in western states have access to more complete results of a national election unfolding across the country.

Exit polling has garnered an additional spotlight with the controversial presidential elections of 2000 and 2004. In both cases, especially the 2004 election, exit polling differed significantly from the actual vote tally, causing many media outlets to incorrectly, or prematurely, announce a victor.

Ballot Problem

There are several interesting mathematical puzzles based on elections and voting; perhaps the most well known of them is the Ballot Problem, originally presented by Joseph Bertrand in the late nineteenth century. Consider an election between two people, Alice and Bob, where Alice has received A votes and Bob B votes. Let A>B so that Alice wins the election. The puzzle arises from the counting of the votes: what is the probability that as the votes are pulled randomly from the ballot box and tallied one by one, that Alice and Bob are tied in their vote total at some point after the first vote is read?

The puzzle’s solution is a creative argument based on combinatorics and probability. Sequences, a listing of votes as they are pulled from the ballot box, can be identified as those with ties and those without. The following is a sequence from an election with nine voters (A=5, B=4):

bbabaabaa.

In this sequence, the first tie occurs with the reading of the sixth vote, though there is also a subsequent tie. There is also a “matching” partial sequence in which the a’s and b’s exchange places up through the point of the first tie:

aababbbaa.

Every such sequence of strings that produces a tie somewhere in the intermediate vote tally comes in matching pairs as shown. Out of each pairing, one sequence must start with an a while its match starts with a b. Since Alice wins the election, some of the sequences starting with an a will result in a tie but not all of them. However, every sequence that starts with a b must at some point achieve a tie since ultimately there will be more as than bs. There are three categories of sequences:

• • sequences that start with an a but never have a tie
• • sequences that start with an a and achieve a tie at some point
• • sequences that start with a b and achieve a tie at some point

The probability that any sequence is found starting with a b is

since there are B ballots out of A+B total ballots where a b can be the first vote drawn. There are exactly as many sequences that start with an a and also achieve a tie because each one is matched with exactly one b-starting sequence. Therefore, the probability of reading the votes and achieving a tie along the way is exactly

This problem has spawned a number of related problems with interesting ties to Catalan numbers.

Bibliography

Freeman, Steven F. The Unexplained Exit Poll Discrepancy. Philadelphia: Center for Organizational Dynamics, University of Pennsylvania. 2004.

Hodge, Jonathan K., and Richard E. Kilma. The Mathematics of Voting and Elections. Providence, RI: The American Mathematical Society, 2005.

Sudman, Seymour. “Do Exit Polls Influence Voting Behavior?” Public Opinion Quarterly 50, no. 3 (1986).

Taylor, Alan D. Mathematics and Politics: Strategy, Voting Power, and Proof. New York: Springer-Verlag. 1995.