[EM] Demonstration that Schulze = Cloneproof SSD

[MIKE OSSIPOFF]

In this message, "Schulze" means BeatpathWinner, though I now
realize that Markus's actual proposal is Beat-&-Tie-Path-Winner.

I'm going to show that Cloneproof SSD & Schulze are just 2 wordings
of the same method, 2 implementations that always give the same
outcome.

I'll be using the beatpath definition of the Schwartz set. The
definition that I've been using, and with which I've defined SSD
& Cloneproof SSD is the unbeaten set definition. It's a well-established
& accepted fact in voting system discussion that those 2 definitions
always define the same set. Though I'll be using that fact without
proof in this letter, I'll demonstrate why it's so in an immediately
subsequent letter.

For now, I'll just state the beatpath definition:

If there's a beatpath from A to B, but not from B to A, then B
has an unreturned beatpath.

An option is in the Schwartz set if & only if it doesn't have an
unreturned beatpath.

[end of definition]

In this letter, "AB" means "The beatpath from A to B whose weakest
defeat is the strongest". "AB>BA" means that AB's weakest defeat
is stronger than that of BA.

By "Schwartz set", I mean "current Schwartz set", the Schwartz set
based only on undropped defeats.

Why Schulze & Cloneproof SSD are the same:

Suppose that option A is a Schulze winner. That means that, for all
B, distinct from A, AB>BA, or AB = BA. By the beatpath definition of the 
Schwartz set, that means that A is in the Schwartz set.

For any particular B:

AB & BA are both in the Schwartz set. That's because AB & BA constitute a 
cycle containing A, which is in the Schwartz set, and because if one member 
of a cycle is in the Schwartz set, then ever member of that cycle is in the 
Schwartz set. To show why that is: Say A is in the Schwartz set, and X beats 
A. The Schwartz set is unbeaten from without, and so if A is in it, then so 
must X be in it. Likewise for some Y which beats X. We can repeat that 
argument all around the cycle, to show that every element of the cycle is in 
the Schwartz set.

Since all the defeats in AB & BA are in the Schwartz set, they all meet the 
Schwartz set requirement for dropping. That means that
AB cannot be broken before BA, since they both qualify for dropping by being 
in the Schwartz set, and because BA contains a weaker defeat than AB does.

If AB or BA is going to be broken, by dropping one of its defeats,
it will be BA that is broken before or simultaneous with AB, because 
Cloneproof SSD
drops weaker defeats in the Schwartz set before stronger ones. Of course,
when BA has been broken, all of the weaker beatpaths from B to A will
have been broken also--before AB could be broken. So every B to A beatpath 
gets broken before AB can be broken.

That means that A can never be removed from the Schwartz set.

Because A is always in the Schwartz set, that means that every member
of any cycle containing A is also in the Schwartz set.

Since any cycle containing A is in the Schwartz set, and since
Cloneproof SSD always results in there being no cycles in the Schwartz
set, then any cycle containing A is going to be broken. Every beatpath
from A to B forms a cycle with every beatpath from B to A. None of those 
cycles
will remain when Cloneproof SSD's process is concluded.

For every B distinct from A:
Because AB's weakest defeat is stronger than or equal to BA, and because BA,
by definition, has a stronger weakest defeat than any other beatpath
from B to A, then, by Cloneproof SSD's rules, every Beatpath from B
to A will be broken before AB is broken, or simultaneously with it. That 
means that, when
the cycles containing A & B are broken, as they must be eventually,
there will be no beatpaths from B to A, because Cloneproof SSD drops
weakest defeats first. That's true for every B distinct from A, and
so eventually A will have no beatpaths to it, since, as stated previously, 
Cloneproof SSD continues till there are no cycles in the Schwartz set.

A pairwise defeat is a 1-step beatpath. The references to beatpaths
in this demonstration say nothing that excludes 1-step beatpaths from
those references' application. And so, eventually A will have no
defeats.

Now, suppose that A is not a Schulze winner. That means that, for
at least one B, distinct from A, BA>AB.

Again, AB & BA constitute a cycle, and if any element of a cycle is in the 
Schwartz set then the entire cycle is in the Schwartz set. So the defeats in 
BA & in AB are all in the Schwartz set or all not in it.


If neither AB nor BA are in the Schwartz set, then neither beatpath ever 
gets broken, and so A always has a defeat, since it always has a beatpath to 
it.

If AB & BA are both in the Schwartz set, then AB gets broken before BA does, 
since AB < BA.

If AB gets broken before BA does, then so does every A to B beatpath, since, 
by definition, AB is stronger than all of those. Then, by the beatpath 
definition of
the Schwartz set, A is removed from the Schwartz set. Since A has
a beatpath to it, then A has a pairwise defeat. Since no defeat that
isn't among the Schwartz set can be dropped, then A will always have
that defeat.

I've shown that if A is a Schulze winner, then A will have no defeats
at the conclusion of Cloneproof SSD's count, and that if A is not
a Schulze winner, then A will have a defeat at the conclusion of
Cloneproof SSD's count.

Mike Ossipoff

_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com