Namespaces
Variants
Actions

Difference between revisions of "Voting paradoxes"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
Line 1: Line 1:
Voting paradoxes describe counter-intuitive election outcomes. The mathematical study started in 1770 when J.C. Borda [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v1100801.png" /> voters with the (complete, transitive) preferences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v1100802.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v1100803.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v1100804.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v1100805.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v1100806.png" />. Here, the plurality ranking of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v1100807.png" /> conflicts with the pairwise rankings of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v1100808.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v1100809.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008010.png" /> with the respective tallies of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008011.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008012.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008013.png" />. Borda suggested an alternative method, the Borda count, where with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008014.png" /> alternatives a voter's <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008015.png" />th ranked candidate receives <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008016.png" /> points, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008017.png" /> The Borda count outcome for the example is the more reasonable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008018.png" /> with the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008019.png" /> tally.
+
{{TEX|done}}
 +
Voting paradoxes describe counter-intuitive election outcomes. The mathematical study started in 1770 when J.C. Borda [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008020.png" /> candidate election can be tallied with a voting vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008021.png" /> where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008022.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008023.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008024.png" />. (The plurality vote corresponds to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008025.png" /> while the Borda count is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008026.png" />) With the infinite number of ways to tally ballots, P.S. Laplace and other mathematicians started a two-century controversy by questioning which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008027.png" /> 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|Arrow impossibility theorem]]). See [[#References|[a2]]], [[#References|[a3]]] for a flavour of the rich history of this area and [[#References|[a7]]] for a mathematical introduction.
+
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|Arrow impossibility theorem]]). See [[#References|[a2]]], [[#References|[a3]]] for a flavour of the rich history of this area and [[#References|[a7]]] for a mathematical introduction.
  
 
===All paradoxes.===
 
===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 [[#References|[a5]]]), they are limited. However, by using symmetry and arguments from chaotic dynamics, all possible voting paradoxes finally have been characterized [[#References|[a6]]], [[#References|[a8]]]. To describe them, notice that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008028.png" /> alternatives define <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008029.png" /> 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 the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008030.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008031.png" />, which designates these <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008032.png" /> choices of voting vectors, is in an appropriate-dimensional vector space. There is a lower-dimensional algebraic set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008033.png" /> so that if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008034.png" />, 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008035.png" />. However, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008036.png" /> uses a non-Borda count choice to tally a subset of candidates, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008037.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008038.png" /> there are voters' preferences where the election outcomes are the same as in the introductory example.
+
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 [[#References|[a5]]]), they are limited. However, by using symmetry and arguments from chaotic dynamics, all possible voting paradoxes finally have been characterized [[#References|[a6]]], [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008039.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008040.png" /> denote, respectively, the number of lists of distinct election rankings allowed by the Borda count and the plurality vote over the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008041.png" /> subsets. Even for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008042.png" />, it turns out that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008043.png" />. These results indicate that the Borda count is the pragmatic answer to Laplace's question about the optimal choice of a voting procedure.
+
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.===
 
===Statistics.===
A closely related assertion holds for rankings determined by non-parametric methods of statistics. In particular, D. Haunsperger [[#References|[a4]]] published a similar theorem, showing that for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008044.png" /> 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.
+
A closely related assertion holds for rankings determined by non-parametric methods of statistics. In particular, D. Haunsperger [[#References|[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====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J.C. Borda,  "Mémoire sur les élections au Scrutin"  ''Histoire de l'Acad. R. des Sci.''  (1781)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  I. McLean,  F. Hewitt,  "Condorcet" , Edward Elgar  (1994)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  I. McLean,  A. Urken,  "Classics of social choice" , Univ. Michigan Press  (1995)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  D. Haunsperger,  "Dictionaries of paradoxes for statistical tests on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008045.png" /> samples"  ''J. Amer. Statist. Assoc.''  (1992)  pp. 149–155</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  J. Kelly,  "Social choice bibliography"  ''Social Choice Welfare'' , '''8'''  (1991)  pp. 97–169</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  D.G. Saari,  "A chaotic examination of aggregation paradoxes"  ''SIAM Review'' , '''37'''  (1995)  pp. 37–52</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  D.G. Saari,  "Basic geometry of voting" , Springer  (1995)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  D.G. Saari,  "The mathematical symmetry of choosing"  ''Math. Japon.'' , '''44'''  (1996)  pp. 183–200</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J.C. Borda,  "Mémoire sur les élections au Scrutin"  ''Histoire de l'Acad. R. des Sci.''  (1781)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  I. McLean,  F. Hewitt,  "Condorcet" , Edward Elgar  (1994)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  I. McLean,  A. Urken,  "Classics of social choice" , Univ. Michigan Press  (1995)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  D. Haunsperger,  "Dictionaries of paradoxes for statistical tests on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v110/v110080/v11008045.png" /> samples"  ''J. Amer. Statist. Assoc.''  (1992)  pp. 149–155</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  J. Kelly,  "Social choice bibliography"  ''Social Choice Welfare'' , '''8'''  (1991)  pp. 97–169</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  D.G. Saari,  "A chaotic examination of aggregation paradoxes"  ''SIAM Review'' , '''37'''  (1995)  pp. 37–52</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  D.G. Saari,  "Basic geometry of voting" , Springer  (1995)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  D.G. Saari,  "The mathematical symmetry of choosing"  ''Math. Japon.'' , '''44'''  (1996)  pp. 183–200</TD></TR></table>

Revision as of 13:41, 17 April 2014

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=31811
This article was adapted from an original article by D. Saari (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article