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
