The French Connection: Borda, Condorcet and the Mathematics of Voting Theory – Condorcet’s Use of Pairwise Comparisons and the Condorcet Paradox

Author(s):
Janet Heine Barnett (Colorado State University – Pueblo)

Having given a particular example to exhibit the inherent flaw that can result in election decisions based on the Plurality Method of Voting, Condorcet next noted that there is one circumstance in which the Plurality Method of Voting could suffice to select the correct choice among candidates, namely when there is a candidate with a majority of the first place votes:

One sees therefore already that one should reject the form of election generally adopted: if one wishes to conserve it, it will be possible [to do so] only in the case where one is not required to elect on the spot, & where one could require that only someone who would have gathered more than half of the votes would be looked upon as elected. In this same case, this form [of voting] would again have the disadvantage of agreeing to look upon as non-elected the one who would have in reality has a very great plurality.[40]

Today, a candidate with a majority of the first-place votes is known as a Majority Candidate, and it is easy to see that a Majority Candidate is also necessarily a Condorcet Candidate. Similarly, it is straightforward to show that a Majority Candidate (if one exists) will necessarily win an election under both the Plurality and Borda Count Methods of Voting. This latter voting method was not, however, the one endorsed by Condorcet as an alternative to the former. Instead, he declared:

So one should in general substitute for this [plurality] form [of voting] that in which each Voter, [by] expressing the order according to which he places the Candidates, would pronounce at the same time on the preference that he would accord respectively to each.[41]

In other words, election decisions should be based on the outcomes of the head-to-head comparisons of every pair of candidates, which in turn can readily be determined from voters’ ranked orderings of the candidates. Importantly, Condorcet’s use of head-to-head comparisons differed from the way such comparisons featured in Borda’s “special elections” method. In that method, recall that Borda summed the numbers of votes cast for each candidate in all of the various pairs in a way that rendered that method equivalent to the basic Borda Count Method of Voting. Given this equivalency together with the dramatic increase that occurs in the number of pairs as the number of candidates increases, Borda ultimately rejected using head-to-head comparisons as an avoidable inconvenience. In contrast, Condorcet’s plan tallies the actual number of votes cast for each candidate in the pair only to determine which of the two candidates in the pair wins that particular comparison: did the voters find that A is better than B, or that B is better than A? Once this is decided, the vote totals themselves are discarded.

Unlike Borda, Condorcet also seemed undaunted by the number of head-to-head comparisons that may need to be tallied.[42] Nor was he daunted by a feature of his recommended voting method that is today known as Condorcet Paradox: the final results of the head-to-head comparisons can be non-transitive. Here is Condorcet’s first example of this situation.

Let us suppose indeed that in the example already chosen, where one has 23 votes for A, 19 for B, 18 for C, the 23 votes for A are for the proposition B is better than C; this proposition [B is better than C] will have a plurality of 42 votes against 18.

Let us next suppose that of the 19 votes in favor of B, there are 17 for B is better than C, & 2 for the contradictory proposition; this proposition C is better than A will have a plurality of 35 votes against 25. We suppose finally that of the 18 votes for C, 10 are for the proposition A is better than B, & 8 for the contradictory proposition, we will have a plurality of 33 votes against 27 in favor of the proposition A is better than B. The system that obtains the plurality will therefore be composed of three propositions,

A is better than B,
C is better than A,
B is better than C.

This system is . . . one of the two [possible systems] that implies contradiction.[43]

For many students (and others), the fact that individual transitive preferences (an assumption implicit in the use of rank orderings) can lead to a intransitive group decision (with A > B, B > C, but C > A) is indeed a paradoxical aspect of the mathematics of social choice. How can the group outcome be so irrational when each individual within the group has voted rationally? As noted earlier, however, Condorcet himself was not fazed by this fact—indeed, he did not even view it as an impediment to the viability of the Pairwise Comparison Method of Voting. Instead, he devoted several pages of his Essai to a discussion of how to proceed with voting in order to produce the winner with the highest probability of being the correct choice in the event that election results do result in one of these “contradictory systems” [Condorcet 1785, pp. clxx–clxxvii; pp. 118–136]. While his full description of this somewhat complicated procedure in Part 2 of his Essai was not completely clear,[44] Condorcet’s concluding remarks about contradictory systems in his Preface provide a glimpse of the basic idea behind his procedure, both in its technical aspects and its societal implications:

Finally, let us observe that these contradictory systems cannot arise without indicating uncertainty in [the] opinions [of the voters], and they will not take place, neither if the votes being taken as usual, one of the Candidates has more than half of the votes, nor if one requires in order to admit the propositions which form the ballot, a plurality of one third.

There results from all the reflections that we have just made, this general rule, that whenever we are forced to elect, it is necessary to take successively all the propositions which have the plurality, beginning with those which have the largest, and pronounce according to the result formed by these first propositions, as soon as they form one, without having regard to the propositions less likely to follow them.

If by this means we disagree with the result least susceptible to error, or a result whose probability is greater than 1/2, and formed from two propositions which are more probable than their contradictories, we will at least have the one which does not oblige [us] to adopt the least probable proposals, and from which it results a lesser injustice between the Candidates, considered two by two.[45]

Today’s standard undergraduate treatment of voting theory features a simplified version of Condorcet’s voting procedure that drops his provision for handling cases in which Condorcet Paradox occurs. Known as the Pairwise Comparison Method of Voting, this method simply uses the number of comparisons won by each candidate to determine the overall election winner.

[40] Condorcet 1785, p. lviii.

[41] Condorcet 1785, p. lviii.

[42] Condorcet was, however, fully aware of the combinatorial challenges involved in using pairwise comparisons as part of one’s voting method, and remarked immediately following the preceding excerpt that:

One would draw from this order [in which candidates are ranked by each voter] the three propositions which should form each opinion, if there are three Candidates; the six propositions that should form each opinion, if there are four Candidates; the ten, if there are five, &c. in comparing the votes in favor of each of these propositions or their contraries [Condorcet 1785, p. lx].

Indeed, because of his emphasis on systems of propositions, the combinatorial challenges involved in Condorcet’s analysis went even further, as he himself noted:

One will have by this means the system of propositions, which will be formed . . . among the 8 systems possible for three candidates, the 64 systems possible for four Candidates, the 1024 systems possible for five Candidates & if one considers only those that do not imply a contradiction, there will be only 8 possible for three Candidates, 24 for four, 120 for five, and so on [Condorcet 1785, p. lx].

In the full analysis of the problems of voting that he provided in Part 2 of the Essai, he also computed these numbers for the general case if n candidates; see footnote 44 below for a statement of his results.

[43] Condorcet 1785, p. lxj. The actual sentence is: “This system is the third, & one of the two that implies contradiction.” The “third” here refers back to a slightly earlier section of his Preface [pp.lvj–lviij] in which Condorcet analyzed the eight different three-proposition systems that can result from an election involving three candidates, finding that two of the eight combinations favored A, two favored B, two favored C, and the final two involved non-transitive results. In Part 2 of his Essai¸ he also provided a full analysis of possible aggregate opinions in the case of n candidates, including a computation of how many of these opinions were contradictory. See also footnote 44.

[44] Condorcet’s statement of his proposed voting procedure appeared in Part 2 of his Essai [Condorcet 1785, pp. 125–126]:

1.° All possible opinions that do not imply a contradiction reduce to an indication of the order of merit that one judges to exist among the candidates. . . . Therefore for nCandidates, one will have $n(n-1) \ldots 2$ possible opinions. . . .

2.° Each Voter having thus given his opinion by indicating the candidates’ order of worth, if one compares them two by two, one will have in each opinion $\frac{n(n-1)}{2}$ propositions to consider separately. Taking the number of times that each is contained in the opinion of one of the q voters, one will have the number of voices who are for each proposition.

3.° One forms an opinion from those $\frac{n(n-1)}{2}$ propositions that agree with the most voices. If this opinion is among the $n(n-1) \ldots 2$ possible opinions, one regards as elected the Subject to whom this opinion accords the preference. If this opinion is among the $2^{\frac{n(n-1)}{2}}-n(n-1)\ldots2$ impossible opinions, then one successively deletes from that impossible opinion the propositions that have the least plurality, and one adopts the opinion from those that remain.

The instruction in 3.° that directs us to “successively deletes from that impossible opinion the propositions that have the least plurality” is the step in Condorcet’s algorithm that scholars have (rightfully) found to be vague. Unfortunately, Condorcet neglected to provide examples in his Essai or elsewhere that would clarify exactly how he meant this step to work. In his study of this particular feature of Condorcet’s voting theory, the economist and game theorist H. P. Young has cited the critical opinions of several Condorcet scholars, including that of the mathematician Isaac Todhunter (1820–1884): “The obscurity and self-contradiction are without any parallel, so far as our experience of mathematical works extends . . . no amount of examples can convey an adequate impression of the evils” (attributed in [Young 1988, p. 1234] to [Todhunter 1949, 352]).Young himself went on to propose a plausible hypothesis about Condorcet’s intended meaning, and described this interpreted version of the algorithm as “a novel and statistically correct rule for finding the most likely ranking of the alternatives” and Condorcet’s development of it as “one of the earliest applications of what today would be called ‘statistical hypothesis testing’” [Young 1988,, pp. 1231, 1235].

[45] Condorcet 1785, pp. lxix–lxx. True to the non-mathematical goals that Condorcet held for his Essai, he went on to write [Condorcet 1785, p. lxx]:

Moreover, the Voters must be enlightened, and all the more enlightened, as the questions which they decide are more complicated; otherwise we will find a form of decision which will preserve the fear of a false decision, but which at the same time making any decision almost impossible, will only be a means of perpetuating abuses and bad laws. Thus the form of the assemblies which decide the strength of men, is much less important for their happiness than the enlightenment of those who compose them: & the progress of reason will contribute more to the good of the Peoples than the forms of political constitutions.

Janet Heine Barnett (Colorado State University – Pueblo), "The French Connection: Borda, Condorcet and the Mathematics of Voting Theory – Condorcet’s Use of Pairwise Comparisons and the Condorcet Paradox," Convergence (September 2020)