Namespaces
Variants
Actions

Voting paradoxes

From Encyclopedia of Mathematics
Revision as of 13:41, 17 April 2014 by Ivan (talk | contribs) (TeX)
Jump to: navigation, search

Voting paradoxes describe counter-intuitive election outcomes. The mathematical study started in 1770 when J.C. Borda [a1] constructed an example to argue that the plurality vote (where each voter votes for one candidate) used to select members to the French Academy of Science was flawed. Borda's example has $5$ voters with the (complete, transitive) preferences $A\succ C\succ B$, $4$ with $B\succ C\succ A$, and $3$ with $C\succ B\succ A$. Here, the plurality ranking of $A\succ B\succ C$ conflicts with the pairwise rankings of $C\succ A$, $C\succ B$, $B\succ A$ with the respective tallies of $7:5$, $8:4$, $7:5$. Borda suggested an alternative method, the Borda count, where with $n$ alternatives a voter's $j$th ranked candidate receives $n-j$ points, $j=1,\ldots,n.$ The Borda count outcome for the example is the more reasonable $C\succ B\succ A$ with the $15:11:10$ tally.

More generally, an $n\geq3$ candidate election can be tallied with a voting vector $\mathbf w^n=(w_1,\ldots,w_n)$ where $w_j\geq w_{j+1}$, $j=1,\ldots,n-1,$ and $w_1>w_n=0$. (The plurality vote corresponds to $(1,0,\ldots,0)$ while the Borda count is $(n-1,n-2,\ldots,1,0).$) With the infinite number of ways to tally ballots, P.S. Laplace and other mathematicians started a two-century controversy by questioning which $\mathbf w^n$ would be "optimal" . The difficulty of this area is partially captured by Arrow's assertion that no procedure does what is commonly expected (cf. Arrow impossibility theorem). See [a2], [a3] for a flavour of the rich history of this area and [a7] for a mathematical introduction.

All paradoxes.

What makes voting paradoxes difficult to analyze is that they are "counter-intuitive" , so it is not clear what to search for. Consequently, while several paradoxes have been discovered (e.g., see [a5]), they are limited. However, by using symmetry and arguments from chaotic dynamics, all possible voting paradoxes finally have been characterized [a6], [a8]. To describe them, notice that $n\geq3$ alternatives define $2^n-(n+1)$ subsets with two or more candidates; for each subset, choose a voting vector. D. Saari showed that for almost-all choices of voting vectors, "anything can happen" . Namely, for each of $2^n-(n+1)$ subsets, choose any ranking of the candidates. There exists an example of voters, each with a transitive ranking of the candidates, where when the ballots for each subset are tallied with the specified voting vector, the outcome is the selected one. More specifically, the vector $\mathbf W^n$, which designates these $2^n-(n+1)$ choices of voting vectors, is in an appropriate-dimensional vector space. There is a lower-dimensional algebraic set $\alpha^n$ so that if $\mathbf W^n\notin\alpha^n$, then this "anything can happen" conclusion holds. A positive assertion is that the number and kind of paradoxes is minimized if the Borda count is used to tally each subset of candidates. More precisely, if a listing of rankings (i.e., a voting paradox) can occur with the Borda count, it also occurs with any other $\mathbf W^n$. However, if $\mathbf W^n$ uses a non-Borda count choice to tally a subset of candidates, then $\mathbf W^n$ admits paradoxes that never occur with the Borda count. As an illustration, only the Borda count rankings are related with the pairwise rankings; e.g., for any other $\mathbf w^3$ there are voters' preferences where the election outcomes are the same as in the introductory example.

To illustrate the Borda count consistency advantage over other procedures, let $||\mathbf B^n||$ and $||\mathbf P^n||$ denote, respectively, the number of lists of distinct election rankings allowed by the Borda count and the plurality vote over the $2^n-(n+1)$ subsets. Even for $n=6$, it turns out that $10^{50}||\mathbf B^6||<||\mathbf P^6||$. These results indicate that the Borda count is the pragmatic answer to Laplace's question about the optimal choice of a voting procedure.

Statistics.

A closely related assertion holds for rankings determined by non-parametric methods of statistics. In particular, D. Haunsperger [a4] published a similar theorem, showing that for $n\geq3$ alternatives, almost-all non-parametric methods allow anything to happen. She then showed that the Krushkal–Wallis test plays the role of the Borda count by minimizing the number and kinds of paradoxes that can occur.

References

[a1] J.C. Borda, "Mémoire sur les élections au Scrutin" Histoire de l'Acad. R. des Sci. (1781)
[a2] I. McLean, F. Hewitt, "Condorcet" , Edward Elgar (1994)
[a3] I. McLean, A. Urken, "Classics of social choice" , Univ. Michigan Press (1995)
[a4] D. Haunsperger, "Dictionaries of paradoxes for statistical tests on samples" J. Amer. Statist. Assoc. (1992) pp. 149–155
[a5] J. Kelly, "Social choice bibliography" Social Choice Welfare , 8 (1991) pp. 97–169
[a6] D.G. Saari, "A chaotic examination of aggregation paradoxes" SIAM Review , 37 (1995) pp. 37–52
[a7] D.G. Saari, "Basic geometry of voting" , Springer (1995)
[a8] D.G. Saari, "The mathematical symmetry of choosing" Math. Japon. , 44 (1996) pp. 183–200
How to Cite This Entry:
Voting paradoxes. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Voting_paradoxes&oldid=42704
This article was adapted from an original article by D. Saari (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article