Linear Algebra/Topic: Voting Paradoxes

Template:Navigation 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.

‎

Template:AnchorThis 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. Template:AnchorOne 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 Template:Harv 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 $D$, $R$, and $T$, we can describe how a voter with preference order $D>R>T$ contributes to the above cycle.

(The negative sign is here because the arrow describes $T$ as preferred to $D$, 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

$5\cdot$$+4\cdot$$+\cdots +2\cdot$

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 $D$ and taking the numbers from the cycle in counterclockwise order. Thus, the mock election and a single $D>R>T$ vote are represented in this way.

$\left(\begin{array}{c}7\\ 1\\ 5\end{array}\right)\text{and}\left(\begin{array}{c}-1\\ 1\\ 1\end{array}\right)$

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 ${ℝ}^3$.

$C=\{\left(\begin{array}{c}k\\ k\\ k\end{array}\right)|k\in ℝ\}=\{k\cdot \left(\begin{array}{c}1\\ 1\\ 1\end{array}\right)|k\in ℝ\}$

For the second part, consider the subspace (see Problem 6) of vectors that are perpendicular to all of the vectors in $C$.

$C^{\perp }=\{\left(\begin{array}{c}{c}_1\\ c_2\\ c_3\end{array}\right)|\left(\begin{array}{c}{c}_1\\ c_2\\ c_3\end{array}\right)\cdot \left(\begin{array}{c}k\\ k\\ k\end{array}\right)=0\text{ for all }k\in ℝ\}$

$=\{\left(\begin{array}{c}{c}_1\\ c_2\\ c_3\end{array}\right)|c_1+c_2+c_3=0\}=\{c_2\left(\begin{array}{c}-1\\ 1\\ 0\end{array}\right)+c_3\left(\begin{array}{c}-1\\ 0\\ 1\end{array}\right)|c_2,c_3\in ℝ\}$

(Read that aloud as "$C$ perp".) So we are led to this basis for ${ℝ}^3$.

$⟨\left(\begin{array}{c}1\\ 1\\ 1\end{array}\right),\left(\begin{array}{c}-1\\ 1\\ 0\end{array}\right),\left(\begin{array}{c}-1\\ 0\\ 1\end{array}\right)⟩$

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 $C$ and $C^{\perp }$.)

For example, consider the $D>R>T$ voter discussed above. The representation in terms of the basis is easily found,

$\begin{array}{ccc}\begin{array}{ccccccc}{c}_1& -& c_2& -& c_3& =& -1\\ c_1& +& c_2& & & =& 1\\ c_1& & & +& c_3& =& 1\end{array}& \underset{-{\rho }_1+{\rho }_3}{\overset{-{\rho }_1+{\rho }_2}{\to }}\underset{}{\overset{(-1/2){\rho }_2+{\rho }_3}{\to }}& \begin{array}{ccccccc}{c}_1& -& c_2& -& c_3& =& -1\\ & & 2c_2& +& c_3& =& 2\\ & & & & (3/2)c_3& =& 1\end{array}\end{array}$

so that $c_1=1/3$, $c_2=2/3$, and $c_3=2/3$. Then

$\left(\begin{array}{c}-1\\ 1\\ 1\end{array}\right)=\frac{1}{3}\cdot \left(\begin{array}{c}1\\ 1\\ 1\end{array}\right)+\frac{2}{3}\cdot \left(\begin{array}{c}-1\\ 1\\ 0\end{array}\right)+\frac{2}{3}\cdot \left(\begin{array}{c}-1\\ 0\\ 1\end{array}\right)=\left(\begin{array}{c}1/3\\ 1/3\\ 1/3\end{array}\right)+\left(\begin{array}{c}-4/3\\ 2/3\\ 2/3\end{array}\right)$

gives the desired decomposition into a cyclic part and an acyclic part.

$=$$+$

Thus, this $D>R>T$ voter's rational preference list can indeed be seen to have a cyclic part.

The $T>R>D$ voter is opposite to the one just considered in that the "$>$" symbols are reversed. This voter's decomposition

$=$$+$

shows that these opposite preferences have decompositions that are opposite. Template:AnchorWe 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.

Template:Anchor

Voting preferences

positive sign	negative spin
Democrat > Republican > Third $=$$+$	Third > Republican > Democrat $=$$+$
Republican > Third > Democrat $=$$+$	Democrat > Third > Republican $=$$+$
Third > Democrat > Republican $=$$+$	Republican > Democrat > Third $=$$+$

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 $a$, $b$, and $c$ could be positive, negative, or zero).

$+$$+$$=$

A voting paradox occurs when the three numbers on the right, $a-b+c$ and $a+b-c$ and $-a+b+c$, are all nonnegative or all nonpositive. On the left, at least two of the three numbers, $a$ and $b$ and $c$, are both nonnegative or both nonpositive. We can assume that they are $a$ and $b$. That makes four cases: the cycle is nonnegative and $a$ and $b$ are nonnegative, the cycle is nonpositive and $a$ and $b$ 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 $a$ and $b$ are nonnegative. The conditions $0\le a-b+c$ and $0\le -a+b+c$ add to give that $0\le 2c$, which implies that $c$ 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 Template:Harv, 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 Template:Harv, Template:Harv, Template:Harv, and Template:Harv. A quite readable recent book is Template:Harv. The long list of cases from recent American political history given in Template:Harv show that manipulation of these paradoxes is routine in practice (and the author proposes a solution).

This Topic is largely drawn from Template:Harv. (Author's Note: I would like to thank Professor Zwicker for his kind and illuminating discussions.)

Exercises

/Solutions/

References

• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation