Voting Paradoxes

Imagine that a Political Science class studying the American presidential process holds a mock election. The $29$ class members rank the Democratic Party, Republican Party, and Third Party nominees, from most preferred to least preferred ($>$ means ‘is preferred to’).

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 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.

This is a voting paradox, specifically, a majority cycle.

Mathematicians study voting paradoxes in part because of their implications for practical politics. For instance, the instructor can manipulate this class into choosing the Democrat as the overall winner by first asking for a vote between the Republican and the Third, and then asking for a vote between the winner of that contest, who will be the Republican, and the Democrat. By similar manipulations the instructor can make any of the other two candidates come out as the winner. (We will stick to three-candidate elections but the same thing happens in larger elections.)

Mathematicians also study voting paradoxes simply because they are interesting. One interesting aspect is that the group’s overall majority cycle occurs despite that each single voter’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 components of that aggregate, the preference lists. However we can use linear algebra 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 canceling.

For this, 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 decomposition table.

Now, to conduct the election we linearly combine these descriptions; for instance, the Political Science mock election

$$ 5 ⋅ + 4 ⋅ + ⋯ + 2 ⋅ $$

yields the circular group preference shown earlier.

Of course, taking linear combinations is linear algebra. The graphical cycle notation is suggestive but inconvenient so we use column vectors by starting at the $D$ and taking the numbers from the cycle in counterclockwise order. Thus, we represent the mock election and a single $D>R>T$ vote 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 ${\mathrm{ℝ}}^3$.

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

For the second part, consider the set of vectors that are perpendicular to all of the vectors in $C$. Exercise 6 shows that this is a subspace

$$\begin{array}{rl}{C}^{\perp }& =\{\left(\begin{array}{c}{c}_1\\ c_2\\ c_3\end{array}\right)\mid \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 \mathrm{ℝ}\}\\ & =\{\left(\begin{array}{c}{c}_1\\ c_2\\ c_3\end{array}\right)\mid 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)\mid c_2,c_3\in \mathrm{ℝ}\}\end{array}$$

(read that aloud as “$C$ perp”). So we are led to this basis for ${\mathrm{ℝ}}^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. We represent that voter with respect to the basis

$$\begin{array}{rcrcrcr}{c}_1& -& c_2& -& c_3& =& -1\\ c_1& +& c_2& & & =& 1\\ c_1& & & +& c_3& =& 1\end{array}\underset{\begin{array}{l}-{\rho }_1+{\rho }_3\end{array}}{\overset{-{\rho }_1+{\rho }_2\phantom{(}}{⟶}}\underset{\begin{array}{}\end{array}}{\overset{(-1/2){\rho }_2+{\rho }_3\phantom{(}}{⟶}}\begin{array}{rcrcrcr}{c}_1& -& c_2& -& c_3& =& -1\\ & & 2c_2& +& c_3& =& 2\\ & & & & (3/2)c_3& =& 1\end{array}$$

using the coordinates $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 we can see that this $D>R>T$ voter’s rational preference list does 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. We say that the first voter has positive spin since the cycle part is with the direction that we have chosen for the arrows, while the second voter’s spin is negative.

The fact 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 table below contains the three pairs of opposite preference lists. For instance, the top line contains the voters discussed above.

positive spin	negative spin
$\text{Democrat}>\text{Republican}>\text{Third}$ $ = + $	$\text{Third}>\text{Republican}>\text{Democrat}$ $ = + $
$\text{Republican}>\text{Third}>\text{Democrat}$ $ = + $	$\text{Democrat}>\text{Third}>\text{Republican}$ $ = + $
$\text{Third}>\text{Democrat}>\text{Republican}$ $ = + $	$\text{Republican}>\text{Democrat}>\text{Third}$ $ = + $

If we conduct the election as just described then after the cancellation of as many opposite pairs of voters as possible there will remain three sets of preference lists: one set from the first row, one from the second row, and one 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 Exercise 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 we have canceled opposite preference orders and are left with one set of preference lists for each of the three rows. Consider the first row’s remaining preference lists. They could be from the first row’s left or right (or between, since the lists could have canceled exactly). We shall write

where $a$ is an integer that is positive if the remaining lists are on the left, where $a$ is negative if the lists are on the right, and zero if the cancellation was perfect. Similarly we have integers $b$ and $c$ for the second and third rows, which can each be positive, negative, or zero.

Then the election is determined by this sum.

$$ + + = $$

A voting paradox occurs when the three numbers in the total cycle on the right, $-a+b+c$ and $a-b+c$ and $a+b-c$, are all nonnegative or all nonpositive. We will prove this occurs only when either all three of $a$, $b$, and $c$ are nonnegative or all three are nonpositive.

Let the total cycle numbers be nonnegative; the other case is similar.

$$\begin{array}{rcrcrcr}-a& +& b& +& c& \ge & 0\\ a& -& b& +& c& \ge & 0\\ a& +& b& -& c& \ge & 0\end{array}$$

Add the first two rows to see that $c\ge 0$. Add the first and third rows for $b\ge 0$. And, the second and third rows together give $a\ge 0$. Thus if the total cycle is nonnegative then in each row the remaining preference lists are from the table’s left. 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 Exercise 4.

Voting theory and associated topics are the subject of current research. There are many intriguing results, notably those produced by K Arrow [Arrow] who won the Nobel Prize in part for this work, showing that no voting system is entirely fair (for a reasonable definition of “fair”). Some good introductory articles are [Gardner, 1970], [Gardner, 1974], [Gardner, 1980], and [Neimi & Riker]. [Taylor] is a readable text. The long list of cases from recent American political history in [Poundstone] shows these paradoxes are routinely manipulated in practice. (On the other hand, quite recent research shows that computing how to manipulate elections can in general be unfeasible, but this is beyond our scope.) This Topic is drawn from [Zwicker]. (Author’s Note: I would like to thank Professor Zwicker for his kind and illuminating discussions.)

References cited in this section