[EM] Fw: IBCM, Tideman, Schulze

[Markus Schulze]

Dear Steve,

you wrote (2 June 2000):
> Consider this example:
>
>    Majorities:  BD65,DC64,CB63,AF62,FE61,CF52,EA51,AB49
>    (All other pairings are ties.)
>    MTM & IBCM elect A.  Schulze elects B.
>   
>    There is a "majority strength beatpath" from B to A:
>    BDCFEA has strength 51.
>
>    But in what sense of "majority" can it be said that a
>    majority has "rejected" A, without also being able to say
>    a majority has "rejected" B?  A's only defeat is EA51,
>    which is shaky (smallest majority in a cycle).  Compare
>    that to B's CB65 defeat, which isn't counted against B.
>    (Blake Cretney made a similar analysis of this issue
>    on 1/24/2000, noting that the Schulze method neglects
>    "extra" information contained in the votes which may
>    undermine links in a beatpath chain.  Markus considers
>    this neglect a "feature" of the Schulze method, but it
>    makes sense to view it as a minor bug.)
>
>    An argument might be made that a beatpath is not just an
>    abstraction, that it is comprised of real voters too.
>    But that's a dubious argument.  Consider this simple
>    scenario to illustrate:
>       35: ABC
>       33: BCA
>       32: CAB
>       Majorities: BC68,AB67,CA65
>    The strongest beatpath of length two or more is ABC67.
>    Who are the "real voters" counted in the ABC beatpath?
>    The AB67 link includes 32 voters who rank C over A, and
>    the BC68 link includes 33 voters who rank C over A.  The
>    strength of a beatpath depends on voters who would oppose
>    the beatpath, and thus are not real voters. (This sort of
>    example is one of the concerns I have about how hard it may
>    be to convince people about the merits of the Schulze method,
>    because there's something "smelly" about counting for a
>    beatpath some voters who oppose the beatpath.)

It seems to me that you haven't understood the concept of beat
paths. The Schulze method is identical to SD (as long as the
pairwise matrix doesn't contain identical elements). Therefore
it is not feasible to say that the Schulze method is "smelly"
without saying simultaneously the same about SD.

Suppose that candidate A and candidate B are in a cycle
A > C[1] > ... > C[n] > B > D [1] > ... > D[m] > A.
Suppose that in the SD heuristic this cycle is broken between
A and C[1] or between C[n] and B or between C[i] and C[i+1]
then this is absolutely the same as if in the beat path heuristic
it is said that the beat path A > C[1] > ... > C[n] > B is weaker
than the beat path B > D [1] > ... > D[m] > A. Therefore if you
don't think that SD is "smelly" then it is not feasible to say
that the Schulze method is "smelly."

Suppose that the strongest beat path from candidate A to candidate B
is strictly weaker than the strongest beat path from candidate B
to candidate A, then this simply means that candidate A cannot be a
SD winner. With this simple observation it is possible to implement
a fast algorithm to calculate the SD winner. Therefore the concept
of beat paths is only a mathematical tool for a more elegant
description of SD. I want you to remember that it is you who
introduced the "Beatpath Criterion" (BC) to this list and claimed
that it is more than just a mathematical tool (26 Feb 2000): "So BC
is at the heart of the defensive strategy criteria." Also you praise
the Tideman method for meeting your Beatpath Criterion. Therefore
also the Tideman method must be "smelly." Maybe you should call your
Beatpath Criterion "Smelly Criterion."

It is strange that you praise the Beatpath Criterion because it can
be defined in terms of beat paths and simultaneously you criticize
Beatpath GMC because it can be defined in terms of beat paths.
It is strange that you praise the IBCM method because it can
be defined in terms of beat paths and simultaneously you criticize
the Schulze method because it can be defined in terms of beat paths.

******

You wrote (2 June 2000):
> Norm is one of the people I had in mind when I wrote a couple
> of weeks ago that some people in EM have written they think it
> may be too hard to explain Schulze's method.

You wrote (3 June 2000):
> Markus wrote (3 June 2000):
> > By the way, when Schulze, path voting, SD and SSD are more
> > intuitive than IBCM and DCD for the members of this mailing
> > list then I don't see any reason why this shouldn't be true
> > for "members of the general public."
>
> I'm unaware of any poll in EM about which is more intuitive.  I
> believe Mike Ossipoff and I consider IBCM (DCD) more intuitive
> than Schulze.

You erred when you suggested that Norman and Mike consider the
Schulze method to be less intuitive than Tideman or IBCM. If you
had read their mails more carefully, then you would have observed
that they don't consider the Schulze method to be less intuitive.
They only consider the beat path heuristic to be less intuitive
than the cycle heuristic. Mike wrote (3 Jun 2000): "When you start
talking about beatpaths, and how to measure their strength, your
listener will feel that it's all arbitrary. Sure, it makes sense
its own way, but would he have any reason to believe that the
count should be done by that rule, out of all the possible rules?
Dropping the weakest defeat from among those that are in conflict
is obvious & natural." Norman wrote (27 May 2000): "I have
expressed doubts in the past about how explainable Schulze's
method would be to members of the general public. This problem
is compensated for by the method's technical excellence. As an
iterative method, IBCM is much less elegant than Schulze's method,
and is no easier to explain." In so far as Norman differs between
the "Schulze method" on the one side and "iterative methods" on
the other side, it is clear that Norman uses the term "Schulze
method" as a synonym for the beat path heuristic.

But in so far as the Schulze method can also be defined in
terms of cycles, the fact that Mike and Norman consider the
beat path heuristic to be less intuitive than the cycle
heuristic cannot be used as an argument against the Schulze
method.

Definition:

   Drop the weakest defeat that is in a cycle. Repeat that until
   there's an unbeaten candidate. If there are in any situation
   q defeats each with the same strength, then consider all
   q! possible orders to consider these defeats one after the
   other and proceed with all q! possible orders.

It seems to me that you consider the fact that the Schulze method
can also be explained in terms of beat paths to be a disadvantage
of the Schulze method. I don't agree with you. To my opinion, the
fact that the Schulze method can also be explained in terms of
beat paths is an important advantage of the Schulze method:

(1) If you don't like the beat path heuristic then you don't need
    to use it. Therefore it cannot be a disadvantage of the Schulze
    method that it can also be explained in terms of beat paths.

(2) Suppose that there are N candidates. Suppose that the pairwise
    matrix doesn't contain identical elements. If you use the beat
    path heuristic for the Schulze method, then the runtime is O(N^3).
    The reason: When you use the Dijkstra Algorithm or the Floyd
    Algorithm to calculate the beat paths, the runtime is O(N^3).
    On the other side, if you use the cycle heuristic to calculate
    the Schulze winner or the Tideman winner, then the runtime is
    O(N^4). The reasons: 1. The runtime to check whether a given
    pairwise defeat is in a directed cycle is O(N^2). 2. You have to
    check this for O(N^2) pairwise defeats.

(3) Suppose that there are N candidates. Suppose that the pairwise
    matrix doesn't contain identical elements. Suppose that you can
    guess the Schulze winner. Then -if you use the beat path heuristic
    for the Schulze method- the runtime to check whether this guess is
    correct is O(N^2) because you only have to calculate the beat
    paths from this guessed winner to the other candidates and from the
    other candidates to this guessed winner. On the other side, if you
    use the cycle heuristic for the Schulze method or the Tideman method
    then the runtime to check whether a guess is correct is still O(N^4).

(4) Suppose that there are N candidates. Suppose that the pairwise
    matrix contains many identical elements. If you use the beat
    path heuristic for the Schulze method, then the runtime is still
    O(N^3). But if you use the cycle heuristic to calculate the
    Schulze winner or the Tideman winner, then the runtime is
    superpolynomial!

(5) To prove whether a given criterion is met is usually more simple
    when you use the beat paths heuristic than when you use the cycle
    heuristic.

Therefore the fact that the Schulze method can be explained in terms
of beat paths while the Tideman method cannot be explained in terms
of beat paths is a very important advantage of the Schulze method.

Again: The Schulze method is not a synonym for the beat path heuristic.
The Schulze method can be defined in terms of beat paths and in terms
of cycles. If you don't like beat paths, then this is not a reason to
reject the Schulze method. But (especially when there are many identical
elements in the pairwise matrix) it is an important advantage of the
Schulze method (compared to the Tideman method) that it can also be
defined in terms of beat paths.

With this seventh reply, I believe that I have commented on all
important parts of your 2 June 2000 mails and your 3 June 2000 mails.

Markus Schulze
schulze at sol.physik.tu-berlin.de
schulze at math.tu-berlin.de
markusschulze at planet-interkom.de