View source for Condorcet paradox

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

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

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

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.

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:

<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" />;

<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" />;

<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" />;

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

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.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  K.J. Arrow,   "Social choice and individual values" , ''Cowles Commission Monograph'' , '''12''' , Wiley  (1951)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  J.-Ch. Borda,   "Sur la forme des élections au scrutin"  ''Mém. Acad. Royal Sci. Paris''  (1781/4)  pp. 657–665</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  N.C. de Condorcet,   "Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix" , Paris  (1785)</TD></TR></table>