"Reverse-Tideman" Idea Explained

[Norman Petry]

Dear Markus,

Thank you for your reply.  You wrote:

>As far as I understand you correctly, you propose
>that the weakest pairwise defeats should be ignored successively
>until there are no cycles anymore.

The idea I had was a little different from this.  I'll use your example to
demonstrate what I had in mind.  First, I'll begin by listing the
"propositions" suggested by the pairwise comparison matrix, from weakest to
strongest:

A>D: 52
C>D: 53
C>A: 65
A>B: 67
B>C: 68
D>B: 77

Now, I'll try to establish a rank ordering of candidates, by beginning with
the weakest proposition, and incorporating new information as I work towards
the strongest.  Where necessary, I'll reverse my previous judgements, since
the stronger propositions must outweigh the weaker ones.  I'm not going to
think about cycles, except to avoid creating them (as in Tideman's method).
Unlike Tideman's method, I'm going to keep track of the "strength" of the
propositions, so I can know how to reverse previous opinions.  I'll show
this as: "A>(52)D" to indicate that the A beats D by 52.

Here's the analysis:

A>D: 52          A>(52)D
C>D: 53          A>(52)D; C>(53)D
C>A: 65          C>(65)A>(52)D
A>B: 67          C>(65)A>(52)D; C>(65)A>(67)B
B>C: 68          B>(68)C>(65)A>(52)D
D>B: 77          D>(77)B>(68)C>(65)A

The final ranking is D>B>C>A, so the single winner is D (unambiguously, I
think).  Note that in steps 3 and 5, I discarded useless information (C>D,
A>B), since new information allowed me to place C and B in the overall rank
order.  In step 6, D had to be placed at the beginning of the chain, since
the evidence for D>B strongly outweighs the evidence for A>D.

I also calculated the single-winner in this example using your beat-path
method, and produced the same result.

To me, this "Reverse-Tideman" method appears promising, at least in the 2
cases I've examined (yours and Mike's Tideman bad example).  Is this method
(as I've described it here) equivalent to yours?

Looking at it, it's almost certain that "Reverse-Tideman" is technically
inferior to the beat-path method, and will probably produce different
(worse) results in some cases.  Also, it might be possible to create
examples where it's impossible to decide how to incorporate new
propositions.  Yet, it might provide a reasonable approximation in most
cases.  Unfortunately, the procedure is messier than Tideman's, and because
we're working from the bottom-up, we couldn't claim that this _is_
Condorcet's method, so we lose some of the practical advantages that I
earlier suggested Tideman's method might have over yours.

Without a doubt, your beat-path method has all the elegance,
comprehensiveness, and consistency that this "Reverse-Tideman" method lacks.
Technically, this method offers nothing.  However, the approach itself is
fairly intuitive, so it might be a useful approximation of the beat-path
method for hand counts, or for people who have difficulty accepting the
validity of "beat-paths" in determining winners.

Any comments?


Norm Petry


-----Original Message-----
From: Markus Schulze <schulze at sol.physik.tu-berlin.de>
To: npetry at sk.sympatico.ca <npetry at sk.sympatico.ca>
Date: August 4, 1998 6:31 AM
Subject: Re: Tideman Problem


>Dear Norman,
>
>you wrote (3 Aug 1998):
>> Your bad example just gave me an idea though -- what would happen
>> if we turned Tideman on it's (his?) head to create a "Reverse-
>> Tideman"?  By this I mean: basically, Tideman's method is to begin
>> with the strongest propositions and ignore contradictions. Your
>> example shows that this might result in an important, strong
>> proposition being ignored. What would happen if we instead started
>> with the weakest propositions, and reversed our earlier judgements
>> as often as necessary as we worked our way up to the strongest?
>> That might break your bad example, and we might not need to resort
>> to the "Improved Tideman" which needs to backtrack over the
>> previously skipped propositions to be (potentially) as good as
>> Schulze.
>
>As far as I understand you correctly, you propose
>that the weakest pairwise defeats should be ignored successively
>until there are no cycles anymore.
>
>In literature, this has been proposed many times (especially by
>Peyton Young). Unfortunately, it doesn't work as expected.
>
>Example:
>
>  19 voters vote A > D > B > C.
>  17 voters vote B > C > A > D.
>  16 voters vote C > A > D > B.
>  16 voters vote D > A > B > C.
>  16 voters vote C > D > A > B.
>  10 voters vote D > B > C > A.
>  06 voters vote B > C > D > A.
>
>  A:B=67:33
>  A:C=35:65
>  A:D=52:48
>  B:C=68:32
>  B:D=23:77
>  C:D=53:47
>
>  There are still cycles (e.g. A > B > C > A,
>  D > B > C > D, A > D > B > C > A).
>  A:D=52:48 is the lowest defeat in a cycle,
>  thus A > D is ignored.
>
>  Now, we have:
>
>  A:B=67:33
>  A:C=35:65
>  B:C=68:32
>  B:D=23:77
>  C:D=53:47
>
>  There are still cycles (e.g. A > B > C > A,
>  D > B > C > D).
>  C:D=53:47 is the lowest defeat in a cycle,
>  thus C > D is ignored.
>
>  Now, we have:
>
>  A:B=67:33
>  A:C=35:65
>  B:C=68:32
>  B:D=23:77
>
>  There is still a cycle (A > B > C > A).
>  A:C=35:65 is the lowest defeat in a cycle,
>  thus A < C is ignored.
>
>  Now, we have:
>
>  A:B=67:33
>  B:C=68:32
>  B:D=23:77
>
>  Now, we have no cycles anymore.
>  But there are two candidates (A and D), who
>  each wins every not-ignored head-to-head pairing.
>  Who should win?
>
>By the way, as far as I know, the successive ignorance
>of weakest defeats has already been proposed by
>Condorcet. In "Essai sur la probabilite des decisions;
>rendues a la pluralite des voix" (1785), Condorcet wrote:
>
> Create an opinion of those n*(n-1)/2 propositions, which
> win most of the votes. If this opinion is one of the n*(n-1)*...*2
> possible, then consider as elected that subject, with which this
> opinion agrees with its preference. If this opinion is one of the
> (2^(n*(n-1)/2))-n*(n-1)*...*2 impossible opinions, then eliminate
> of this impossible opinion successively those propositions, that
> have a smaller plurality, & accept the resulting opinion of the
> remaining propositions.
>
>But then, Condorcet found that this formulation leads to the
>above mentioned problem. That's why in later writings
>Condorcet proposed a method identical to Tideman's method.
>
>Markus Schulze
>
>