Comparison of latest Condorcet Variants

[Norman Petry]

Mike,

In this post, I'm going to try to sort out (in my own mind, at least) some
of the mess we've made in the last few days with a plethora of new Condorcet
methods and variants.  To begin:

You wrote, in reference to Schulze's method:

>I don't have an example where it's indecisive, and I don't
>know if it has that problem at all, or more than the other
>versions, like Sequential Dropping (I wouldn't object to a
>better name for Sequential Dropping).

I don't think "Sequential Dropping" (or "Condorcet1") is decisive; at least,
not if I've understood it correctly.  In fact, I think it's exactly the same
as my "Reverse-Tideman", and your new interpretation of Tideman (what I
called "Improved Tideman"), that tries to preserve pair orderings with
greater pairwise majorities.  I'll apply my understanding of the each of
these methods to the indecisiveness problem you devised:

>{A,B,C} is a subcycle, but not a clone set.
>
>A>B 2
>B>C 3
>C>A 1
>
>{A,B,C}>D 7
>E>A 8
>E>B 5
>E>C 4
>
>D>E 6


Pairwise Dropping:

"Starting with the weakest defeat, sequentially drop the defeats that
conflict (by forming a cycle) with larger defeats, till there's an
undefeated alternative."

Drop C>A 1 to break cycle {A,B,C}
Drop A>B 2 to break cycle {A,B,D,E}
Drop B>C 3 to break cycle {B,C,D,E}
Drop E>C 4 to break cycle {C,E,D}
Drop E>B 5 to break cycle {B,D,E}
Drop D>E 6 to break cycle {A,D,E}

No more cycles.  What's left?

E>A>D
B>D
C>D

Result: winners are {B,C,E}


Reverse-Tideman:

Norman: "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?"

Mike: "Throw out defeats that conflict (by forming a cycle) with stronger
defeats."

C>A: 1     C>(1)A
A>B: 2     C>(1)A>(2)B
B>C: 3     A>(2)B>(3)C
E>C: 4     A>(2)B>(3)C; E>(4)C
E>B: 5     A>(2)B>(3)C; E>(5)B>(3)C
D>E: 6     A>(2)B>(3)C; E>(5)B>(3)C; D>(6)E
A>D: 7     A>(7)D>(6)E>(5)B>(3)C
B>D: 7     B>(7)D>(6)E; A>(7)D>(6)E; B>(3)C
C>D: 7     B>(7)D>(6)E; A>(7)D>(6)E; C>(7)D
E>A: 8     B>(7)D; E>(8)A>(7)D; C>(7)D

Result: winners are {B,C,E}



Improved Tideman:

David: "...Tideman says they are the same.  His version says 'When a
pair-ordering is encountered that cannot be preserved while also preserving
all pair-orderings with greater majorities, ...'"

Mike: "The crucial phrase in the quotation was "...while preserving all pair
orderings with greater majorities".  As opposed to all greater defeats that
haven't been skipped.  So previously- skipped defeats _aren't_ subsequently
ignored."

E>A: 8     E>A
A>D: 7     E>A>D
B>D: 7     E>A>D; B>D
C>D: 7     E>A>D; B>D; C>D
D>E: 6     E>A>D; B>D; C>D (skip: E>A>D: 7)
E>B: 5     E>A>D; B>D; C>D (skip: B>D>E: 6)
E>C: 4     E>A>D; B>D; C>D (skip: C>D>E: 6)
B>C: 3     E>A>D; B>D; C>D (skip: C>D>E>B: 5)
A>B: 2     E>A>D; B>D; C>D (skip: B>D>E>A: 6)
C>A: 1     E>A>D; B>D; C>D (skip: A>D>E>C: 4)

Note that where it says "skip", this just means that the new proposition
could not be incorporated into the final answer as doing so would not
preserve previous pair orderings, _not_ that these results are later
ignored.

Result: winners are {B,C,E}


Summary:

All three of these methods produce the same indecisive result: {B,C,E}.
The reason for this seems to be that they're doing essentially the same
thing, but in different order.  Viewed graphically:

1) Pairwise dropping: start with a graph containing all the beat paths.
Erase the weakest until there are no more cycles.
2) Reverse-Tideman: start with an empty graph, containing only the
candidates.  Connect the candidates via beat-paths beginning with the
weakest defeats.  Erase weaker defeats if adding a stronger defeat will
create a cycle.
3) Improved Tideman: start with an empty graph, containing only the
candidates.  Connect the candidates via beat-paths beginning with the
strongest defeats.  If adding a beat-path would create a cycle, use an
"invisible" line (dashes, or whatever) instead of a solid line.  The winners
are the undominated candidates connected to others via solid line beat
paths.

Which of these three approaches is better?

"Pairwise Dropping" is easiest to describe.  "Reverse-Tideman" is the
easiest to carry out by hand, using pencil and paper.  "Improved Tideman" is
confusing and difficult to apply accurately -- it has no advantages.  All
the methods are equivalent in terms of results.  They (probably) achieve
clone independence to some degree (since they're based on Tideman's regular
method), at the cost of indecisive results.  Depending on the tiebreaker
used, they might satisfy GMC. All of these methods have been invented before
(by Condorcet, Young, etc.) as Markus pointed out.

What about (regular) Tideman?


Tideman:

Mike: ""skip" a defeat, and leave it skipped and ignored for the rest of the
count"

lock E>A: 8     E>A
lock A>D: 7     E>A>D
lock B>D: 7     E>A>D; B>D
lock C>D: 7     E>A>D; B>D; C>D
skip D>E: 6     E>A>D; B>D; C>D
lock E>B: 5     E>A>B>D; C>D
lock E>C: 4     E>A>B>D; E>C>D
lock B>C: 3     E>A>B>C>D
lock A>B: 2     E>A>B>C>D
skip C>A: 1     E>A>B>C>D

Result: winner is E.

Tideman's (regular) method is decisive and easy to apply.  It provides clone
independence ("almost always", according to Tideman), but may sometimes
violate GMC (as you showed), since it may be forced to skip very strong
defeats.


Finally, Schulze (results from yesterday).

Schulze:

Mike: "A beats B if more voters rank A over B than vice-versa.  The strength
of that defeat is the number of voters who ranked  A over B.  There's a
"beat path" from A to B if either A beats B, or if A beats something that
has a beat path to B.  The strength of a beat path is measured by its
weakest defeat.  If A has a stronger beat path to B than B has to A, then A
has a Schulze win against B.  If an alternative has a Schulze win against
each one of the others, then it wins."

A>>D: 7:6 (A>D vs. D>E>A)
B>>A: 6:5 (B>D>E>A vs. A>D>E>B)
B>>D: 7:5 (B>D vs. D>E>B)
B>>E: 6:5 (B>D>E vs. E>B)
C>>A: 6:4 (C>D>E>A vs. A>D>E>C)
C>>B: 5:4 (C>D>E>B vs. B>D>E>C)
C>>D: 7:4 (C>D vs. D>E>C)
C>>E: 6:4 (C>D>E vs. E>C)
E>>A: 8:6 (E>A vs. A>D>E)
E>>D: 7:6 (E>A>D vs. D>E)

Result: winner is C.

Schulze's method provides (complete?) clone independence and satisfies GMC.
It decisively resolves a larger class of problems than any of the sequential
methods that have been discussed (except regular Tideman), by simultaneously
considering _all_ possible beat paths.  It's a more complex method to
describe, however.


Conclusion:

It appears to me that we've been led down a false path in trying to adapt
Tideman's method so that it can be both: 1) simpler than Schulze to
describe, and 2) better than Smith//Condorcet(EM), by adding
clone-independence to what SC provides.  Regular Tideman sacrifices GMC
compliance to get clone independence, which is probably a poor trade-off.
The three equivalent variants (Improved Tideman, Reverse-Tideman, Pairwise
Dropping) are simpler than Schulze, and probably somewhat clone-independent,
but they are indecisive.  Adding a good tiebreaker to these methods will
probably increase the complexity of the definition, with the result that
there might be little or no improvement in that regard over Schulze.

Unless a *very simple* tiebreaker could be found that would ensure that 1)
the result satisfies GMC, and 2) preferably produces the same result as
Schulze, in cases where Schulze is decisive, I see little hope for these
methods.

Could Condorcet(EM) be used as the tiebreaker?  When I apply "Pairwise
Dropping//Condorcet(EM)" to this example, I get C, which happens to be the
same as Schulze.  (Pairwise Dropping or Reverse-Tideman would be the best
descriptions to use, due to the simplicity of definition).  Can it be proven
that the Schulze winner will always be among the set of winners produced by
Pairwise Dropping/Reverse-Tideman/Improved Tideman?  If not, then it seems
unlikely that _any_ tiebreaker would guarantee clone independence, the way
Schulze does.


Norm Petry

P.S.  I didn't comment on your FOP or LOP proposals, as they seemed at least
the equal of Schulze in complexity, and were designed to be decisive in
cases where Schulze was thought not to be.  So far, we haven't found _any_
cases where Schulze is indecisive, so these methods seem unnecessary (esp.
since you didn't recommend them yourself, due to Pareto violations, etc.).



-----Original Message-----
From: Mike Ositoff <ntk at netcom.com>
To: election-methods-list at eskimo.com <election-methods-list at eskimo.com>
Cc: ntk at netcom.com <ntk at netcom.com>
Date: August 7, 1998 4:27 PM
Subject: Re: Tiebreakers, Subcycle Rules


>
>
>My apologies, especially to Markus: I forgot to consider the
>longer beatpaths between A, B, & C. I only noticed the
>subcycle beatpaths.
>
>So what I said about Schulze's method being indecisive might
>not be true at all--but you already knew that, before I did.
>
>I don't have an example where it's indecisive, and I don't
>know if it has that problem at all, or more than the other
>versions, like Sequential Dropping (I wouldn't object to a
>better name for Sequential Dropping).
>
>In a situation with the defeats configured like that example,
>if A loses with respect to D & E, and if C wins weth repect
>to them, then  I realize now that, by beatpaths outside
>the subcycle, C inevitably beats A, and the winner with
>respect to the non-subcycle alternatives is the winner
>against the subcycle alternatives.
>
>But what if A, B, & C have different defeat magnitudes against
>D? Could a person devise an example, then, where the
>method is indecisive? But then I don't know how the other
>versions would do in such an example either, so maybe
>Schulze & Sequential Dropping have the same status
>in that regard.
>
>Mike
>
>
>
>
>