Linear Algebra/Topic: Voting Paradoxes/Solutions

Solutions

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.

1. 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.
2. 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?
3. 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.

Answer

This is one example that yields a non-rational preference order for a single voter.

	character	experience	policies
Democrat	most	middle	least
Republican	middle	least	most
Third	least	most	middle

The Democrat is preferred to the Republican for character and experience. The Republican is preferred to the Third for character and policies. And, the Third is preferred to the Democrat for experience and policies.

Problem 2

Compute the values in the table of decompositions.

Answer

First, compare the $D>R>T$ decomposition that was done out in the Topic with the decomposition of the opposite $T>R>D$ voter.

${\begin{pmatrix}-1\\1\\1\end{pmatrix}}={\frac {1}{3}}\cdot {\begin{pmatrix}1\\1\\1\end{pmatrix}}+{\frac {2}{3}}\cdot {\begin{pmatrix}-1\\1\\0\end{pmatrix}}+{\frac {2}{3}}\cdot {\begin{pmatrix}-1\\0\\1\end{pmatrix}}\quad {\text{and}}\quad {\begin{pmatrix}1\\-1\\-1\end{pmatrix}}=d_{1}\cdot {\begin{pmatrix}1\\1\\1\end{pmatrix}}+d_{2}\cdot {\begin{pmatrix}-1\\1\\0\end{pmatrix}}+d_{3}\cdot {\begin{pmatrix}-1\\0\\1\end{pmatrix}}$

Obviously, the second is the negative of the first, and so $d_{1}=-1/3$, $d_{2}=-2/3$, and $d_{3}=-2/3$. This principle holds for any pair of opposite voters, and so we need only do the computation for a voter from the second row, and a voter from the third row. For a positive spin voter in the second row,

${\begin{array}{*{3}{rc}r}c_{1}&-&c_{2}&-&c_{3}&=&1\\c_{1}&+&c_{2}&&&=&1\\c_{1}&&&+&c_{3}&=&-1\end{array}}\;{\xrightarrow[{-\rho _{1}+\rho _{3}}]{-\rho _{1}+\rho _{2}}}\;{\xrightarrow[{}]{(-1/2)\rho _{2}+\rho _{3}}}\;{\begin{array}{*{3}{rc}r}c_{1}&-&c_{2}&-&c_{3}&=&1\\&&2c_{2}&+&c_{3}&=&0\\&&&&(3/2)c_{3}&=&-2\end{array}}$

gives $c_{3}=-4/3$, $c_{2}=2/3$, and $c_{1}=1/3$. For a positive spin voter in the third row,

${\begin{array}{*{3}{rc}r}c_{1}&-&c_{2}&-&c_{3}&=&1\\c_{1}&+&c_{2}&&&=&-1\\c_{1}&&&+&c_{3}&=&1\end{array}}\;{\xrightarrow[{-\rho _{1}+\rho _{3}}]{-\rho _{1}+\rho _{2}}}\;{\xrightarrow[{}]{(-1/2)\rho _{2}+\rho _{3}}}\;{\begin{array}{*{3}{rc}r}c_{1}&-&c_{2}&-&c_{3}&=&1\\&&2c_{2}&+&c_{3}&=&-2\\&&&&(3/2)c_{3}&=&1\end{array}}$

gives $c_{3}=2/3$, $c_{2}=-4/3$, and $c_{1}=1/3$.

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?

Answer

The mock election corresponds to the Voting preferences table above in the way shown in the first table, and after cancellation the result is the second table.

positive spin      negative spin      $D>R>T$   5 voters   $T>R>D$   2 voters   $R>T>D$   8 voters   $D>T>R$   4 voters   $T>D>R$   8 voters   $R>D>T$   2 voters

positive spin      negative spin      $D>R>T$   3 voters   $T>R>D$   –   $R>T>D$   4 voters   $D>T>R$   –   $T>D>R$   6 voters   $R>D>T$   –

All three come from the same side of the table (the left), as the result from this Topic says must happen. Tallying the election can now proceed, using the cancelled numbers

$3\cdot \,$ $+4\cdot \,$$+6\cdot$$\,=\,$

to get the same outcome.

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.

1. Continuing the positive cycle case considered in the proof, use the two inequalities $0\leq a-b+c$ and $0\leq -a+b+c$ to show that $|a-b|\leq c$.
2. Also show that $c\leq a+b$, and hence that $|a-b|\leq c\leq a+b$.
3. 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.
4. Can the opposite happen; can addition of one voter with a "wrong" spin cause a cycle to appear?
5. Give a condition that is both necessary and sufficient to get a majority cycle.

Answer

1. The two can be rewritten as $-c\leq a-b$ and $-c\leq b-a$. Either $a-b$ or $b-a$ is nonpositive and so $-c\leq -|a-b|$, as required.
2. This is immediate from the supposition that $0\leq a+b-c$.
3. A trivial example starts with the zero-voter election and adds any one voter. A more interesting example is to take the Political Science mock election and add two $T>D>R$ voters (they can be added one at a time, to satisfy the "addition of one more voter" criteria in the question). Observe that the additional voters have positive spin, which is the spin of the votes remaining after cancellation in the original mock election. This is the resulting table of voters, and next to it is the result of cancellation.

   positive spin      negative spin      $D>R>T$   5 voters   $T>R>D$   2 voters   $R>T>D$   8 voters   $D>T>R$   4 voters   $T>D>R$   10 voters   $R>D>T$   2 voters

   positive spin      negative spin      $D>R>T$   3 voters   $T>R>D$   –   $R>T>D$   4 voters   $D>T>R$   –   $T>D>R$   8 voters   $R>D>T$   –

   The election, using the cancelled numbers, is this.

   $3\cdot \,$$\,+4\cdot \,$$\,+8\cdot \,$$\,=\,$

   The majority cycle has indeed disappeared.

4. One such condition is that, after cancellation, all three be nonnegative or all three be nonpositive, and: $|c|<|a+b|$ and $|b|<|a+c|$ and $|a|<|b+c|$. This follows from this diagram.

   $\,+\,$$\,+\,$$\,=\,$

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.

1. 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.)
2. Show that for any number of voters greater than one, there is an election involving that many voters that results in a majority cycle.

Answer

1. A two-voter election can have a majority cycle in two ways. First, the two voters could be opposites, resulting after cancellation in the trivial election (with the majority cycle of all zeroes). Second, the two voters could have the same spin but come from different rows, as here.

   $1\cdot \,$$\,+1\cdot \,$$\,+0\cdot \,$$\,=\,$

2. There are two cases. An even number of voters can split half and half into opposites, e.g., half the voters are $D>R>T$ and half are $T>R>D$. Then cancellation gives the trivial election. If the number of voters is greater than one and odd (of the form $2k+1$ with $k>0$) then using the cycle diagram from the proof,

   $\,+\,$$\,+\,$$\,=\,$

   we can take $a=k$ and $b=k$ and $c=1$. Because $k>0$, this is a majority cycle.

Problem 6

Let $U$ be a subspace of $\mathbb {R} ^{3}$. Prove that the set $U^{\perp }=\{{\vec {v}}\,{\big |}\,{\vec {v}}\cdot {\vec {u}}=0{\text{ for all }}{\vec {u}}\in U\}$ of vectors that are perpendicular to each vector in $U$ is also a subspace of $\mathbb {R} ^{3}$.

Answer

It is nonempty because it contains the zero vector. To see that it is closed under linear combinations of two of its members, suppose that ${\vec {v}}_{1}$ and ${\vec {v}}_{2}$ are in $U^{\perp }$ and consider $c_{1}{\vec {v}}_{1}+c_{2}{\vec {v}}_{2}$. For any ${\vec {u}}\in U$,

$(c_{1}{\vec {v}}_{1}+c_{2}{\vec {v}}_{2})\cdot {\vec {u}}=c_{1}({\vec {v}}_{1}\cdot {\vec {u}})+c_{2}({\vec {v}}_{2}\cdot {\vec {u}})=c_{1}\cdot 0+c_{2}\cdot 0=0$

and so $c_{1}{\vec {v}}_{1}+c_{2}{\vec {v}}_{2}\in U^{\perp }$.