Linear Algebra, Topic: Voting Paradoxes

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

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.

‎

This 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. One 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 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 ⋅ $$\ + 4 ⋅ $$\ + ⋯ + 2 ⋅ $
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.

( \begin{matrix}7 \\ 1 \\ 5\end{matrix} ) \ \text{and} \ ( \begin{matrix}− 1 \\ 1 \\ 1\end{matrix} )

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 = \{ ( \begin{matrix}k \\ k \\ k\end{matrix} ) \ | \ k ∈ ℝ \} = \{ k ⋅ ( \begin{matrix}1 \\ 1 \\ 1\end{matrix} ) \ | \ k ∈ ℝ \}

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

{C}^{⊥} = \{ ( \begin{matrix}{c}_{1} \\ {c}_{2} \\ {c}_{3}\end{matrix} ) \ | \ ( \begin{matrix}{c}_{1} \\ {c}_{2} \\ {c}_{3}\end{matrix} ) ⋅ ( \begin{matrix}k \\ k \\ k\end{matrix} ) = 0 \text{ for all } k ∈ ℝ \}

= \{ ( \begin{matrix}{c}_{1} \\ {c}_{2} \\ {c}_{3}\end{matrix} ) \ | \ {c}_{1} + {c}_{2} + {c}_{3} = 0 \} = \{ {c}_{2} ( \begin{matrix}− 1 \\ 1 \\ 0\end{matrix} ) + {c}_{3} ( \begin{matrix}− 1 \\ 0 \\ 1\end{matrix} ) \ | \ {c}_{2} , {c}_{3} ∈ ℝ \}

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

⟨ ( \begin{matrix}1 \\ 1 \\ 1\end{matrix} ) , ( \begin{matrix}− 1 \\ 1 \\ 0\end{matrix} ) , ( \begin{matrix}− 1 \\ 0 \\ 1\end{matrix} ) ⟩

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}^{⊥}.)

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

\begin{matrix}\begin{matrix}{c}_{1} & − & {c}_{2} & − & {c}_{3} & = & − 1 \\ {c}_{1} & + & {c}_{2} & & & = & 1 \\ {c}_{1} & & & + & {c}_{3} & = & 1\end{matrix} & {→}_{− {ρ}_{1} + {ρ}_{3} \ }^{− {ρ}_{1} + {ρ}_{2}} \ {→}_{ \ }^{( − 1 / 2 ) {ρ}_{2} + {ρ}_{3}} & \begin{matrix}{c}_{1} & − & {c}_{2} & − & {c}_{3} & = & − 1 \\ & & 2 {c}_{2} & + & {c}_{3} & = & 2 \\ & & & & ( 3 / 2 ) {c}_{3} & = & 1\end{matrix}\end{matrix}

so that {c}_{1} = 1 / 3, {c}_{2} = 2 / 3, and {c}_{3} = 2 / 3. Then

( \begin{matrix}− 1 \\ 1 \\ 1\end{matrix} ) = \frac{1}{3} ⋅ ( \begin{matrix}1 \\ 1 \\ 1\end{matrix} ) + \frac{2}{3} ⋅ ( \begin{matrix}− 1 \\ 1 \\ 0\end{matrix} ) + \frac{2}{3} ⋅ ( \begin{matrix}− 1 \\ 0 \\ 1\end{matrix} ) = ( \begin{matrix}1 / 3 \\ 1 / 3 \\ 1 / 3\end{matrix} ) + ( \begin{matrix}− 4 / 3 \\ 2 / 3 \\ 2 / 3\end{matrix} )

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

$\ = $ $\ + $ | 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 ≤ a − b + c and {}0 ≤ − a + b + c add to give
that {}0 ≤ 2 c, 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 (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) harv error: no target: CITEREFNeimiRiker_1976 (help).
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 1

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.

• 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.
• 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?
• 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 2

Compute the values in the table of decompositions.

Problem 3

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 4

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.

• Continuing the positive cycle case considered in the proof, use the two inequalities {}0 ≤ a − b + c and {}0 ≤ − a + b + c to show that | a − b | ≤ c.
• Also show that c ≤ a + b, and hence that | a − b | ≤ c ≤ a + b.
• 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.
• Can the opposite happen; can addition of one voter with a "wrong" spin cause a cycle to appear?
• 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.

• 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.)
• 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 6

Let U be a subspace of {ℝ}^{3}. Prove that the set {U}^{⊥} = \{ \overset{→}{v} \ | \ \overset{→}{v} ⋅ \overset{→}{u} = 0 \text{ for all } \overset{→}{u} ∈ U \} of vectors that are perpendicular to each vector in U is also a subspace of {ℝ}^{3}.

Solutions

References

• Arrow, J. (1963), Social Choice and Individual Values, Wiley.
• Gardner, Martin (April 1970), "Mathematical Games, Some mathematical curiosities embedded in the solar system", Scientific American: 108–112{{citation}}: CS1 maint: year (link).
• Gardner, Martin (October 1974), "Mathematical Games, On the paradoxical situations that arise from nontransitive relations", Scientific American{{citation}}: CS1 maint: year (link).
• Gardner, Martin (October 1980), "Mathematical Games, From counting votes to making votes count: the mathematics of elections", Scientific American{{citation}}: CS1 maint: year (link).
• Neimi, G.; Riker, W. (June 1976), "The Choice of Voting Systems", Scientific American: 21–27{{citation}}: CS1 maint: year (link).
• Poundstone, W. (2008), Gaming the vote, Hill and Wang, ISBN 978-0-8090-4893-9.
• Taylor, Alan D. (1995), Mathematics and Politics: Strategy, Voting, Power, and Proof, Springer-Verlag.
• Zwicker, S. (1991), "The Voters' Paradox, Spin, and the Borda Count", Mathematical Social Sciences, 22: 187–227

Where this page came from

This page was imported from Wikibooks. From “Linear Algebra” on Wikibooks, by its contributors, under CC BY-SA 4.0. Changed here: set as a page; navigation and edit links left out; each image under its own licence, credited in its caption.

Nobody has written it yet — it is the source material at a new address, which is why search engines are asked to skip it and why no one earns from it. It is up for grabs: take it on, and it is yours to rewrite and to earn from.