Maybe None Clone-Independent

[Norman Petry]

Mike,

I've verified your result for Pairwise-Dropping.  It does appear to violate
Independence of Clones (GITC) in probably a *very small* class of problems.
I applied Schulze to the same problem, with the following result:

A>>{D,E,F} 2
A>>G 5
A>>H 6
D>>A 1
D>>{E,F} 10
E>>{D,F} 20
F>>D 30
F>>E 10
{D,E,F}>>{G,H} 4
{G,H}>>A 1
{G,H}>>{D,E,F} 2
G>>H 2
H>>G 5

When A's clones, B&C are added, the result is:

A>>{B,C} 100
B>>{A,C} 200
C>>A 300
C>>B 100
{A,B,C}>>{D,E,F} 2
{A,B,C}>>G 5
{A,B,C}>>H 6
D>>{A,B,C}1
D>>{E,F} 10
E>>{D,F} 20
F>>D 30
F>>E 10
{D,E,F}>>{G,H} 4
{G,H}>>{A,B,C}1
{G,H}>>{D,E,F} 2
G>>H 2
H>>G 5

Therefore, the Schulze winner is decisively B (a clone of A, which is OK).
Earlier, Markus provided a proof that the beat-path method is
clone-independent, and we find no exception to that here.

What you have proven, though, is that Sequential Dropping <> Schulze, and
appears to violate GITC in at least a few cases.  I guess I shouldn't have
gone out on that limb!  Nevertheless, it does appear to be an excellent
_approximation_ of Schulze, in the few cases I've examined.

On technical grounds, Schulze is still superior, but as a practical
proposal, Pairwise Dropping might have the edge.  Furthermore, since the
definition is at least as simple as Smith//Condorcet(EM), and appears to
provide much more (GITC (usually), Positive-Involvement, No-Show, etc.), we
could probably toss that one out as a recommendation.  It even rivals
Condorcet(EM) in simplicity, so that method might not be needed either.  It
*must* have a better name, though!

Can it be proven that the winner of Pairwise Dropping is always a member of
the Smith set?  That would seem to be the main requirement for getting rid
of the other two methods (I note that it is in this example, as Smith =
{A..H}).

***

With regard to Tideman's tiebreaker, you wrote:

>Because Tideman said that his method could fail
>Independence from Clones unless complicated modifications
>are added, and since I now have an 8-candidate example
>where Sequential Dropping fails that criterion, could
>it be that none of these basic methods can always meet
>that criterion without complicated modification?

The tiebreaker he proposed to provide "complete" independence of clones
("Complete Independence of Clones in the Ranked Pairs Rule", Soc Choice
Welfare (1989) 6: 167-173) is not needed for either Schulze or Pairwise
Dropping.  Essentially, he was looking at a problem his method faced when
many ties were encountered.  Since he locks or skips majorities
sequentially, he found that his final result was order-dependent when a
number of propositions had tied majorities.  Sometimes, it was possible for
the method to violate clone-independence as a result.  He proposed using a
random ballot as a tiebreaker to determine the order in which propositions
of equal strength should be listed (prior to locking/skipping), and found
that by doing so, he could produce complete clone-independence (at least, if
I've understood the formulese correctly).

Schulze's method never makes these mistakes, and neither did Pairwise
Dropping, when I applied it to Tideman's example.  While Pairwise Dropping
doesn't provide complete clone-independence, it appears to be better than
Tideman in that regard.  Schulze's method is clone-independent in all cases,
as he proved on 1 Jan 1998 (Re: Condorect sub-cycle rule):

>Suppose, B is not a twin of A. Then the introduction of
>twins cannot change the maximum beat-path from A to B,
>because all the twins from a set of twins have the same
>defeat against non-twins. Thus, the maximum beat-path
>from A to B cannot be increased by adding twins.


Norm Petry


-----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 9, 1998 4:32 AM
Subject: Maybe None Clone-Independent


>
>Because Tideman said that his method could fail
>Independence from Clones unless complicated modifications
>are added, and since I now have an 8-candidate example
>where Sequential Dropping fails that criterion, could
>it be that none of these basic methods can always meet
>that criterion without complicated modification?
>
>Here's my example:
>
>At first there are 6 alternatives. {D,E,F} is a clone-set
>subcycle.
>
>{D,E,F}>A 1
>A>G 3
>G>{D,E,F} 2
>{D,E,F}>H 4
>H>G 5
>A>H 6
>
>{D,E,F}>A gets dropped first, and A wins.
>
>D>E 10
>E>F 20
>F>D 3
>
>***
>
>Now, 2 other alternatives enter the race, B & C.
>
>They form a clone-set subcycle with A:
>
>A>B 100
>B>C 200
>C>A 300
>
>Now, first {D,E,F}>{A,B,C} 1 is dropped.
>
>The next greater defeat that conflicts with greater ones
>is G>{D,E,F} 2. That defeat is dropped.
>
>Next, D>E 10 is dropped, and E is unbeaten, and wins.
>
>So the addition of the 2 clones defeated A.
>
>***
>
>With an 8-candidate example, I can't be sure that I didn't
>make an error, of course, but it seems correct.
>
>I haven't yet checked Schulze in that example, but even
>if Schulze, unlike Tideman or Sequential Dropping, _never_
>violates Independence From Clones, I still say that this
>example is so improbable that, for all intents & purposes,
>SD is clone-independent. And its greater simplicity, and
>its decisiveness, and consequent freedom from need to further
>add to its rules with a tiebreaker--those things outweigh
>that highly improbable Clone Independence violation.
>
>***
>
>Mike
>
>
>