Linear Algebra/Topic: Voting Paradoxes

Linear Algebra Topic: Voting Paradoxes Topic: Crystals Topic: Dimensional Analysis Imagine that a Political Science class studying the American presidential process holds a mock election. Members of the class are asked to rank, from most preferred to least preferred, the nominees from the Democratic Party, the Republican Party, and the Third Party, and this is the result ( means "is preferred to"). Preference order     Number with   that preference Democrat > Republican > Third     5 Democrat > Third > Republican     4 Republican > Democrat > Third     2 Republican > Third > Democrat     8 Third > Democrat > Republican     8 Third > Republican > Democrat     2 Total     29 What is the preference of the group as a whole? Overall, the group prefers the Democrat to the Republican by five votes; seventeen voters ranked the Democrat above the Republican versus twelve the other way. And, overall, the group prefers the Republican to the Third's nominee, fifteen to fourteen. But, strangely enough, the group also prefers the Third to the Democrat, eighteen to eleven. 200px|center‎ voting paradoxThis is an example of a voting paradox, specifically, a majority cycle. Voting paradoxes are studied in part because of their implications for practical politics. For instance, the instructor can manipulate the class into choosing the Democrat as the overall winner by first asking the class to choose between the Republican and the Third, and then asking the class to choose between the winner of that contest, the Republican, and the Democrat. By similar manipulations, any of the other two candidates can be made to come out as the winner. (In this Topic we will stick to three-candidate elections, but similar results apply to larger elections.) Voting paradoxes are also studied simply because they are mathematically interesting. rational preferenceOne interesting aspect is that the group's overall majority cycle occurs despite that each single voters's preference list is rational— in a straight-line order. That is, the majority cycle seems to arise in the aggregate, without being present in the elements of that aggregate, the preference lists. Recently, however, linear algebra has been used Zwicker 1991 to argue that a tendency toward cyclic preference is actually present in each voter's list, and that it surfaces when there is more adding of the tendency than cancelling. For this argument, abbreviating the choices as , , and , we can describe how a voter with preference order contributes to the above cycle. 175px|center (The negative sign is here because the arrow describes as preferred to , but this voter likes them the other way.) The descriptions for the other preference lists are in the Voting preferences table below. Now, to conduct the election we linearly combine these descriptions; for instance, the Political Science mock election 100px100px100px yields the circular group preference shown earlier. Of course, taking linear combinations is linear algebra. The above cycle notation is suggestive but inconvienent, so we temporarily switch to using column vectors by starting at the and taking the numbers from the cycle in counterclockwise order. Thus, the mock election and a single vote are represented in this way. We will decompose vote vectors into two parts, one cyclic and the other acyclic. For the first part, we say that a vector is purely cyclic if it is in this subspace of . For the second part, consider the subspace (see Problem 6) of vectors that are perpendicular to all of the vectors in . (Read that aloud as " perp".) So we are led to this basis for . We can represent votes with respect to this basis, and thereby decompose them into a cyclic part and an acyclic part. (Note for readers who have covered the optional section in this chapter: that is, the space is the direct sum of and .) For example, consider the voter discussed above. The representation in terms of the basis is easily found, so that , , and . Then gives the desired decomposition into a cyclic part and an acyclic part. x100pxx100pxx100px Thus, this voter's rational preference list can indeed be seen to have a cyclic part. The voter is opposite to the one just considered in that the "" symbols are reversed. This voter's decomposition x100pxx100pxx100px shows that these opposite preferences have decompositions that are opposite. spinWe say that the first voter has positive spin since the cycle part is with the direction we have chosen for the arrows, while the second voter's spin is negative. The fact that that these opposite voters cancel each other is reflected in the fact that their vote vectors add to zero. This suggests an alternate way to tally an election. We could first cancel as many opposite preference lists as possible, and then determine the outcome by adding the remaining lists. The rows of the table below contain the three pairs of opposite preference lists. The columns group those pairs by spin. For instance, the first row contains the two voters just considered. voting +Voting preferencespositive signnegative spinDemocrat > Republican > Third x100pxx100pxx100pxThird > Republican > Democrat x100pxx100pxx100pxRepublican > Third > Democrat x100pxx100pxx100pxDemocrat > Third > Republican x100pxx100pxx100pxThird > Democrat > Republican x100pxx100pxx100pxRepublican > Democrat > Third x100pxx100pxx100px If we conduct the election as just described then after the cancellation of as many opposite pairs of voters as possible, there will be left three sets of preference lists, one set from the first row, one set from the second row, and one set from the third row. We will finish by proving that a voting paradox can happen only if the spins of these three sets are in the same direction. That is, for a voting paradox to occur, the three remaining sets must all come from the left of the table or all come from the right (see Problem 3). This shows that there is some connection between the majority cycle and the decomposition that we are using---a voting paradox can happen only when the tendencies toward cyclic preference reinforce each other. For the proof, assume that opposite preference orders have been cancelled, and we are left with one set of preference lists from each of the three rows. Consider the sum of these three (here, the numbers , , and could be positive, negative, or zero). x100pxx100pxx100pxx100px A voting paradox occurs when the three numbers on the right, and and , are all nonnegative or all nonpositive. On the left, at least two of the three numbers, and and , are both nonnegative or both nonpositive. We can assume that they are and . That makes four cases: the cycle is nonnegative and and are nonnegative, the cycle is nonpositive and and are nonpositive, etc. We will do only the first case, since the second is similar and the other two are also easy. So assume that the cycle is nonnegative and that and are nonnegative. The conditions and add to give that , which implies that is also nonnegative, as desired. That ends the proof. This result says only that having all three spin in the same direction is a necessary condition for a majority cycle. It is not sufficient; see Problem 4. Voting theory and associated topics are the subject of current research. There are many intriguing results, most notably the one produced by K. Arrow Arrow 1963, who won the Nobel Prize in part for this work, showing that no voting system is entirely fair (for a reasonable definition of "fair"). For more information, some good introductory articles are Gardner 1970, Gardner 1974, Gardner 1980, and Neimi Riker 1976. A quite readable recent book is Taylor 1995. The long list of cases from recent American political history given in Poundstone 2008 show that manipulation of these paradoxes is routine in practice (and the author proposes a solution). This Topic is largely drawn from Zwicker 1991. (Author's Note: I would like to thank Professor Zwicker for his kind and illuminating discussions.) Exercises Problem 1exer:IrrIndVote Here is a reasonable way in which a voter could have a cyclic preference. Suppose that this voter ranks each candidate on each of three criteria. <li> Draw up a table with the rows labelled "Democrat", "Republican", and "Third", and the columns labelled "character", "experience", and "policies". Inside each column, rank some candidate as most preferred, rank another as in the middle, and rank the remaining oneas least preferred. <li> In this ranking, is the Democrat preferred to the Republican in (at least) two out of three criteria, or vice versa? Is the Republican preferred to the Third? <li> Does the table that was just constructed have a cyclic preference order? If not, make one that does. So it is possible for a voter to have a cyclic preference among candidates. The paradox described above, however, is that even if each voter has a straight-line preference list, a cyclic preference can still arise for the entire group. Problem 2exer:VoteCalcTable Compute the values in the table of decompositions. Problem 3exer:CancelPolSci Do the cancellations of opposite preference orders for the Political Science class's mock election. Are all the remaining preferences from the left three rows of the table or from the right? Problem 4exer:VoterCondNotSuff The necessary condition that is proved above—a voting paradox can happen only if all three preference lists remaining after cancellation have the same spin—is not also sufficient. <li> Continuing the positive cycle case considered in the proof, use the two inequalities and to show that . <li> Also show that , and hence that . <li> Give an example of a vote where there is a majority cycle, and addition of one more voter with the same spin causes the cycle to go away. <li> Can the opposite happen; can addition of one voter with a "wrong" spin cause a cycle to appear? <li> Give a condition that is both necessary and sufficient to get a majority cycle. Problem 5 A one-voter election cannot have a majority cycle because of the requirement that we've imposed that the voter's list must be rational. <li> Show that a two-voter election may have a majority cycle. (We consider the group preference a majority cycle if all three group totals are nonnegative or if all three are nonpositive---that is, we allow some zero's in the group preference.) <li> Show that for any number of voters greater than one, there is an election involving that many voters that results in a majority cycle. Problem 6exer:PerpIsSubSp Let be a subspace of . Prove that the set of vectors that are perpendicular to each vector in is also a subspace of . /Solutions/ References J. Arrow Social Choice and Individual Values Wiley 1963. Martin Gardner Mathematical Games, Some mathematical curiosities embedded in the solar system Scientific American April 1970 108-112. Martin Gardner Mathematical Games, On the paradoxical situations that arise from nontransitive relations Scientific American October 1974. Martin Gardner Mathematical Games, From counting votes to making votes count: the mathematics of elections Scientific American October 1980. G. Neimi W. Riker The Choice of Voting Systems Scientific American June 1976 21-27. W. Poundstone Gaming the vote Hill and Wang 2008 978-0-8090-4893-9. Alan D. Taylor Mathematics and Politics: Strategy, Voting, Power, and Proof Springer-Verlag 1995. S. Zwicker The Voters' Paradox, Spin, and the Borda Count Mathematical Social Sciences 1991 22 187-227 Linear Algebra Topic: Voting Paradoxes Topic: Crystals Topic: Dimensional Analysis