[EM] Reply to Norm's misdefinition

[Norman Petry]

On January 30, 2001 Mike Ossipoff wrote:

>
>But Norm invented a wildly different method which he calls Cloneproof
>SSD. Norm, I encourage you to invent whatever you want to, but please
>use an original name for your inventions. And would you be so kind as
>to let me be the one who decides what is my definition of a method
>that I propose?
>

etc.

Mike seems to be implying that I was attempting to redefine his proposed
method in order to level false criticisms against it.  I honestly don't know
why he should think I would want to do that.  Mike is certainly correct that
I had misunderstood what he had intended in his Cloneproof SSD proposal.
However, this was simply an honest misunderstanding -- I was not attempting
to misrepresent him.

When I began looking at Cloneproof SSD, I referred to the definition that
Mike had supplied, which was:

"Drop the weakest defeat that's among the Schwartz set. Repeat till there
are no cycles in the Schwartz set. Whoever is unbeaten at that time wins."

The way I interpreted this was:

1. Calculate the Schwartz set, S.
2. Drop the weakest defeat in S (if there is more than 1 equal, drop them
all)
3. Repeat (2), until there are no cycles among candidates in S.

Mike's intended method was:

1. Calculate the Schwartz set, S.
2. Drop the weakest defeat in S (if there is more than 1 equal, drop them
all)
3. Repeat (1), until there are no cycles among candidates in S.

I believe that the definition that Mike supplied was unclear, and that the
my (admittedly incorrect) interpretation of Cloneproof SSD is also described
by the definition he supplied.  The problem is that it is not obvious what
exactly is being repeated -- is it the dropping of weakest defeats, or the
calculation of Schwartz sets?  Even with Mike's clarified definition, I
don't think it is obvious.  Others may disagree, of course.

In any case, the analysis of "Cloneproof SSD" that I posted was incorrect,
since it does not pertain to the method Mike intended.  It is I believe an
accurate analysis of "Iterated Schwartz//Young", but that of course is
unimportant, since no one is seriously proposing such a method (I certainly
have no wish to do so ;-)

>
>Norm, you said you were going to test for that equivalence with your
>simulations. I take it that you've done that testing for your very
>own "Cloneproof SSD", which isn't mine. Now, why don't you start over,
>and, this time, test for Cloneproof SSD, as I define it, to test for
>that equivalence.
>

After receiving your reply on Sunday ("Possible misunderstanding of
definition"), I did precisely this.  I applied both the Schulze method and
my revised implementation of Cloneproof SSD to a series of 'Smith Matrices',
and could not discover *any* difference in results over a great many trials
with a large number of candidates (25,000 trials, 15 candidates).
Therefore, I think it is safe to say that Cloneproof SSD is equivalent to
Schulze, and therefore has the same properties as that method (Clone
Independence, Monotonicity, etc.)

A *proof* that the methods are equivalent would be better, of course, but I
have no doubt that Cloneproof SSD is the same as the Schulze beatpath method
(at least, as I had always understood it -- more on this later).

>Yes or No: Can you find an example where Cloneproof
>SSD fails a criterion that Schulze passes, or is less decisive than
>Schulze? Yes or No: Can you find an example where the 2 methods produce
>different winner-sets, or different win-probabilities?

No.  The methods are equivalent, provided that the 'beatpaths' used in
Schulze's method are constructed using pairwins only.  I had always
interpreted Schulze's method in that way -- that is, a 'beatpath' is
composed only of 'beats' (pairwise victory vote totals).  However, in a
recent message to EM, Markus clarified that his concept of beatpaths can
actually contain tied values as well.  With that interpretation, the two
methods *are* slightly different.  Here's what Markus wrote on that subject:

>From: Markus Schulze <schulze at sol.physik.tu-berlin.de>
>To: election-methods-list at eskimo.com <election-methods-list at eskimo.com>
>Date: January 21, 2001 12:29 PM
>Subject: Re: [EM] Cloneproof SSD
[...]
>
>The winner of the Schwartz set heuristic and the winner of the
>beat path heuristic can differ only when there is at least one
>pairwise tie.
>
>Example:
>
>   A:B=50:50
>   A:C=35:25
>   B:C=40:60
>
>The Schwartz set heuristic would choose candidate A because
>candidate A is the unique Schwartz winner. The Schwartz set
>heuristic treats all pairwise ties in the same manner.
>
>The beat path heuristic would choose candidate C because beat
>paths must be able to contain pairwise ties. Otherwise it would
>be possible that there is neither a beat path from candidate X
>to candidate Y nor from candidate Y to candidate X.
>

I had never noticed this detail before, and wondered if Markus had changed
the definition of his method.  However, looking at his earliest description
of the beatpaths, this is in fact the definition that he used.  On Sat, 04
Oct 1997 he wrote (EM, "Re: Condorect sub-cycle rule"):

*****

What are beat-path-defeats?

A defeats B M:N via a beat-path means:

  M is the highest number with

     X >> Y means, that the number of voters, who prefer
     X to Y, is LARGER THAN OR EQUAL TO [emphasis added] the number of
voters,
     who prefer Y to X, and that X gets at least M votes in
     the pairwise comparison of X versus Y.

     The following statement is valid:
     A >> B or there is a set of candidates C[1],...,C[s]
     with A >> C[1] >> ... >> C[s] >> B.

  N is the highest number with

     X >> Y means, that the number of voters, who prefer
     X to Y, is larger than or equal to the number of voters,
     who prefer Y to X, and that X gets at least N votes
     the pairwise comparison of X versus Y.

     The following statement is valid:
     B >> A or there is a set of candidates D[1],...,D[t]
     with B >> D[1] >> ... >> D[t] >> A.

  And M > N.

*****

A more accurate description for Markus' concept would be 'beatOrTiePath',
but that's a bit clumsy, I suppose.

My previous testing of Schulze used pairwins only, so the result of changing
the method to allow for ties in the beatpaths will yield slightly different
results than Cloneproof SSD.  Markus argues that by allowing ties in
beatpaths, the method does a bit better job at minimising the number of
voters who may be dissatisfied with the choice of winner.  In that example,
option A is opposed by at most 50 voters, whereas option C is only opposed
by 40, and therefore it is better to pick C.  I have modified my simulator
to correct for the revised definition of Schulze, and will post some results
showing what change (if any) this has on the method.

Markus claims that allowing ties (or wins) in beatpaths is all that is
necessary to guarantee that the method satisfies the Smith criterion (or
LIIAC).  Since Smith allows pairties, this sounds correct to me, but I
haven't tested the revised implementation for Smith compliance.  I would
guess that all of Mike's strategy-free criteria would still be met as well
(how could one hope to manipulate an election outcome by relying on pairwise
ties?), but perhaps Mike is in a better position than I am to comment on
that.

>Can we dispense with wasting people's time by defining & discussing
>Reverse Tideman, DCD, IBCM, & Peyton Young's method? I don't want to
>waste the letter kilobytes needed to demonstrate that none of those
>, iterated or otherwise, is Cloneproof SSD. When talking about Cloneproof
>SSD & its properties, I'm going to have to insist that we only use
>my own definition, by my own wording.
>
>So then Norm shows that his method, which he calls "Cloneproof SSD",
>but which I'll call Petry's method, fails Monotonicity.
>
>If you want to show that Cloneproof SSD fails a Criterion, Norm,
>show that by using _my_ definition of Cloneproof SSD.
>

The tone of these comments is needlessly belligerent.  I simply
misunderstood your proposal, and thought that my analysis *did* apply to the
method you were writing about.

[...]

>Cloneproof SSD is SSD with a new stopping rule: We don't stop until
>there are no cycles in the current Schwartz set. Otherwise it's the
>same as SSD. I'll restate it here:
>
>Drop the weakest defeat that's among the current Schwartz set. Repeat
>till there are no cycles in the current Schwartz set.
>
>(The current Schwartz set is the Schwartz set based only on undropped
>defeats).
>
>[end of definition]
>
>As I said, I'd use that with the same add-on iterative tiebreaker that
>you use with Schulze: If the method produces a tie by undefeating more
>than 1 option, then drop everything but the undefeated options and
>re-apply the method to that set of options. Quit when that doesn't
>reduce the size of the set of undefeated options.
>
>Now Norm, is that clear? That definition is not complicated.
>

I agree it's not complicated (presupposing one understands the Schwartz-set
concept), but no, it still isn't very clear, for reasons explained above.  I
do now understand what you mean, though.

--
Norm Petry