Mathematics of Voting

A hypothetical Electoral College problem, in which people overall vote one way, but their representatives vote another way. Retrieved from [1].

Voting, from a mathematical perspective, is the process of aggregating the preferences of individuals in a way that attempts to describe the preferences of a whole group. This can be either for voting on a single best option--such as which restaurant you and your friends would like to go to--or determining who should be let in to a small group of decision makers--such as deciding how many seats should go to students, faculty, and administration on a university's decision board.

Formalizing what it means for the preferences of individuals to be aggregated in a way that most fairly represents the desires of the group turns out to be extremely difficult. A number of surprising results in the field of social choice theory known as "impossibility theorems" show that our notions of "fairness" are often incompatible. Being fair in one way can preclude being fair in another. Whether or not voting systems are fair also depends on the way in which votes are taken: for instance, one could describe just their top choice, rank all their choices in order, or give scores to each of the possible options.

Many voting systems are not particularly robust, in the sense that they can be susceptible to changes in aggregate preference in nonobvious ways when a small number of voters change preferences. Below, one surprisingly strong voting method and several related paradoxes in the mathematics of voting theory are discussed.

The Condorcet method is a robust method for determining aggregate preference from individual preference which works by taking every possible comparison between two choices, finding the victor, and then chaining the pairwise results together to form an overall ordering.

Specifically, let there be a set of voters \(V\) and a set of options \(O\) to vote on. Each voter \(v \in V\) defines their individual preference ranking on the set \(O\). This means that for any \(o_1, o_2 \in O\), either \(o_1 \geq o_2\) or \(o_2 \geq o_1\). For example, if Alice is voting between getting apples, bananas, or cantaloupes at the store, and she prefers cantaloupes to bananas and bananas to apples, she would express these facts as "cantaloupes \(\geq\) bananas" and "bananas \(\geq\) apples." Furthermore, this ordering must obey the transitive rule. If \(o_1 \geq o_2\) and \(o_2 \geq o_3\), then it must be true that \(o_1 \geq o_3\). In the previous example, Alice's stated preferences imply that she must also have the preference "cantaloupes \(\geq\) apples."

Once each voter specifies their preference, every pair of options in \(O\) is compared, counting the number of times each voter preferred one over the other. If 5 voters prefer \(o_1\) to \(o_2\) and 3 voters prefer \(o_2\) to \(o_1\), then the aggregate preference for that pair is \(o_1 \geq_{agg} o_2\). The overall aggregate preference is found by taking these individual comparisons and using the transitive rule to figure out the rest of the implied preferences.

Alice, Bob, and Carol are voting on what topping to get for their pizza. They only have enough money to get one topping, and the pizza place is low on supplies so they can only decide between Anchovies, Broccoli, and extra Cheese. They vote and find their preferences are as follows:

• Alice: Broccoli \(\geq\) Cheese \(\geq\) Anchovies
• Bob: Broccoli \(\geq\) Anchovies \(\geq\) Cheese
• Carol: Anchovies \(\geq\) Cheese \(\geq\) Broccoli.

Comparing each of the options pairwise gives

• Broccoli \(\geq_{agg}\) Anchovies (2 to 1)
• Anchovies \(\geq_{agg}\) Cheese (2 to 1)
• Broccoli \(\geq_{agg}\) Cheese (2 to 1).

Using the transitive rule, the full ordering is

• Broccoli \(\geq_{agg}\) Anchovies \(\geq_{agg}\) Cheese.

Given this example, it seems reasonable to use the transitive rule on the aggregate preference, since each individual preference is assumed to be transitive. However, this is not the case.

Alice, Bob, and Carol run into the same conundrum the next day, but their preferences have changed. They take a new vote and find

• Alice: Anchovies \(\geq\) Broccoli \(\geq\) Cheese
• Bob: Broccoli \(\geq\) Cheese \(\geq\) Anchovies
• Carol: Cheese \(\geq\) Anchovies \(\geq\) Broccoli.

Comparing each of the options pairwise gives

• Anchovies \(\geq_{agg}\) Broccoli (2 to 1)
• Broccoli \(\geq_{agg}\) Cheese (2 to 1)
• Cheese \(\geq_{agg}\) Anchovies (2 to 1).

This set of orderings is cyclic. Attempting to use the transitive property would result in saying that both Anchovies are better than Cheese and Cheese is better than Anchovies, meaning that Cheese and Anchovies must be identical (an assertion that any chef would scoff at). The fact that transitive individual preferences can result in cyclic aggregate preferences is called Condorcet's paradox.

Three desirable features for a voting system are as follows:

• Unanimity: If everyone prefers \(A\) to \(B\), \(A\) should win.
• No Dictators: There should not be anyone whose individual preferences always determine who wins.
• Independence of Irrelevant Alternatives (IIA): Adding extra options should not make existing relations change. That is, if \(A \geq B\), adding option \(C\) should not make \(B \geq A\).

Independence of irrelevant alternatives is an important criterion since ideally a voting system will not be susceptible to strategic voting, in which voters will rank options in ways that do not reveal their true preferences so as to attempt to make sure their top choice is elected.

Arrow's Impossibility Theorem

It is impossible to fulfill all of the three above features (Unanimity, No Dictators, IIA) at the same time in any ranked voting system.

Voter profiles and the resulting aggregate preferences [2]. Consider a vote with \(N\) voters and three options \(A\), \(B\), and \(C\). In the diagram to the right, it is shown that given unanimity and independence of irrelevant alternatives, one of the voters must be a dictator [3].

If everyone individually votes \(B\) as the worst option, then by unanimity, \(B\) is the aggregate worst option. This is profile \(0\) in the diagram. Similarly, if everyone thinks \(B\) is the best option, then \(B\) is the aggregate best option. This is profile \(N\). Between \(0\) and \(N\) are profiles \(i\) where the first \(i\) people vote \(B\) as best, and \(N - i\) people vote \(B\) as worst. At one of these values, the aggregate ranking must switch so that \(B\) is the aggregate best. Let this switching value be \(k\), the pivotal voter for \(B\). If \(k\) ranks \(B\) first, then \(B\) wins, and if \(k\) ranks \(B\) last, then \(B\) does not win.

The rest of the proof demonstrates that, if unanimity and independence of irrelevant alternatives hold, then voter \(k\) always determines the outcome of the vote. That is, voter \(k\) is a dictator.

First, consider the case where \(k\) ranks \(A\) over \(C\), and all other voters have some arbitrary ranking. Now, for \(k\), move \(A\) to their first preference and \(B\) to their second. By IIA, this can't change the aggregate ranking of \(A\) versus \(C\). Similarly, for voters \(0\) through \(k-1\), move \(B\) to their first preference, and for voters \(k+1\) through \(N\), move \(B\) to their bottom preference. Again, by IIA, this can't change the ranking of \(A\) and \(C\).

Now all voters \(0\) through \(k\) prefer \(A\) to \(B\) and all voters \(k+1\) through \(N\) prefer \(B\) to \(A\). By the definition of \(k\), that means the aggregate preference must be \(A > B\). Similarly, all voters \(0\) through \(k\) prefer \(B\) to \(C\) and all voters \(k+1\) through \(N\) prefer \(C\) to \(B\). By the definition of \(k\), that means the aggregate preference must be \(B > C\). By transitivity, the overall preference must be \(A > C\). Therefore, \(k\) is a dictator. \(_\square\)

Arrow's theorem seems to put a nail in the coffin for fair voting systems, but it only does so for systems where preferences must be simply ranked, and not scored. If voters can say, for instance, that they prefer \(A\) 10 times more than \(B\) and \(C\) 1.1 times more than \(A\), then these results need not hold.

The number of representatives assigned to US states after the 2010 census [4]. Whereas Arrow's theorem states impossibility results for the preferences over a set of particular candidates, the apportionment paradox makes similar statements for fairly dividing up a number of discrete seats to different groups.

Representative democracy is a form of government in which, instead of having every individual vote on every issue (direct democracy), individuals instead elect a small number of representatives to vote in their interests. The apportionment paradox is an impossibility theorem for choosing the number of representative seats to be assigned to each group. In countries with party-list proportional representation, the groups are political parties. Each party gets a number of seats that is a function of the number of people voting for that party. In the United States, the groups are states. The number of seats they get in the House of Representatives is a function of the population of the state. Residence in a state is a “vote” for a seat for that state (in a sense separate from the actual votes for what candidates will fill the seats given to the state).

Ideally, when making a fair division, the number of seats assigned to each group would be directly proportional to the number of votes (or state population, in the U.S.). For instance, if there are 10 seats available and 57% of people vote for group \(A\), 24% vote for group \(B\), and 19% vote for group \(C\), they would get 5.7, 2.4, and 1.9 seats respectively. However, if seats cannot be divided into fractions (as is usually the case), then a decision process is needed to assign individual seats. An ideal assignment system would obey the following three rules:

1. Quota rule: each group gets a number of seats equal to its proportion of the vote either rounded up or rounded down. \((\)In the example, the seats would be 5 or 6 to \(A,\) 2 or 3 to \(B,\) and 1 or 2 to \(C.)\)
2. If the total number of seats is increased, the number assigned to any group doesn’t decrease.
3. If group \(A\) gets more votes than group \(B\), no seats are transferred from \(A\) to \(B\).

If there are only two groups, it is possible to fulfill all these criteria by assigning seats directly proportional to the number of members of each group. However, if there are three or more groups, the apportionment paradox states that it is impossible for all of these rules to be satisfied at the same time.

The Alabama paradox is an example of a violation of rule 2. In 1880, the U.S. House of Representatives realized that if they had 299 seats, Alabama would be assigned 8, but if they had 300 seats, Alabama would be assigned 7 [5].

Divisor methods are a class of assignment rules that obey criteria 2 and 3, but violate the quota rule.

The method begins by calculating a divisor \( D \) by taking the total population divided by the number of seats.

Then the quota \( Q_{state} \) for each state (or district, or whatever is being used) is calculated by taking the total population divided by the divisor \( D \). Note that in perfect circumstances, the quotas would then all be round numbers and the assigning would be done; handling the fractional part of the quotas is where the paradox arises.

There are multiple methods of handling the fractional parts for each \( Q_{state} \). One method (Hamilton's) rounds all quotas down, and then assigns any remaining seats one-by-one in order from largest fractional part to smallest.

Another approach, known as d'Hondt's method or Jefferson's method, is to keep reducing the value of \( D\) so that when all the quotas are rounded down, the quotas add together to the correct number of seats.

The current method in use by the US House of Representative is known as Huntington-Hill. Each \( Q_{state} \) is temporarily rounded down (call this value \( n ),\) but then this value is compared against the geometric mean of \( n \) and \( n + 1 \):

\[ \sqrt{(n)(n + 1)}. \]

If \( Q_{state} \) is greater than the geometric mean, then \( Q_{state} \) is rounded up; otherwise it is rounded down.

Just like d'Hondt's method, \( D \) may need to be adjusted to ensure all the quotas together add to the correct number of seats.

In the same way that a nation is divided into states, states are divided into districts, each of which votes on a particular candidate. Candidates are elected by counting the number of districts they win, under the assumption that winning the most districts is the same as winning the overall vote. However, it is possible for one candidate to win in most districts while still losing the popular vote. Gerrymandering refers to the practice of purposefully redrawing district lines so that one candidate is more likely to win.

Also present in voting is Simpson's paradox in statistics, which says it is possible for variables to be positively correlated in subgroups despite being negatively correlated overall.

[1] Image retrieved on 1 Mar 2016 from https://en.wikipedia.org/wiki/Electoral_College_(United_States)#/media/File:PopWinnerLosesElecVote.png

[2] By Nilesj - Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=27989711.

[3] Quint, Dan. Lecture 2: Arrow's Impossibility Theorem. 2014. Retrieved on 7 Mar 2016 from http://www.ssc.wisc.edu/~dquint/econ698/lecture%202.pdf

[4] Image retrieved on 1 Mar 2016 from https://en.wikipedia.org/wiki/United_States_congressional_apportionment#/media/File:2010_census_reapportionment.svg

[5] Apportionment Paradoxes. Retrieved from http://www.ctl.ua.edu/math103/apportionment/paradoxs.htm on 1 Mar 2016.