[EM] Condorcet cyclic drop rule

[Markus Schulze]

Dear Mike,

you wrote (6 Apr 2001):
> But if you're saying that Condorcet's drop-weakest proposal says to
> drop the weakest defeat till there are no cycles, that's a radical
> new interpretation.

Actually, this "radical new" interpretation of Condorcet's bottom-up
proposal has been mentioned _very frequently_ in this mailing list
since 1996. For example, on 15 Jan 1997 Thomas Jones wrote:

> Prof. Young gives the following example of his (Young's) interpretation
> of Condorcet's comments (that I quoted in the original Left or right
> loser posting)--
>          Table 1- 13 voters
>            a         b          c
>  a        --        8            6
>  b        5        --           11
>  c        7          2          --
>
> Prof. Young's comments- Let us apply this rule [Condorcet's comments that
> I quoted in the original Left or right loser posting] to the situation
> in Table 1.  First we are to choose the three propositions having a
> majority, namely b > c with eleven votes, a > b with eight votes, and
> c > a with seven votes.  Since these three propositions form a cycle,
> however, we delete the proposition with the smallest plurality, namely
> c > a.  This leaves the combination b > c and a > b (and implicitly
> a > c), which implies the ranking a > b > c.
> ---
> My comment- It appears that Prof. Young says that Condorcet's
> tiebreaker is different from anything written about on the EM list.
> ----
> Prof. Young goes on with a 4 candidate cycle example--
> 25 Voters
>          a       b         c         d
> a     --       12      15       17
> b    13        --      16       11
> c    10         9       --       18
> d     8         14       7        --
>
> In step 2 of Condorcet's algorithm one would select the six propositions
> having greatest majorities.  In descending size of majority, these
> are c > d [18 > 7] , a > d [17 > 8], b > c [16 > 9], a > c [15 > 10],
> d > b [14 > 11], b > a [13 > 12].  According to a literal reading of
> [Condorcet's] step 3, one would first delete the proposition b > a, as
> it has the smallest majority in its favor.  But this does not result
> in an "opinion" because one cycle still remains: b > c, c > d, d > b.
> Therefore one would delete the proposition d > b, as it has the next-
> smallest majority in its favor.  All cycles are now eliminated.  But
> there is a difficulty: in the resulting partial order both a and b are
> undominated.  Either one of them could be interpreted as the top-ranked
> candidate, so the outcome is indeterminate.
>
> [snip]
>
> I suggest that all Condorcet fans take a look at-- Condorcet's Theory
> of Voting by H. P. Young, 82 American Political Science Review 1231
> (Dec. 1988).

******

You wrote (6 Apr 2001):
> I don't remember the exact words, but in an article in _Journal of
> Economic Perspective_, for Winter '95, it seems to me that they said
> that Ranked Pairs was Tideman's interpretation of Condorcet's
> top-down proposal.

These are the exact words (Jonathan Levin, Barry Nalebuff, "An
Introduction to Vote-Counting Schemes," _Journal of Economic
Perspectives_, vol. 9, no. 1, p. 3-26):

> Condorcet's (1785) seminal paper expresses the idea that a candidate
> who would defeat each of the others head-to-head should win the
> election. If no such candidate exists, then large majorities should
> take precedence over small majorities in breaking cycles. In his
> own words, the general rule was "to take successively all the
> propositions that have a majority, beginning with those possessing
> the largest. As soon as these first decisions produce a result, it
> should be taken as a decision, without regard for the less probable
> decisions that follow." How is this idea implemented? Consider all
> the possible lists that order the candidates from top to bottom.
> Find the largest margin of victory in any pairwise match - and then
> eliminate all potential rankings that contradict this preference.
> For example, if the largest victory is for candidate A over
> candidate B, eliminate all potential rankings which place B above A.
> Next, consider the second largest margin of victory, and eliminate
> all potential rankings that disagree. Continue this process until
> one ranking remains.
> With only three candidates, this method is well defined and is
> equivalent to ignoring the election with the smallest margin of
> victory. The problem is that in elections with four or more
> candidates, considering the largest unconsidered margin of victory
> may, at some point, force us to eliminate all remaining potential
> rankings (by locking in a cycle). Condorcet does not discuss this
> possibility, an omission which has led to criticism and some
> confusion.
> T.N. Tideman suggests one solution to this dilemma of cycles:
> simply skip over a head-to-head result that will lock in a cycle.
> Tideman further notes that if ties exist, there may be more than
> one potential ranking left even after we have considered all
> victories. In this case, we declare a tie among the candidates
> who have first-place ranks in the remaining potential rankings.
> Tideman calls this scheme "ranked pairs."
> In the pairwise-comparisons matrix below, we first lock in A > B,
> then B > C. This implies A > C. The next largest victory is C > A,
> but this locks in a cycle, so we ignore that head-to-head result.
> We then lock in A > D, B > D, C > D, which leaves us which a final
> ranking A > B > C > D.
> 
> A:B=61:39
> A:C=41:59
> A:D=51:49
> B:C=60:40
> B:D=51:49
> C:D=51:49

Markus Schulze