Dictatorships Are Not the Only Option An Exploration of Voting Theory

Dictatorships Are Not the Only Option: An Exploration of Voting Theory 2014 Abstract The field of social choice theory, also known as voting theory, examines the methods by which the individual preferences of voters are compiled into a single social preference. These social preferences form the results of elections, ranging from choices as mundane as deciding which movie a group of friends should watch to the far more consequential elections of presidents and prime ministers. This paper explores multiple types of election methods and the unexpected problems that arise from each type of method. Including an analysis of Arrow’s Theorem, one of the main results of social choice theory, from both a combinatorial and geometric perspective, this paper offers a brief introduction to multiple aspects of this relevant and important field. 1 Introduction Social choice theory is a field of mathematics aimed at analyzing the methods through which individual choices are merged to create a single preference that represents the collective choice of all individuals. This field is also called voting theory. As implied by this alternate name, voter’s choices often take the form of preferences of candidates for an election. This paper focuses on this type of preference and introduces some of the fundamental problems that arise within both common and uncommon systems for determining the winner of an election. While most of the systems employed by governments, committees and other groups of people to determine the outcome of an election seem to accurately determine the inclination of the voters, at times their the accuracy of these methods seem more questionable. Consider, for example, the 2000 United States presidential election. George W. Bush and Albert Gore were the main candidates in this election, but Ralph Nader also played an important role. Even though President Bush won the election, many questioned the accuracy of this result, particularly in the controversial Florida vote. Since many of the voters who voted for Nader preferred Gore to Bush [9], questions arose as to whether the majority of voters would have been happier if Gore had won instead of Bush. Election results such as these make voters question the efficacy of existing systems of voting and motivate further research into social choice theory. Social choice theory provides crucial insight into the actual accuracy of different systems that determine election outcomes. This paper provides an overview of several components of voting theory, with a focus on evaluating these voting methods. While delving into other aspects of the field, much of the content of this paper centers on the important work of Donald G. Saari. This paper relies on some knowledge of combinatorics and linear algebra, particularly for the proofs of Arrow’s Theorem. However, most of this paper is accessible to audiences without a background in these fields. Uncertain results such as the 2000 presidential election form voting paradoxes. These paradoxes, other unexpected results, and complexities of voting form the content of Section 2. Arguably the most important result in voting theory, Arrow’s Theorem, is explored in depth in Section 3. In addition to stating the theorem, this section provides several proofs of the result and examines it through the perspectives of combinatorics 1 and linear algebra. Section 4 examines the ways of implementing voting dictionaries to compare different voting methods. Section 5 assesses the possibility of successfully finding a compromise that will satisfy the most voters within a society . The final section offers some potential avenues for further research within this field and recommendations for accurately determining the outcome of an election. 2 2.1 Voting Paradoxes The Method Chooses the Winner Edward B. Burger and Michael Starbird present multiple methods of voting and the flaws that attend each of these methods in their 2005 book, The Heart of Mathematics: An invitation to effective thinking [5]. In particular, Burger and Starbird demonstrate that the choice of voting method can have a greater influence on the outcome of the election than the votes themselves. We begin delving into this topic by introducing and considering several voting methods. Definition 2.1.1 (Plurality Voting). Each voter votes for a single candidate and the candidate with the most votes wins. Plurality voting provides the basis for the electoral college system used for presidential elections in the United States. Under this system, if there are three or more candidates, it is possible to elect a candidate who would have lost in a head-to-head competition with one of the other candidates. For example, returning to the 2000 presidential election, the electoral college system led to George W. Bush’s victory. Yet, Al Gore would have won in a head-to-head competition against either Bush or Nader. Definition 2.1.2 (Vote-for-Two). Each voter votes for two candidates and the candidate with the most votes wins. The difference between the plurality voting method and the vote-for-two method lies in the number of candidates a voter can select. The vote-for-two method and the plurality vote are just different k values for the vote-for-k type of election method. As plurality voting and vote-for-two allow a voter to vote for one and two candidates respectively, the remaining method that we will consider in this section is a different type of method that allows each voter to consider all of the candidates. This final method is commonly analyzed in voting theory and is used for certain elections in the Republic of Nauru and the Republic of Kiribati [7]. Definition 2.1.3 (Borda Count). Suppose there are n candidates. Each voter ranks the candidates such that they give their favorite candidate one point, their second favorite candidate two points, . . ., and their nth favorite candidate n points. The candidate that receives the smallest total number of points wins. Each of the discussed voting methods are valid democratic processes of determining the winner of an election. However, in certain cases each method chooses a different candidate. To demonstrate this we present a scenario similar to the elementary school election scenario included in Burger and Starbird’s text. Suppose that a town is voting to decide if they should build a new bridge. The town has three different proposals: Proposal A is against building the bridge, Proposal B is to build a basic bridge and Proposal C is for creating a complex bridge that will cost more but last longer. The majority of the town is for constructing a bridge and most of these citizens prefer Proposal C. At the same time a sizable contingent of the town does not want to spend the construction costs for any new bridge and is for Proposal A. Observe how, if put to a vote, the method of voting completely determines the outcome. If the town uses plurality voting, then the voters interested in building the bridge will be split between Proposal B and Proposal C. As a result Proposal A is accepted. If instead the town uses the vote-for-two method, the majority of the people will choose proposals B and C to ensure that a bridge is built. Since Proposal B costs less than Proposal C, the townsfolk against building the bridge would be more inclined to vote for proposals A and B. Consequently, Proposal B is selected. Finally, if the town uses the Borda count method then the most common ranking would be a one for Proposal C, two for Proposal B, and three for Proposal A. As a result, this could lead to Proposal C being chosen. Hence, it is the choice of method, rather than the individual votes, that selects the winner in this scenario. 2 Voter 1 2 3 Outcome {A, B} AB BA AB AB {B, C} BC BC CB BC {A, C} AC CA CA CA Table 1: Cycle of votes representing Condorcet’s paradox. Voter 1 2 3 Outcome Proposition 1 Yes No Yes Yes Proposition 2 Yes Yes No Yes Decision Yes No No No Table 2: Example of List’s paradox. 2.2 The Same Paradox Three Times Over In Donald G. Saari’s 2008 book Disposing Dictators, Demystifying Voting Paradoxes: Social Choice Analysis [9], Saari explores multiple paradoxes found in voting systems. In particular, he demonstrates the parallels between the work of Christian List and his coauthors, Elizabeth Anscombe and Marquis de Condorcet. Saari argues that by changing the presentation of their results, the works of List and Anscombe can be viewed as special cases of Condorcet’s work. To demonstrate this we introduce the paradoxes relevant to this argument. We start by introducing Condorcet’s work. Condorcet believed that the best voting system would be determined by majority voting across pairs of candidates. As such, the Condorcet winner is the candidate that receives the majority of votes across all pairings, while the Condorcet loser is the candidate that loses in each head-to-head pairing. While exploring the possible outcomes of using such a method, Condorcet considered the following scenario: suppose there are three candidates, namely A, B and C, and three voters. The ranking of the candidates according to the first voter is A  B  C, the second voter’s ranking is B  C  A, and the remaining voter ranks them as C  A  B. Note that “” can by interpreted to mean “preferred to” such that if a voter ranks A  B then that means that they prefer Candidate A in comparison to Candidate B. If we break these rankings down into binary preferences, we can compare the preferences among pairs of candidates, as seen in Table 1. The results of this comparison create a cyclical result. This cyclical result is inconclusive because each candidate wins by a two-thirds majority in one head-to-head match and loses in the other. The cyclic outcome of this scenario is known as the paradox of voting or Condorcet’s triplets. Outside of the setting of social choice, List, along with his coauthors, explored philosophical and legal paradoxes. Saari then translated the ideas behind these paradoxes into the context of voting. Suppose that two propositions are being considered and both must be passed for either to be enacted. Table 2 demonstrates one possible scenario of votes. As seen in this table the outcome of such a situation can change depending on how the votes are compared. In examining how many voters want both propositions to pass, the table reveals that only one-third of the voters want this outcome and so, with a two-thirds majority, both propositions fail. However, if we look at the votes another way, by first comparing the opinions regarding each proposition, we find that Proposition 1 and Proposition 2 each pass with a twothirds majority. Consequently, in this case, both propositions would pass. Hence, we find the paradox wherein the order in which these votes are counted or compiled can yield completely opposite results. Saari demonstrates the connection between these two results through a comparison of Table 1 with Table 2. By replacing A  B, B  C, and C  A with Yes and the opposite preferences with No, we transform Table 1 into Table 2. Consequently, List’s result has the same central problem behind it as Condorcet’s paradox. Now that we have shown the similarity between Condorcet and List’s findings, we complete this discussion 3 Voter 1 2 3 4 5 Outcome Proposition 1 Yes No Yes No No No Proposition 2 Yes Yes No No No No Proposition 3 No Yes Yes No No No Table 3: Example of Anscombe’s paradox. by introducing Anscombe’s work in relation to Condorcet’s paradox. Anscombe’s paradox demonstrates that in certain circumstances a majority of voters can lose on a majority of issues. Table 3 demonstrates one such set of circumstances. In this case voters 1, 2 and 3 form a majority, while voters 4 and 5 create the winning minority. Each of the three propositions would win by a two-thirds majority within the majority group. Thus, a majority of voters want at least one of these propositions to pass. However, the minority gets their way on each vote. This provides some of the reasoning behind “party discipline” being used by political parties to make sure all members vote in the same way to give their group opinion the best opportunity of being reflected in the outcome of the vote. To understand how Anscombe’s paradox relates to Condorcet’s paradox we examine Table 3 in relation to Table 1. This time we start with Table 1 and replace A  B, B  C, and C  A with Yes and the remaining relative ratings with No. This recreates the votes of the majority party as seen in Table 3. This similarity reveals that the majority party creates a cyclic vote, which allows the minority group to determine the outcome of the election. Consequently, the paradoxes introduced by Condorcet, List and Anscombe all boil down to essentially the same paradox: the problem of a voting method that leads to a cyclical, and therefore unclear, decision. 2.3 The Curse of Dimensionality Saari employs a geometric argument to demonstrate how unexpected voting results such as the Condorcet triplets come about. This argument demonstrates how increasingly complex it is to locate the desires of the voters when more options become available. Before diving into Saari’s argument [9], it is worth noting the following definition: Definition 2.3.1 (Voting Profile). A voting profile accounts for the way that each voter ranked the candidates or voted on an issue. Thus, because they present each voter’s preference, each of the tables from the previous discussion illustrate a voting profile. To see how complexity builds when more options are introduced we first consider the simple case. Suppose that there is only one proposition being voted on. A voter votes A if they want to enact the proposition and B if they disagree with the proposition. Suppose: • 60% of voters vote against the proposition, and • 40% of voters vote for the proposition. Then Figure1a accurately represents the situation; where both the outcome and the voting profile of the election are reflected by the • in Figure 1a. To clarify, the figure reflects this because the • is 60% of the distance between A and B away from A and towards B. Thus, Figure 1a shows both that 60% of voters voted for B and that 60% prefer B  A. This representation of the profile and outcome seems straightforward to represent. However, if we add in a new proposition, it quickly becomes more complicated. Introducing a second proposition, where voters for this proposition vote with C and those against it vote D. With this setup, consider Figure 1b. It is clear from the diagram that the outcome of this vote is B  A and D  C, which means both propositions fail. Yet, the diagram no longer indicates the voting profile. It is unclear how the election came to this result. This failure to accurately represent the election profile is what Saari calls the “curse of dimensionality.” 4 4 5 3 7 D D 6 8 F C C A B (a) Result for a single proposal 2 A B (b) Result for two proposals 1 A E B (c) Result for three proposals Figure 1: An illustration of the “curse of dimensionality” To further illustrate this “curse of dimensionality,” we consider two possible scenarios that would give the result displayed in Figure 1b. For the first scenario suppose: • 55% of voters voted against both proposals, • 40% voted for both proposals, and • 5% voted no to the first proposal and yes to the second proposal. In this case, the majority of voters (55%), ranked B  A and D  C. Consequently, for this scenario the outcome clearly reflects the opinion of the majority of voters. However, consider an alternate scenario that leads to these same results, in which 85% of voters want at least one proposition to pass. For this scenario suppose that: • 60% voted to enact the first proposal but not the second, • 45% voted no to the first proposal and yes to the second proposal, and • 15% of voters voted against both propositions. This profile would lead to the same outcome as our first scenario, the one shown in Figure 1b. Thus, in this case, even though the majority (85%) of voters want one of the two proposals to pass, neither pass. Returning to Figure 1 we see the roots of this “curse of dimensionality.” Whereas there are only two ways of voting when only one proposal is considered (A  B or B  A), once we add one more proposal there are now four possible ways of voting (A  B and C  D, A  B and D  C, B  A and C  D, or B  A and D  C). Thus, with the added proposal the domain of possible rankings has moved from a two-dimensional space to a four-dimensional space. Hence, the phrase the “curse of dimensionality.” This inability to accurately represent an election profile becomes even more extreme when we add in a third proposal. Let voters use E to vote for this third proposal and F to vote against enacting it. As seen in Figure 1c we now have outputs in eight-dimensional space. Where each of the eight vertices represent one of the eight possible rankings. These rankings follow the same logic as the previous two diagrams and are outlined in Table 4. Now consider the scenario displayed in Figure 1c, where each • in the diagram represents the preference of a single voter. Thus, if there are three voters, based on the diagram, they cast their votes in the following manner: • one voter voted B  A, C  D, E  F , • a second voter voted A  B, D  C, E  F , and • the remaining voter voted B  A, D  C, F  E. 5 Vertex 1 2 3 4 5 6 7 8 B  A, A  B, A  B, A  B, B  A, B  A, B  A, A  B, Ranking C  D, E  F C  D, E  F D  C, E  F D  C, F  E D  C, F  E C  D, F  E D  C, E  F C  D, F  E Table 4: Labeling for vertices on Figure 1c. The outcome of this election would be B  A, D  C and E  F , where each proposal passes or fails by a two-thirds majority. This outcome can also be seen in Figure 1c. The vertices 1, 3 and 5, which represent the wishes of these three voters, form an equilateral triangle. The vertex closest to the center of this equilateral triangle is vertex 7, which represents the outcome of this election. Consequently, with only three proposals and three voters, it is possible to have no voter completely agree with the results of the election. Figure 1 demonstrates how quickly the “curse of dimensionality” takes effect. While Figure 1b fails to depict the voting profile, Figure 1c demonstrates a situation where the results do not reflect the preferences of any individual voter. These results directly show how new problems arise with each additional option offered to voters. 3 Arrow’s Theorem Kenneth J. Arrow made a large contribution to the field of social choice in 1952 with what he termed the “Possibility Theorem” [1]. This theorem is now referred to as Arrow’s Theorem and usually appears with the conditions that accompanied the 1963 version of his theorem [2]. We present this theorem using Saari’s terminology surrounding his explanation of the result in Disposing Dictators, Demystifying Voting Paradoxes: Social Choice Analysis [9]. The value of Arrow’s Theorem comes from its comprehensive evaluation of all possible voting methods, rather than focusing on the faults or merits of individual methods. In order to examine all possible methods, Arrow came up with a series of reasonable requirements for any accurate voting method and then set out to construct such a method. To frame this idea of a generic voting method, consider a method to be a function. Such a function would map from the individual preferences of a voting profile to a single social preference. In this scenario individual preferences would take the form of each voter’s ranking of the candidates, which, when combined with all of the other voter’s individual preferences, would create a voting profile. Under the voting method created by Arrow this voting profile would lead to a strict, transitive ranking of the candidates that would be the social preference. The conditions for Arrow’s Theorem, or the requirements that Arrow put in place for a successful voting method, take the form of the following three rules. Rule 1 (Transitivity). Each voter’s ranking should be transitively ordered. Rule 2 (Independence of Irrelevant Alternatives). The ranking of two candidates in relation to each other should not be influenced by how any candidates except those two are ranked. Rule 3 (Pareto). If all the voters rank one candidate over another then that preference should be reflected in the cumulative ranking. Each of these rules seem necessary to create an accurate cumulative ranking and Arrow tested for the existence of a function that would follow all three of them. If a specific voter’s transitively ordered preferences determines the social preference for all possible voting profiles the voting method formed is called a 6 Voter 1 2 First Choice Candidate A Candidate B Second Choice Candidate B Candidate A Third Choice Candidate C Candidate C Table 5: Proposal rankings for profile 1. dictatorship. Note that a dictatorship will be defined with more precision in Section 3.3 and that it abides by Arrow’s rules. However, in implementing these rule to find an alternative function, Arrow discovered that there is always a voting profile where the voting method must concede in one aspect to the ranking of a specific voter. This one aspect, along with rules 2 and 3, end up determining the cumulative ranking for that profile. Thus, the function becomes a dictatorship. This result forms Arrow’s theorem. Theorem 3.0.1 (Arrow’s Theorem). When there are three or more alternatives, the only method of creating a cumulative ranking in keeping with the previous rules is a dictatorship. It is hard to believe that a dictatorship is the only method following these requirements. The rest of this section attempts to make sense of this result first through examples and then by examining the theorem via the lens of two different fields of study. Namely, the fields of combinatorics and geometry. 3.1 An Illustration of Arrow’s Theorem Burger and Starbird provide the following useful example to demonstrate how quickly a single voter becomes a dictator [5]. Since Arrow’s Theorem takes effect when there are three or more alternatives, we choose the simplest case and suppose there are three candidates. Let these three candidates be Candidate A, Candidate B and Candidate C. In order for there to be a nontrivial dictatorship, there must be at least two voters. For simplicity, let there be two voters, namely Voter 1 and Voter 2. Now,we may consider the different scenarios that can be created in attempting to construct a voting method that follows Arrow’s rules. For our first voter profile, suppose that these two voters vote in the manner shown in Table 5. As shown, the two voters agree in their ranking of Candidate C. However, they differ in their ranking of Candidate A in relation to Candidate B. The rules alone dictate that Candidate C must be bottom ranked. However, the function could map to either the ranking A  B  C or B  A  C while still following the rules set down by Arrow. Since these two voters are the only voters, and they disagree, an arbitrary choice must be made regarding which voter’s preference determines the election outcome for this profile. Certainly there will be other scenarios where Voter 1 and Voter 2 do not agree with each other. As a result, suppose we decide to arbitrarily concede to Voter 1 in this scenario and, for fairness, in the next scenario where the election is inconclusive we will concede to Voter 2’s preference. Thus, for this first profile the election results align exactly with Voter 1’s A  B  C preference. Now, for a second profile consider the rankings displayed in Table 6. By the rule of independence of irrelevant alternatives (IIA) the ranking between Candidate A and Candidate B relative to each other should in no way depend on how the voters rank Candidate C. Suppose that Candidate C suddenly dropped out of the election. Observe that Table 5 and Table 6 would become the same. Since we have already decided that for the first profile the election results should mimic Voter 1’s preference of Candidate A, in order to maintain the rule of IIA Candidate A should be ranked above Candidate B in this situation as well. Furthermore, both voters ranked Candidate B above Candidate C. Thus, by the Pareto rule, the cumulative ranking should have Candidate B preferred over Candidate C as well. Consequently, the election results in B  C  A and the outcome, again, matches up exactly with Voter 1’s ranking. As our final illustrative example, consider a third profile as represented by Table 7. Again, we apply the rule of IIA, in this case to examine the relationship between Candidate A and Candidate C. Removing Candidate B, Table 6 and Table 7 express the same relative rankings. Therefore, regarding Candidate A and Candidate C, their comparative ranking in the outcome should be the same for both elections. Since our second scenario ranked Candidate A above Candidate C, this must also be the outcome of this election. Voter 1 and Voter 2 both rank Candidate B above Candidate A, which means by the Pareto rule Candidate 7 Voter 1 2 First Choice Candidate A Candidate B Second Choice Candidate B Candidate C Third Choice Candidate C Candidate A Table 6: Candidate rankings for profile 2. Voter 1 2 First Choice Candidate B Candidate C Second Choice Candidate A Candidate B Third Choice Candidate C Candidate A Table 7: Candidate rankings for profile 3. B is ranked above Candidate A. Hence, the election result is C  B  A and once again aligns precisely with Voter 1’s preferences. As indicated by these three profiles, in deciding the outcome of a single profile we have determined the outcome for all profiles. Consequently, there is no opportunity to concede to Voter 2 at any point. This single concession to Voter 1’s preference in the first scenario makes it so that every election result exactly matches Voter 1’s ranking of the three proposals. Note that the voter’s preferences in each of these three scenarios conform to the rule of transitivity and the results obey the rules of Pareto and IIA. Thus, Voter 1 is the dictator guaranteed by Arrow’s Theorem. Repetition of this process could extend these results to cases involving more than three candidates. Instead of writing out such extended examples, we formalize these current results using a proof from the field of combinatorics. 3.2 A Brief Introduction to Combinatorics In addition to Social Choice Theory, Arrow’s Theorem can be interpreted within the field of Combinatorics. Before delving into the interpretation of Arrow’s Theorem within this field, it is necessary to provide a short introduction to the relevant ideas from Combinatorics. Namely, a basic knowledge of total order is needed for the subsequent proof of Arrow’s Theorem. Since a total order is a special type of relation, we start by introducing the concept of relations. Note that the definitions that follow come from Brualdi’s Introductory Combinatorics [4]. Definition 3.2.1 (Relation). A relation on a set X is a subset R of the set X × X of ordered pairs of elements in the set X. For the ordered pair (x, y) ∈ X the standard notation is xRy if (x, y) is in R and x R y when (x, y) is not in R. In other words, a relation is some type of “property” that either is or is not true for some pair of elements in a set X. Simple examples of relations include <, ≤, >, ≥, =, ⊂, ⊆, and |. As an illustration of our definition, suppose our relation R on X = {0, 1, 2} is ≥. Since 0 ≥ 0, 0  1, 0  2, 1 ≥ 0, 1 ≥ 1, 1  2, 2 ≥ 0, 2 ≥ 1, 2 ≥ 2 our subset of X × X is R = {(0, 0), (1, 0), (1, 1), (2, 0), (2, 1), (2, 2)}. There are multiple properties that a relation can have, below we outline three such properties: Property 3.2.1 (Reflexive). A relation R is reflexive if xRx for all x ∈ X. This means that, when a relation is reflexive, each element in X is related to itself. Based on our earlier simple examples the relations ≤, ≥, =, ⊆, and | are all reflexive relations, while <, >, and ⊂ are not reflexive or are irreflexive relations. Property 3.2.2 (Antisymmetric). A relation R is antisymmetric when the relation has the property that xRy implies y R x for all x, y ∈ X where x 6= y. 8 This definition of the antisymmetric property can be restated as: for an antisymmetric relation R, if xRy and yRx for some x, y ∈ X then x = y. From these definitions we see that out of our simple examples <, ≤, >, ≥, ⊂, ⊆ and | are antisymmetric relations. Thus, only = is not an antisymmetric or a symmetric relation. Property 3.2.3 (Transitive). A relation R is transitive when xRy and yRz implies xRz for all x, y, and z ∈ X. The transitive property acts in the same way as the rule of transitivity from Arrow’s Theorem. All of the simple examples of relations are transitive. The Condorcet Triplets in Section2.2 provide an example of a relation (social preference) that is not transitive. A relation that has the properties of being reflexive, antisymmetric and transitive is a special type of relation known as a partial order. Definition 3.2.2 (Partial Order). A relation R that is reflexive, antisymmetric and transitive is a partial order on a set X. A set X that has a relation R that is a partial order on it is often referred to as a partially ordered set or a poset for short. As noted above, the relation ≥ has all three of these properties and is therefore a partial order. In fact, we will use the similar notation of  to denote a partial order and (X, ) to mean a partially ordered set. The “partial” in partial order refers to the fact that while the relation in some sense “orders” the set X it may be the case that for some x, y ∈ X, x R y and y R x. For example, consider the relation ⊆. As already noted, this relation is reflexive, antisymmetric and transitive and therefore a partial order. While ⊆ orders sets by comparisons of inclusion, two disjoint sets are not related to each other and thus are not ordered by the relation. Definition 3.2.3 (Total Order). A partial order on a set X is a total order if every pair of elements on X is comparable. Note that two elements x, y on a set X with relation R are comparable so long as either xRy or yRx. Thus, a total order is relation that is able to order an entire set X. Out of our initial simple examples ≤ and ≥ are the only total orders. While | and ⊆ are both only partial orders, <, > and ⊂ are irreflexive and = is symmetric. This concept of total order becomes crucial in the following discussion, wherein we consider the cumulative ranking system designed in Arrow’s Theorem to be a total order. 3.3 How Total Order Relates to Arrow’s Theorem As indicated earlier, the conditions or rules accompanying Arrow’s Theorem changed with Arrow’s 1963 publication [2]. Prior to this publication the theorem relied on more restrictive rules than the three introduced above. In our discussion of the connection between posets and Arrow’s Theorem we will consider the original version of the theorem that appeared in his 1952 work [1]. Thus, we will proceed by introducing two new rules that will take the place of the Pareto rule, and redefining our existing rules. The following discussion and proof comes from Cameron’s textbook Combinatorics: Topics, Techniques, Algorithms [6]. We begin by considering the setup to Arrow’s Theorem within a combinatorial setting. Suppose we have n voters that are part of some society I, and the set X is the set of candidates that the n voters have to choose between. Let i represent the individual preferences of voter i ∈ I. We will define a social choice function as a function, beholden to the four rules listed below, which takes the preferences i for all i ∈ I and gives a social preference  on X. Rule 1 (Transitivity). The relation i is a total order on X for each i ∈ I. As discussed previously, total order implies transitivity. As indicated by the notation, i is a total order, which means that in addition to being transitive i is reflexive, antisymmetric and comparable. Within our current context, this just requires each voter to provide a complete ranking of all of the candidates. Rule 2 (Independence of Irrelevant Alternatives). Let {i } and {0i } be two sets of individual preferences on X, with corresponding social preferences  and 0 respectively. If Y ⊆ X and these sets are such that i and 0i have the same ordering on Y for all i ∈ I, then  and 0 have this same ordering on Y . 9 This rule corresponds directly with our earlier IIA rule. It demonstrates that the social choice function operates in the same manner on a subset of X as it does on X. Thus, the social ranking of a subset of candidates, relative to each other, should remain constant, regardless of how many additional candidates are part of the election. Rule 3 (Monotonicity). If x  y for some x, y ∈ X, then this remains true if the individual preferences of a voter is changed to favor y. To clarify this, let 0i be another system of individual preferences with social preference 0 . Suppose that the two systems of individual preference agree on all points except those involving candidate y, which means u i v if and only if u i v for all non-y values u, v ∈ X. Further suppose that this new system agrees with our current system regarding preferences for voter y, which means that if u i y then u 0i y for all u ∈ X. The monotonicity rule states that if x  y then it is also true that x 0 y. Rule 4 (Non-imposition). For any x, y ∈ X where x 6= y, there is some system of individual preferences where x  y. Essentially, the non-imposition rule states that any binary ranking is a possible result, given enough voters express that result as their preference. Note that the non-imposition rule and monotonicity rule in conjunction imply that the Pareto rule is also in effect. To illustrate this, for two given candidates x and y we know that some combination of preferences yields x  y by the non-imposition rule. Moreover, by the monotonicity rule it also is true that x  y if x i y for all i ∈ I. Thus, the Pareto rule holds. With our current notation in mind, we now define a dictator as an individual i ∈ I, whose preferences i are the same as  for all systems of individual preferences. Consequently, a dictatorship is a social choice function where the individual preferences of a dictator decide the social preference for all possible sets of individual voter preferences. Using this definition and our four rules, Arrow’s Theorem becomes: Theorem 3.3.1 (Arrow’s Theorem). If |X| ≥ 3, then the only social choice function that exists is a dictatorship. Proof. Building off of our work in combinatorics thus far, we provide a combinatorial proof of Arrow’s Theorem. This is a proof by contradiction. Thus, we start by supposing that there exists a social choice function when |X| ≥ 3 that is not a dictatorship. First, we introduce some new terminology. For an ordered pair (x, y), where x, y ∈ X and x 6= y, a set J of individuals is (x, y)-decisive if, when all of the individuals in J prefer y to x, y is preferred to x in the social order. Symbolically, when J is (x, y)-decisive, if x i y for all i ∈ J, then x  y. When a set J is (x, y)-decisive for distinct x and y then J is decisive. Earlier, we indicated how the Pareto rule follows from the non-imposition rule and the monotonicity rule, using our new terminology we provide a more rigorous proof of this fact. Note that the Pareto rule may be restated to say that the society I is (x, y)-decisive for all x, y ∈ X. Let (x, y) be an ordered pair of distinct options, by the IIA rule we may treat x and y as if they are the only candidates for this election. Some system of preference exists, by the rule of non-imposition, such that x  y. Lastly, by the monotonicity rule this preference is maintained when more voters vote with this same preference. Thus, x  y when x i y for all i ∈ I and society I is decisive over all pairs of candidates. The rule of non-imposition guarantees that there is some set of individuals J where J 6= ∅ that is a minimal decisive set. Let J be (x, y)-decisive and suppose that an individual i is in J. Recall from our earlier definition of a dictator, and our assumption that our social choice function is not a dictatorship, we assume that J 6= {i} when J is (x, y)-decisive for all x, y ∈ X such that x 6= y. That is, we have assumed that the minimal set of individuals that is decisive for all ordered pairs of candidates does not contain a single person, and therefore our function cannot be a dictatorship. Let J 0 = J\{i} and K = I\J. Since |X| ≥ 3 there exists a candidate z ∈ X that is different from both x and y. Consider the scenario represented by the following preferences: • x i y i z, • z j x j y for all j ∈ J 0 , and • y k z k x for all k ∈ K. 10 Type E1 E2 E3 Ranking ABC ACB CAB Type E4 E5 E6 Ranking CBA BCA BAC Table 8: All possible rankings of candidates A, B, and C. C E3 E4 E2 E5 E1 E6 A B Figure 2: Placement of all possible rankings from Table 8 on triangle. By the rule of IIA ignoring the ranking of z yields x i y and x j y for all j ∈ J 0 . Since J = {i} ∪ J 0 , this means that x j y for all j ∈ J. Moreover, because J is the determining set for (x, y) this means that x  y. Suppose that z  y, then J 0 would be a decisive set. However, since |J| > |J 0 | this would violate the minimality of J. Thus, y  z. By the rule of transitivity x  z. This social preference contradicts the preferences of both the set J 0 and K of voters. Since i is the only voter that agrees with this outcome it must be the case that {i} is (x, z)-decisive, and because J is minimal J = {i}. Since z is just a candidate distinct from candidate x, {i} is (x, z)-decisive for all z 6= x. For y 6= x, and z 6= x, y. Suppose the voters have the preferences outlined below: • y i x i z, and • z k y k x for all k ∈ I where k 6= x. By examining the relative rankings of x and y under the rule of IIA, we see that all of the voters in I prefer candidate y to candidate x. By the Pareto rule this results in y  x. Since x i z and {i} is (x, z)-decisive, x  z. The rule of transitivity demonstrates that y  z. This social ranking contradicts the preference of all voters except for voter i. Thus, {i} is (y, z)-decisive for all y 6= x and z 6= x, y. Lastly, consider the scenario in which the voters preferences are: • y i z i x, and • z k x k y for all k ∈ I such that k 6= x. All voters in I prefer candidate z to candidate x by the Pareto rule this means that z  x. Additionally, since {i} is (y, z)-decisive for all y 6= x and z 6= x, y, the social rank must be y  z. Consequently, by the transitivity rule y  x. No voter, except for voter i, agrees with this ranking. Hence, {i} is (y, x)-decisive for all y 6= x. Consequently, {i} is decisive for all ordered pairs of distinct objects in X. This contradicts the assumption that our social choice function is not a dictatorship. This completes our proof. 3.4 The Geometry of Voting Now that we have explored Arrow’s Theorem through examples and the field of combinatorics, we take a final look at this central theorem with respect to geometry. Saari creates a method of illustrating the wishes 11 C 1 2 2 1 4 2 A B Figure 3: Illustration of scenario involving 12 voters and candidates A, B, and C. of voters through geometry in Basic Geometry of Voting [8]. This geometric approach offers a more in-depth understanding of the causes behind Arrow’s Theorem. Before applying these methods to Arrow’s Theorem we first introduce these illustrations. Suppose there are three candidates for an election, namely candidates A, B, and C. Omitting any ties, there are only six possible ways for a voter to rank these three candidates. These six rankings are explicitly shown in Table 8. Saari uses an equilateral triangle to present these rankings in a single diagram as demonstrated in Figure 2. To illustrate how this triangle can be used we will show the value of using it to represent a scenario in which twelve voters vote as follows: • 4 voters are type E1 (A  B  C), • 2 voters are type E2 (A  C  B), • 1 voter is type E3 (C  A  B), • 2 voters are type E4 (C  B  A), • 1 voter is type E5 (B  C  A), and • 2 voters are type E6 (B  A  C). The votes resulting from these twelve voters are depicted in Figure 3. Note that the preference that each section of the triangle represents is indicated by its proximity to each of the candidates. For instance the “4” in Figure 3 is in the section that touches point A, is half the distance of one side of the triangle from point B and more than half the distance of a side of the equilateral triangle away from point C. Thus, it reflects that the preference of these four voters is A  B  C. At this point, the diagram of our scenario is decent, however it does not really provide any information that could not be conveyed just as easily through a table of preferences. The true value of using an equilateral triangle divided into six parts is that it can simultaneously demonstrate the division of votes and the results of these votes in terms of each pairing of candidates. Consider if candidate C suddenly dropped out of the race. Assuming that the ranking of each voter reflects their true preferences, their respective rankings of candidates A and B should not change. Thus, of the six types of rankings, types E1 , E2 and E3 all have A  B as their preference while voters of type E4 , E5 and E6 have B  A as their preference. The triangle in Figure 4a reflects this by demonstrating that in a runoff strictly between Candidate A and Candidate B, Candidate A would win by two votes. Similarly, Figures 4b and 4c respectively reflect the results if Candidate B or Candidate A dropped out of the race. Thus, the best representation of this scenario accounts for all of these runoff results and accounts for the ranking preferences of each of the twelve voters. This illustration appears in Figure 5. This diagram of the scenario simultaneously depicts each voter’s preference and the result of the election. It is easy to confirm using Figure 5 that A is the Condorcet winner of this election and C is the Condorcet loser of the election. Hence, these diagrams provide a comprehensive illustration of an election. Below we employ these diagrams to portray some of the key aspects that result in Arrow’s Theorem. 12 C C C 4 1 2 2 A 7 1 1 4 5 8 2 2 1 2 4 5 1 2 2 1 4 BA (b) Candidates A and C B (c) Candidates B and C Figure 4: Results of runoffs between pairs of candidates from scenario. C 4 5 1 8 2 2 1 4 7 2 7 5 B Figure 5: Illustration of votes and results of election scenario 13 7 2 BA (a) Candidates A and B A 2 C A B Figure 6: The agreed upon ranking for {A, C}, A  C, represented in green. 3.5 The Problem with Independence of Irrelevant Assumptions Saari argues that the combination of demanding that a social choice function follow the rule of IIA and produce a transitive result provides the impetus behind Arrow’s Theorem. Here we provide Saari’s illustration of how these two aspects of a social choice function conflict and result in the single option of a dictatorship [8]. For this illustration we create a scenario where there are only two voters and three candidates, namely Voter 1, Voter 2, Candidate A, Candidate B and Candidate C. In this scenario we let Voter 1 and Voter 2 be decisive over the comparative ranking of Candidate A with Candidate B and Candidate B with Candidate C respectively. The ranking of Candidate A in relation to Candidate C should be determined based on a consensus between the two voters. Suppose both voters agree on the {A, C} ranking of A  C. Using the method of representation introduced previously, we illustrate acceptable outcomes of this election by coloring the corresponding sectors of the triangle green in Figure 6. Since Voter 1 controls the preference between Candidate A and Candidate B, they have the power to choose which side of the C line should contain the region of the election outcome. Thus, Voter 1 chooses E6 (B  A  C) or votes A  B and lets Voter 2 choose between E1 (A  B  C) and E2 (A  C  B). Likewise, Voter 2 has two different options in dictating which side of the A line that the result should be found. Based on their ranking of Candidate A in relation to Candidate C Voter 2 either chooses E2 (A  C  B) or narrows down the possible election results to ranking E1 (A  B  C) or E6 (B  A  C). Note that each of these three rankings maintain the agreed upon A  C ranking. Now suppose that Voter 1 chooses the E6 ranking through a B  A preference and Voter 2 chooses the E2 ranking by voting C  B. Ignoring the consensus ranking of A  C, these preferences of Voter 1 and Voter 2 are recorded in Figure 7. From Figure 7 we get the consensus ranking of E4 . However, note that E4 lies outside the consensus region of Figure 6. In terms of rankings this means that Voter 1 and Voter 2’s individual rankings of B  A and C  B results in the ranking of C  B  A despite the consensus of the two voters that A  C. The geometric illustrations provide a clear view of how the choices of Voter 1 and Voter 2 can create a cycle. This is due to the uneven distribution of preferences within the region of Figure 6. Once A  C is decided there is only one ranking with C  B whereas there are two possibilities if Voter 1 votes B  C. Similarly, there is only one position corresponding to a ranking of C  B while there are two within the colored region with relative ranking B  C. Consequently, by having both Voter 1 and Voter 2 choose the ranking represented by a single triangle we create a cycle. This same logic can create cycles in any similar setup. This illustrative example shows that even in very simple cases, logical binary rankings of candidates can lead to cyclic outcomes. This is why the rule of IIA creates the problem behind Arrow’s Theorem. Recall that the rule of IIA can reduce any ranking of candidates down to the binary rankings of pairs of candidates. However, this example demonstrates that cyclic election outcomes can have logical binary rankings. Thus, the IIA makes it so that the function can no longer identify if the voting profile leads to a cycle by demanding that cyclic and transitive profiles by treated in the same way. For instance, in this example, if the two voters had instead agreed that C  A, then the election would result in the transitive ranking C  B  A. By the IIA both of these rankings (the transitive and the intransitive one) can be 14 C A B Figure 7: Voter 1’s B  A preference represented in blue, Voter 2’s C  B vote shown in yellow and the resulting consensus of these two rankings in green. reduced to binary preferences. Since both have the same {A, B} and {B, C} preferences the IIA shows that they should both have the same outcome in terms of these two rankings, which leads to the C  B  A transitive ranking. However, this ranking contradicts the Pareto rule for the intransitive or cyclic case. Essentially, the problem arises when IIA requires that both of these rankings be treated the same way. By allowing rankings to reduce to comparative binary rankings, IIA also requires that cycles and transitive inputs have the same outcome within any social choice function. Clearly, no function can create such a mapping without violating one of Arrow’s other rules. In this light, Arrow’s Theorem becomes far more logical. Consequently, while still disappointing, this logic makes the lack of any function fulfilling all of these requirements far more reasonable. 3.6 Reinterpreting Arrow’s Theorem In addition to shedding light on the reasoning behind Arrow’s Theorem, Saari also demonstrates that functions exist that almost satisfy all of Arrow’s rules. Saari illustrates these results through a discussion of a theorem closely related to Arrow’s Theorem. We provide a brief outline of Saari’s proof of this theorem, a detailed proof can be found starting on page 88 of Saari’s text [8]. Before we introduce this theorem we must define voter responsiveness. A function satisfies voter responsiveness so long as the outcome of the function does not identically match the output of a function that only relies on a single voter. For example, a dictatorship does not satisfy voter responsiveness but every other voting method discussed so far does satisfy this condition. With this term defined and borrowing our notation from Section 3.3 this new theorem may be stated as follows: Theorem 3.6.1. No function exists that maps from the transitive rankings provided by voters to an output of three transitively ranked candidates while satisfying independence of irrelevant alternatives, non-imposition and voter responsiveness. This theorem is a more general version of Arrow’s Theorem. As noted above, a dictatorship violates voter responsiveness, and as discussed in Section 3.3, the rule of Pareto implies non-imposition. Thus, Arrow’s Theorem is just a specific case of Theorem 3.6.1. We have already noted that a dictatorship violates voter responsiveness, the only other voting function that violates this requirement is an anti-dictatorship. Like a dictatorship, an anti-dictatorship only relies on the preferences of a single voter and is defined below. Definition 3.6.2 (Anti-Dictatorship). The election outcome is determined by a single voter and is the reverse of that voter’s preferences. The idea behind an anti-dictatorship is that, to spite the wishes of an individual voter, the preferences of that voter are not only not met they are intentionally reversed completely in the result of the election. With this term defined, we may restate Theorem 3.6.1 in a way that more closely emulates Arrow’s Theorem as: the only functions with three transitively ranked candidates as its input that satisfies the rules of transitivity, independence of irrelevant alternatives, and non-imposition are a dictatorship and an anti-dictatorship. Now 15 q2 = −3 q2 = −1 q2 = 1 p1 q2 = 3 p3 q1 = 3 q1 = 1 p2 q1 = −1 q1 = −3 Figure 8: Level sets for x + y = q1 and x − y = q2 . that the connection between Theorem 3.6.1 and Arrow’s Theorem is established we can discuss a proof of this theorem, and by extension, Arrow’s Theorem. The proof starts with the case where there are n = 2 voters. Let all possible strict transitive rankings of the three candidates form the space Si(3). Since no restrictions are placed on how the voters can rank the candidates, if we assume Theorem 3.6.1 is false, then there exists a function satisfying all of the conditions referenced in the theorem of the form F : Si(3) × Si(3) → Si(3). From the IIA property this function can be defined in terms of the rankings over each pairing of candidates. Let our three candidates be Candidate A, Candidate B and Candidate C . Thus, we get the three functions FA,B , FB,C , and FC,A , where for a voting profile p we get FX,Y (p) is the relative ranking of X and Y as determined by F (p). For example if a voting profile p is such that F (p) = A  B  C then we see that FA,B (p) = A  B, FB,C (p) = B  C, and FC,A (p) = C  A. Since there are only two possible outcomes for each of these binary rankings we can simplify the notation such that FX,Y = 1 if X  Y and FX,Y = −1 if Y  X for some candidates X and Y . Thus, for the above voting profile p we would have FA,B (p) = 1, FB,C (p) = 1 and FC,A (p) = −1. Consequently, if we compile these three binary rankings we can represent our result as F ∗ (p) = (FA,B (p), FB,C (p, FC,A (p) = (1, 1, −1). Based on the above notation it follows that any output of the form (1, 1, 1) or (−1, −1, −1) is a cycle. Thus, our function does not satisfy the conditions of Theorem 3.6.1 if there exists a voter profile p such that F ∗ (p) = (1, 1, 1) or F ∗ (p) = (−1, −1, −1). The proof of this theorem relies on constructing a profile that produces such a cycle. Since, we do not have an explicit definition of our function, we use the concept of level sets to prove that such a profile exists. Rather than reproducing the full proof, we indicate how this proof works through a similar example. Consider the functions q1 = x + y and q2 = x − y shown in Figure 8.The level sets for q1 form the lines sloping from upper left to lower right while those moving from lower left to upper right are the level sets for q2 . The idea is to solve for q1 and q2 that produce point p3 using level sets rather than solving the two equations. Without explicitly using the two equations we start at the point p1 = (−2, 1) with corresponding (q1 , q2 ) = (−1, −3). Staying on the level set for q1 we follow the line until it intersects with the q2 level set of the desired point. This moves us to point p2 = (1, −2) located at (q1 , q2 ) = (−1, 3) Lastly, by remaining on the level set q2 = 3 we find the point p3 = (2.5, −0.5) found at (q1 , q2 ) = (2, 3). Thus, without explicitly using q1 and q2 we have determined that values of q1 and q2 exist that correspond with the desired point. A similar use of level sets can show that a profile exists such that F ∗ (p) = (1, 1, 1). Saari argues that Theorem 3.6.1 represents the border between the type of election functions that are possible and those that are impossible. According to him if any condition of the theorem is weakened a function becomes possible [8]. For instance, if there is a single ranking that one voter is prohibited from submitting as their vote, a function exists that satisfies the remaining conditions of Theorem 3.6.1. 16 Furthermore, consider replacing the IIA rule with the rule of the intensity IIA, where the relative ranking of two candidates only depends on the voters’ rankings of those two candidates and the intensity of that ranking. With this definition in mind we get the following theorem. Theorem 3.6.3. There exists a function that maps from the transitive rankings provided by voters to an output of transitively ranked candidates while satisfying intensity independence of irrelevant alternatives, non-imposition and voter responsiveness. In fact, the Borda count method is one such function that satisfies these properties. Thus, even though Arrow’s Theorem provides a daunting result, in light of further investigation, the logic behind this theorem becomes far more intuitive. Additionally, we see that, even though no function satisfies all of the qualities desired by Arrow’s Theorem, functions do exist that almost work the way we would expect. This combination of expected and unexpected results from elections is investigated further in the next section. 4 Accounting for Everything 4.1 Voting Dictionaries As indicated earlier, the value of Arrow’s Theorem comes from its evaluation of all possible voting methods, rather than examining each individual method. Similarly, instead of seeking specific problems and examples, Saari devised a method to account for all of the results possible under a given voting method [9]. The method Saari developed relies on what he calls voting dictionaries, this section offers a brief introduction to these dictionaries and their uses. In order to conceptualize all of these examples we return to the idea of a voting method as a function. With this in mind, by trying to account for all possible results for a specific voting method, Saari seeks the range of such a function. One possible approach for assessing this range is to take the entire domain of our function, all possible voting profiles, and find the output for each profile to determine the range. However, even in simple scenarios where there are only three candidates and 19 voters there are over 60 trillion possible voting profiles to consider. Consequently, to account for all examples we instead start with the codomain, or all possible preferences that could be a result of an election, and then determine if a voting profile exists that can map to this preference. Some of the examples within the codomain of this function are completely counterintuitive in the context of voting. For instance, suppose that we examine the possibilities under the plurality vote, with 78 voters and four candidates. Let these four candidates be Candidate A, Candidate B, Candidate C and Candidate D. One such element in this codomain would be the election results: • A  B  C  D with all four candidates, • D  C  B if Candidate A drops out of the election, • D  C  A if Candidate B drops out of the election, • D  B  A if Candidate C drops out of the election, • C  B  A if Candidate D drops out of the election, • C  D if candidates A and B drop out of the election, • B  D if candidates A and C drop out of the election, • B  C if candidates A and D drop out of the election, • A  D if candidates B and C drop out of the election, • A  C if candidates B and D drop out of the election, and • A  B if candidates C and D drop out of the election, 17 Number 5 7 9 4 7 Preference ABCD ACBD ADBC BACD BCAD Number 9 8 11 8 10 Preference BDAC CBAD CDAB DBAC DCAB Table 9: Voting profile that leads to a reversal of preference whenever a candidate withdraws under the plurality method. Note that in this example the election results reverse any time a candidate drops out of the election. Surely the voter’s preferences would not change so dramatically, or at all, if a candidate forfeits the election. Consequently, we expect that no voting profile would allow these reversals and that this element in the codomain of the plurality vote would not be in its range. Although it seems unlikely that any voting profile would map to these extreme results, such a voting profile does exist and is displayed in Table 9. It is easy to confirm that this profile produces the results listed above under the plurality vote. This example illustrates one of the surprising results that comes out of considering all possibilities. Now that we see the value behind this endeavor we formalize the ideas being discussed. First, we clarify the meaning of voting methods for its use in this section. Since we consider, as above, the outcome for any subset of candidates it may be the case that the voting method used to evaluate the candidates depends on which subset is selected. For instance, one possible method employs the vote-for-two on all candidates to determine the top two choices and then has a plurality runoff between these two candidates that decides the winner [5]. For the above example we considered the 11 possible subsets of the four candidates that contain two or more candidates. Note that the election results would be trivial if there was only one candidate being considered. Instead, suppose that we had a situation with n ≥ 3 candidates. It is a combinatorial result that there would be 2n − (n + 1) subsets of the n candidates containing 2 or more candidates. To provide some insight for this number consider that there must be 2n subsets of n candidates because for each of the n candidates there are two options, they are either included in the subset or not included. Out of these 2n subsets one is the empty set and there are n sets, one for each candidate, that contains a single candidate. With this in mind we form the following definitions: Definition 4.1.1 (Word). For n ≥ 3 candidates and a given voting method and voting profile, a word is a list of election rankings that would result from such an election. This list is the collection of outcomes of the given voting method for each subset containing two or more of these candidates. Based on this definition a word contains a ranking for each of the 2n − (n + 1) subsets of candidates. This means that each word is in the form of an element in our codomain. Moreover, since each word is the result of a given voting profile, a word is just an element in the range of our function. The bulleted list of rankings for our previous scenario provides an example of a word for n = 4, the plurality as our voting method and Table 9 as the given voting profile. Definition 4.1.2 (Dictionary). For a given voting method, the dictionary of that method is the collection of all words possible under some voting profile. Returning to our function analogy, a dictionary for any specific voting method is the range of that method. Thus, the list of all possible examples, that we introduced at the beginning of the section, would just be the dictionary for that voting method. As some final notation, the Borda count dictionary for n candidates is denoted by Dn (B). Similarly, the notation for the plurality dictionary for n candidates is Dn (P). Where in both of these cases the given method is used on all subsets of candidates. Note that the word represented by the bulleted list in our example is an element of Dn (P). Now that we have a better understanding of voting dictionaries, it is clear that creating a dictionary would be a time consuming process. It would require examining every possible combination of rankings over all of the subsets of candidates containing two or more candidates and determining if a voting profile 18 H Flip 1 H Flip 2 Flip 3 T H T T H H T H T T H T Flip ... Figure 9: All possibilities when flipping a coin exists that leads to that word. Saari grapples with the difficultly of this task and provides a clever method for constructing these dictionaries, rather than focusing on their construction the remainder of this section considers the use of these dictionaries. 4.2 Better Methods Here we reproduce Saari’s connection between dictionaries and chaos theory and show some of the results that come out of using these dictionaries [9]. Specifically, Saari discusses what is called symbolic dynamics, which is a branch of chaos theory that looks for all possible outcomes. This concept fits in directly with the idea of a creating a dictionary. Symbolic dynamics often observes random events such as flipping a coin. Figure 9 illustrates the different possible results of flipping a coin, where each of the eight entries in the third row represent a different combination of results for the first three flips. For example, the second “H” listed in the third row represents the outcome of Head on the first flip, Tail on the second flip and another Head on the third flip. As indicated by the “Flip . . . ” this pattern of options can continue on for any number of flips. Since each possible outcome is represented by following a branch of Figure 9, even though the process is random, we can think of it in terms of chaotic dynamics. This means that we consider these events as being the result of some deterministic process rather than chance. Let f (x) be the function of this deterministic process, such that xn+1 = f (xn ) for n = 0, 1, 2, . . ., which indicates that the current result xn dictates the future result xn+1 . As a simple example we suppose that our function is the one shown in Figure 10, which is restricted to the unit square and and consequently 0 ≤ x ≤ 1. Using this figure our function starts at some x0 and then moves through the iterates x0 , x1 , x2 , . . ., where the location of each xi falls either to the left or right of the dotted line. Those to the left may be assigned to represent flipping a Head while those to the right would symbolize flipping a Tail. Since this sequence is infinite, for any infinitely long sequence of Heads and Tales, there exists some integer j such that the sequence of Heads and Tales associated with xj , xj+1 , xj+2 , . . . is the same as the given sequence of flips. Applying this idea back to our dictionaries, a figure similar to Figure 9 can be constructed for preferences of candidates. As a result we see that any sequence of preferences can be created by some initial condition. Note that a figure illustrating all of the possible voting preferences for just three candidates would have 351 total branches. These 351 possible outcomes include the possibility of ties, so that for each pair of candidates there are three possible outcomes for the binary preference of the two candidates. Thus, 351 accounts for the 3 × 3 × 3 × 13 = 351 possible words for the codomain of our dictionary. As indicated by our discussion of chaos theory, for almost all voting methods these 351 branches also represent the range of our dictionary. However, by construction, the Borda Count cannot rank the Condorcet loser above the Condorcet winner. This aspect of the Borda count restricts the range of the dictionary making D3 (B) the only dictionary for three candidates to exclude some of these 351 possible results. The fact that the Borda count prevents some of these unexpected results becomes increasingly important in elections with more candidates and, as a consequence, more possible outcomes. As an illustration, if one additional candidate joins the election the 351 possible branches increase to 36 × 134 × 69 = 1, 436, 646, 861 possible outcomes. The possibilities under an increasing number of candidates continues to grow to be roughly a billion times a billion times a billion potential outcomes with just five candidates. This is particularly impressive when we consider that most voting methods admit all of these outcomes. Moreover, if the outcome 19 1 L R 1 x Figure 10: A possible deterministic function for flipping a coin under each subset of candidates could be determined by the cumulative ranking of all five candidates, as some voters expect, the number of possible outcomes would only be 431. After seeing the size of these ranges for just four or five candidates it becomes unclear how much the restriction on the range of the Borda count dictionary can really make a difference. When there are over a billion cubed possibilities the Borda count dictionary would need to eliminate a vast number of outcomes before there would be any practical difference between it and these other dictionaries. As a gauge of the extent to which Borda eliminates unwanted results we compare its range to that of the plurality vote when there are seven candidates. The result of this comparison shows that 1050 |D7 (B)| ≤ |D7 (P)|. For some perspective on this 1050 value, it is worth noting that this number is significantly greater than a billion times the number of water droplets in all of the oceans in the world. Consequently, these dictionaries reveal that the Borda count eliminates a significant number of the unexpected results that come up with other voting methods. 5 5.1 Creating Compromise Finding Agreeable Candidates Thus far our discussion has largely focused on uncovering the unexpected results that can occur within common voting systems and determining how successful these various methods of voting are at representing the desires of the voters. Here, rather than considering the effectiveness of voting for determining the single outcome desired by voters, we consider its effectiveness at pinpointing the more general desire of voters and at appeasing voters. We address this work using Berg, Norine, Su, Thomas and Wollan’s “Voting in Agreeable Societies” [3]. To shift focus towards the “general” opinion of voters, instead of thinking of voter preferences as a ranking of candidates (as in previous sections), think of voter preferences as a range of acceptable candidates. This thinking leads to another method of voting that has yet to come up in our discussion so far, namely approval voting. Approval voting is used by both the Mathematical Association of America and the American Mathematical Society to determine elections. We provide Burger and Starbird’s definition of the method below [5]. Definition 5.1.1 (Approval Voting). Each voter votes for all of the candidates that they find acceptable and the candidate that receives the most votes wins. Based on its definition, approval voting relies on each voter having a range of candidates that they find acceptable. One way to visualize this is demonstrated in Figure 11, where a voter’s opinion falls somewhere on the spectrum ranging between the two conflicting political philosophies of liberalism and conservatism. Each location on this spectrum represents a different platform that a candidate can represent and a voter may wish to support. The two brackets on the spectrum in Figure 11 represent the most liberal and most conservative platforms that voter x approves of and encompass the range of platforms that voter x finds acceptable. The range of platforms that voter x finds acceptable is termed voter x’s approval set. Within this setup we can assume that each voter has an approval set that is a closed interval in R and that each candidate has 20 Liberal Neutral Conservative [ ] x Figure 11: The range of platforms that voter x approves in a one-dimensional political spectrum. 5 1 6 2 3 7 4 Figure 12: A linear society with seven voters whose approval sets are represented by a line over an infinite one-dimensional spectrum. The shaded area indicates the range of platforms that would win an election under approval voting. a platform located somewhere on this political spectrum. This spectrum combined with a set of candidates and a set of voter’s approval sets form what is called a linear society. A linear society has several important properties that, along with the definition of a linear society, form the content of the following discussion. 5.2 The Ease of Pleasing an Agreeable Linear Society Before defining linear societies, and delving into their various properties, we provide the more technical definitions, from “Voting in Agreeable Societies” [3], for several of the terms employed above. A set X that can model all possible voter preferences is a spectrum, which means that the elements of the spectrum are the different platforms. For the finite set V of voters, each v ∈ V is associated with an approval set Av of platforms. A society S is a triple (X, V, A) for some X a spectrum, V a set of voters, and A a collection of approval sets for each voter v ∈ V . This terminology leads us to our definition of a linear society: Definition 5.2.1 (Linear Society). A linear society is a society (X, V, A) where X is a closed subset of R, and for each approval set Ai ∈ A there exists an interval I such that Ai = X ∩ I and I is either empty or a closed bounded interval in R. It follows from this definition that the society shown in Figure 11, where the set of all voters is simply {x}, is a linear society. Figure 12 provides an example of a linear society with a larger set of voters. In order to make this figure readable the approval set of each voter is now represented by a line above the spectrum. Note that the society depicted in Figure 12 is in fact linear because each line representing an approval set contains its endpoint and is unbroken, which means it represents a closed and bounded interval on the spectrum. It easily follows that each approval set is equal to the intersection of the interval that it represents and the spectrum. Moreover, since this spectrum is infinite it is an improper subset of R. Pictorially, the more these lines (which represent the voter’s approval sets) overlap, the more the voters agree with each other. Within a linear society this results in an outcome that more voters approve. If any two voters have at least one candidate that they both approve than a linear society is super-agreeable. Restating this definition, a linear society (X, V, A) is super-agreeable if for any two voters x, y ∈ X there exists a candidate c such that c ∈ Ax ∩ Ay . When a linear society is super-agreeable there exists a candidate that every voter approves. However, it is unlikely that most linear societies would be super-agreeable. Thus, we seek a more common result. Instead of demanding that a linear society is super-agreeable we only require it to be agreeable. We define a linear society to be agreeable if within any set of three voters some pair of these three voters approves a candidate. This means for any x, y, z ∈ X there exists a candidate c that either satisfies c ∈ Ax ∩ Ay , c ∈ Ax ∩ Az , or c ∈ Ay ∩ Az . When the condition of being agreeable is met it leads to an equally strong result. 21 3 1 2 4 7 5 6 Figure 13: The agreement graph for the linear society in Figure 12. Theorem 5.2.1. If a linear society is agreeable, then there exists a candidate that has the approval of at least half the voters. Even this condition is difficult to meet. Hence, we provide a more general result. A linear society is (k, m)-agreeable if for any m voters there exists a candidate that at least k of those m voters approve. Thus, Theorem 5.2.1 generalizes to the following theorem. Theorem 5.2.2 (The Agreeable Linear Society Theorem). Let 2 ≤ k ≤ m. In a linear society with n voters that is (k, m)-agreeable, there exists a candidate that has the approval of at least n(k − 1)/(m − 1) voters. Note that the society in Figure 12 is a (2, 3)-agreeable society. Since there are seven voters in this case, using the notation of our theorem we have n = 7, k = 2 and m = 3. Thus, applying our theorem we are guaranteed a candidate that has the approval of at least 7(2 − 1)/(3 − 1) = 3.5 voters. This translates to four voters and any candidate whose profile falls in the shaded portion of Figure 12 satisfies this result. The rest of this section uses graph theory from combinatorics to further these results. 5.3 A Connection with Graphs Now we provide the comparison, created in this paper [3], between the earlier content of this section and graph theory. A graph G in combinatorics is a set of vertices V (G) and the edges in the set E(G) connecting these vertices. If two vertices u and v are connected then e = {u, v} is an edge in E(G) and u and v are adjacent. A graph G is connected if there exit edges in E(G) such that each vertex in V (G) is connected to every other vertex in V (G). This idea of a graph connects with approval voting through the idea of an agreement graph. From a society S we can create an agreement graph by first representing each of the voters in S by a vertex in V (G). We connect two vertices by an edge in E(G) if the corresponding voters have at least one profile that falls into both of their approval sets. Figure 13 provides the agreement graph constructed from the society in Figure 12. Note that voters 4 and 7 both agree on any of the platforms in the shaded region of Figure 12, which is represented in Figure 13 by the edge connecting vertex 4 with vertex 7. Similarly, since voter 7 and voter 2 do not agree on any platforms in the graph there is no edge connecting vertex 2 with vertex 7. For a society S and a platform p we use a(p) to denote the agreement number of p, where the approval number is the number of voters in S that approve platform p. For example, if p is a platform in the shaded portion of Figure 12 then a(p) = 4 because voters 4, 5, 6 and 7 all approve of platforms in this region. For a society S the agreement number a(s) is the maximum agreement number out of all of the platforms possible in S. If a society S has an agreement number equal to the number of voters then all voters have that platform in their approval set and the subsequent agreement graph would be a complete graph. A clique is a set of vertices such that each pair of vertices in the set are adjacent to each other. Thus, in Figure 13 vertices 1, 2 and 3 form a clique of size 3, as does the set of vertices 2, 4 and 5. The clique number of a graph G, denoted by ω(G), is the maximum integer q such that G has a clique of size q. As seen in Figure 13 our agreement graph has a clique of size 4 formed by vertices 4, 5, 6 and 7. This clique of size 4 is the largest clique in our graph. Hence, if we let G represent our agreement graph then ω(G) = 4. This means that a(G) = 4 = ω(G). This shared value for our example is indicative of a general result. For the agreement graph of a linear society, the clique number of the graph is the same value as the agreement number of that society. Given 22 the set up of the problem, this makes sense as both numbers count the maximum number of voters that all approve of the same platform or platforms. The authors of “Voting in Agreeable Societies” use this fact to prove further interesting results outside of the scope of this paper. For our purposes it is sufficient to note this connection and to see that although no voting method functions in the way we would like, namely following the rules of Arrow’s Theorem, it is possible to obtain results acceptable to voters. 6 Conclusion This paper provides a brief overview of some of the many aspects of social choice theory. Starting with the voting paradoxes that form the foundations of this field we built up to Arrow’s Theorem and the complexities surrounding this revolutionary result. Using a combination of combinatorics, geometry and linear algebra we tackled this theorem to conclude that the expectation of a transitive result is one of the main causes of Arrow’s conclusion. We then applied the holistic approach, employed in Arrow’s Theorem, of viewing all possible results at once to specific types of voting methods through our construction of voting dictionaries. Lastly, we analyzed the effectiveness of approval voting in finding a consensus among voters. Unfortunately, by only providing an overview, many aspects of voting theory could not make it into this paper. In particular, there are many applications of geometry relevant to this field other than those discussed in relation to Arrow’s Theorem. The interested reader may investigate such results using Saari’s Basic Geometry of Voting [8]. Another result not included in this paper is Saari’s method of constructing dictionaries and generating voter profiles with unexpected election results as discussed in Chapter 4 of his work Disposing Dictators, Demystifying Voting Paradoxes: Social Choice Analysis [9]. For proofs and extensions of the results discussed in Section 5 consult [3]. Further development and interest in voting theory is crucial for us to ensure that the opinion of the public is properly represented by our election results. This paper outlines problems found in many of the voting methods used to determine elections and make decisions that have a large global impact. While Arrow’s Theorem shows that there is no ideal voting method, analyses such as Saari’s dictionaries indicate that methods such as the Borda count might provide more accurate results. Consequently, advocates are vital to producing a change towards more reliable methods of determining these elections. By implementing the results from this field it could be possible to prevent elections such as the 2000 United States presidential election, where the wishes of the voters are not reflected by the election result. References [1] Arrow, Kenneth J. ‘’A Difficulty in the Concept of Social Welfare.” The Journal of Political Economy 58 (1950): 328-346. [2] Arrow, Kenneth J. (1963). Social Choice and Individual Values (2nd ed.). New York: John Wiley & Sons, Inc. [3] Berg, Deborah E., Serguei Norine, Francis Edward Su, Robin Thomas and Paul Wollan. “Voting in Agreeable Societies.” The American Mathematical Monthly 117 (2010): 27-39. [4] Brualdi, Richard A. (1999). Introductory Combinatorics (3rd ed.). Upper Saddle River, NJ: Prentice Hall. [5] Burger, Edward B., and Michael Starbird. (2005). The Heart of Mathematics: An invitation to effective thinking (2nd ed.). Emeryville, CA: Key College Publishing. [6] Cameron, Peter J. (1994). Combinatorics: Topics, Techniques, Algorithms. Cambridge: Cambridge University Press. [7] Reilly, Benjamin. “Social Choice in the South Seas: Electoral Innovation and the Borda Count in the Pacific Island Countries.” International Political Science Review 23, no. 4 (2002): 355-372. [8] Saari, Donald G. (1995). Basic Geometry of Voting. Berlin: Springer. 23 [9] Saari, Donald G. (2008). Disposing Dictators, Demystifying Voting Paradoxes: Social Choice Analysis. New York, NY: Cambridge University Press. 24