Namespaces
Variants
Actions

Difference between revisions of "Condorcet paradox"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
 
Line 1: Line 1:
 +
{{TEX|done}}
 
M.J.A.N. de Caritat, Marquis de Condorcet, studied the problem of determining the most likely correct choice, under voting by a group of decision-makers. In this, his work is closely related to that of J.-Ch. Borda.
 
M.J.A.N. de Caritat, Marquis de Condorcet, studied the problem of determining the most likely correct choice, under voting by a group of decision-makers. In this, his work is closely related to that of J.-Ch. Borda.
  
 
In the case of dichotomous choice (two alternatives), Condorcet obtained valuable results (see also [[Condorcet jury theorem|Condorcet jury theorem]]), which have been extended in recent times (as of 2000). For the case of three or more alternatives (candidates), however, serious difficulties occur (see also [[Social choice|Social choice]]).
 
In the case of dichotomous choice (two alternatives), Condorcet obtained valuable results (see also [[Condorcet jury theorem|Condorcet jury theorem]]), which have been extended in recent times (as of 2000). For the case of three or more alternatives (candidates), however, serious difficulties occur (see also [[Social choice|Social choice]]).
  
Briefly, one can say that candidate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c1301801.png" /> defeats candidate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c1301802.png" /> if a majority of the voters prefer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c1301803.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c1301804.png" />. With only two candidates, there is little more to say: barring ties (which are assumed to have extremely low [[Probability|probability]]), one of the two candidates will defeat the other. Where there are three or more candidates, however, cyclic situations might occur, wherein <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c1301805.png" /> defeats <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c1301806.png" />, who defeats <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c1301807.png" />, who in turn defeats <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c1301808.png" />. It is of course possible that one candidate defeats all the others; if so, this candidate is said to be the Condorcet winner. However, even if there is a Condorcet winner, standard methods of voting need not produce this winner. This is Condorcet's paradox (cf. also [[Voting paradoxes|Voting paradoxes]]).
+
Briefly, one can say that candidate $A$ defeats candidate $B$ if a majority of the voters prefer $A$ to $B$. With only two candidates, there is little more to say: barring ties (which are assumed to have extremely low [[Probability|probability]]), one of the two candidates will defeat the other. Where there are three or more candidates, however, cyclic situations might occur, wherein $A$ defeats $B$, who defeats $C$, who in turn defeats $A$. It is of course possible that one candidate defeats all the others; if so, this candidate is said to be the Condorcet winner. However, even if there is a Condorcet winner, standard methods of voting need not produce this winner. This is Condorcet's paradox (cf. also [[Voting paradoxes|Voting paradoxes]]).
  
 
The easiest method of voting is, of course, straight plurality voting. Another might be two-round voting, with a second round only if there is no majority on the first round.
 
The easiest method of voting is, of course, straight plurality voting. Another might be two-round voting, with a second round only if there is no majority on the first round.
Line 9: Line 10:
 
A third, more sophisticated method, is the following: voters state their first choice. If no candidate has a majority of the votes, then that candidate with the least votes is eliminated, and voters are asked to choose among the remaining candidates. These steps are repeated until one candidate is left with a majority. This method is frequently used in elections.
 
A third, more sophisticated method, is the following: voters state their first choice. If no candidate has a majority of the votes, then that candidate with the least votes is eliminated, and voters are asked to choose among the remaining candidates. These steps are repeated until one candidate is left with a majority. This method is frequently used in elections.
  
With any of these three methods, suppose there are three candidates, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c1301809.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018010.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018011.png" />, and nine voters. Suppose two voters rank the candidates <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018012.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018013.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018014.png" />; three rank them <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018015.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018016.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018017.png" />; and four rank them <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018018.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018019.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018020.png" />. In this case, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018021.png" /> would be the winner under straight plurality voting.
+
With any of these three methods, suppose there are three candidates, $A$, $B$ and $C$, and nine voters. Suppose two voters rank the candidates $A$, $B$, $C$; three rank them $B$, $A$, $C$; and four rank them $C$, $A$, $B$. In this case, $C$ would be the winner under straight plurality voting.
  
For either of the other two methods, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018022.png" /> (with only two votes) would be eliminated in the first round; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018023.png" /> would then defeat <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018024.png" /> in the second round. Note, however, that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018025.png" /> defeats <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018026.png" /> by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018027.png" /> votes to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018028.png" />, and also defeats <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018029.png" /> by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018030.png" /> votes to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018031.png" />. Thus <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018032.png" />, the first eliminated, is the Condorcet winner.
+
For either of the other two methods, $A$ (with only two votes) would be eliminated in the first round; $B$ would then defeat $C$ in the second round. Note, however, that $A$ defeats $B$ by $6$ votes to $3$, and also defeats $C$ by $5$ votes to $4$. Thus $A$, the first eliminated, is the Condorcet winner.
  
An alternative idea is to count the number of votes that a candidate would have in one-on-one contests against each of the other candidates. This is known as the Borda count (cf. also [[Voting paradoxes|Voting paradoxes]]), and Borda suggested that the candidate with highest count should be the winner. Again, the Condorcet winner (if one exists) need not be the Borda winner. As an example, suppose there are three candidates, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018033.png" /> voters, with rankings as follows:
+
An alternative idea is to count the number of votes that a candidate would have in one-on-one contests against each of the other candidates. This is known as the Borda count (cf. also [[Voting paradoxes|Voting paradoxes]]), and Borda suggested that the candidate with highest count should be the winner. Again, the Condorcet winner (if one exists) need not be the Borda winner. As an example, suppose there are three candidates, and $11$ voters, with rankings as follows:
  
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018034.png" /> voters rank <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018035.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018036.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018037.png" />;
+
$5$ voters rank $A$, $C$, $B$;
  
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018038.png" /> voter ranks <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018039.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018040.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018041.png" />;
+
$1$ voter ranks $B$, $A$, $C$;
  
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018042.png" /> voters rank <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018043.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018044.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018045.png" />;
+
$2$ voters rank $C$, $A$, $B$;
  
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018046.png" /> voters rank <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018047.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018048.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018049.png" />. In this case, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018050.png" /> defeats both <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018051.png" /> (by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018052.png" /> votes to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018053.png" />) and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018054.png" /> (by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018055.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018056.png" />). Thus <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018057.png" /> is the Condorcet winner, and has a Borda count of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018058.png" />. However, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018059.png" /> defeats <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018060.png" /> by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018061.png" /> votes to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018062.png" />, and so <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018063.png" />'s Borda count is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018064.png" />. Thus, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130180/c13018065.png" /> is the Borda winner.
+
$3$ voters rank $C$, $B$, $A$. In this case, $A$ defeats both $B$ (by $7$ votes to $4$) and $C$ (by $6$ to $5$). Thus $A$ is the Condorcet winner, and has a Borda count of $13$. However, $C$ defeats $B$ by $10$ votes to $1$, and so $C$'s Borda count is $15$. Thus, $C$ is the Borda winner.
  
 
In general, the problem of group decision when there are three or more alternatives leads to contradictions. These are best summarized in the [[Arrow impossibility theorem|Arrow impossibility theorem]], which states (briefly) that there is no method (for such decisions) satisfying certain eminently reasonable axioms.
 
In general, the problem of group decision when there are three or more alternatives leads to contradictions. These are best summarized in the [[Arrow impossibility theorem|Arrow impossibility theorem]], which states (briefly) that there is no method (for such decisions) satisfying certain eminently reasonable axioms.

Latest revision as of 13:15, 9 August 2014

M.J.A.N. de Caritat, Marquis de Condorcet, studied the problem of determining the most likely correct choice, under voting by a group of decision-makers. In this, his work is closely related to that of J.-Ch. Borda.

In the case of dichotomous choice (two alternatives), Condorcet obtained valuable results (see also Condorcet jury theorem), which have been extended in recent times (as of 2000). For the case of three or more alternatives (candidates), however, serious difficulties occur (see also Social choice).

Briefly, one can say that candidate $A$ defeats candidate $B$ if a majority of the voters prefer $A$ to $B$. With only two candidates, there is little more to say: barring ties (which are assumed to have extremely low probability), one of the two candidates will defeat the other. Where there are three or more candidates, however, cyclic situations might occur, wherein $A$ defeats $B$, who defeats $C$, who in turn defeats $A$. It is of course possible that one candidate defeats all the others; if so, this candidate is said to be the Condorcet winner. However, even if there is a Condorcet winner, standard methods of voting need not produce this winner. This is Condorcet's paradox (cf. also Voting paradoxes).

The easiest method of voting is, of course, straight plurality voting. Another might be two-round voting, with a second round only if there is no majority on the first round.

A third, more sophisticated method, is the following: voters state their first choice. If no candidate has a majority of the votes, then that candidate with the least votes is eliminated, and voters are asked to choose among the remaining candidates. These steps are repeated until one candidate is left with a majority. This method is frequently used in elections.

With any of these three methods, suppose there are three candidates, $A$, $B$ and $C$, and nine voters. Suppose two voters rank the candidates $A$, $B$, $C$; three rank them $B$, $A$, $C$; and four rank them $C$, $A$, $B$. In this case, $C$ would be the winner under straight plurality voting.

For either of the other two methods, $A$ (with only two votes) would be eliminated in the first round; $B$ would then defeat $C$ in the second round. Note, however, that $A$ defeats $B$ by $6$ votes to $3$, and also defeats $C$ by $5$ votes to $4$. Thus $A$, the first eliminated, is the Condorcet winner.

An alternative idea is to count the number of votes that a candidate would have in one-on-one contests against each of the other candidates. This is known as the Borda count (cf. also Voting paradoxes), and Borda suggested that the candidate with highest count should be the winner. Again, the Condorcet winner (if one exists) need not be the Borda winner. As an example, suppose there are three candidates, and $11$ voters, with rankings as follows:

$5$ voters rank $A$, $C$, $B$;

$1$ voter ranks $B$, $A$, $C$;

$2$ voters rank $C$, $A$, $B$;

$3$ voters rank $C$, $B$, $A$. In this case, $A$ defeats both $B$ (by $7$ votes to $4$) and $C$ (by $6$ to $5$). Thus $A$ is the Condorcet winner, and has a Borda count of $13$. However, $C$ defeats $B$ by $10$ votes to $1$, and so $C$'s Borda count is $15$. Thus, $C$ is the Borda winner.

In general, the problem of group decision when there are three or more alternatives leads to contradictions. These are best summarized in the Arrow impossibility theorem, which states (briefly) that there is no method (for such decisions) satisfying certain eminently reasonable axioms.

References

[a1] K.J. Arrow, "Social choice and individual values" , Cowles Commission Monograph , 12 , Wiley (1951)
[a2] J.-Ch. Borda, "Sur la forme des élections au scrutin" Mém. Acad. Royal Sci. Paris (1781/4) pp. 657–665
[a3] N.C. de Condorcet, "Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix" , Paris (1785)
How to Cite This Entry:
Condorcet paradox. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Condorcet_paradox&oldid=32777
This article was adapted from an original article by Guillermo Owen (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article