[EM] Tideman and GMC

[Markus Schulze]

Dear participants,

the main difference between Steve's IBCM method and my
Schulze method becomes clear when Mike's DCD heuristic
for the IBCM method and my "iterative Schwartz" heuristic
for the Schulze method are used.

DCD:

   Step1: Start with the weakest pairwise defeat.

   Step2: If the current pairwise defeat is in a directed
   cycle then this pairwise defeat is dropped. Go to the
   next weakest pairwise defeat.

   Step3: Repeat Step2 until there are no directed
   pairwise cycles any more. If there is more than one
   undominated candidate then this method is re-applied
   to these undominated candidates.

Iterative Schwartz:

   Step1: Start with the weakest pairwise defeat.

   Step2: If the current pairwise defeat is in a directed
   cycle then this pairwise defeat is dropped. Go to the
   next weakest pairwise defeat.

   Step3: Repeat Step2 until there is a Schwartz winner.

The iterative Schwartz heuristic has also been called
"beat path Schwartz." Mike has proposed a very similar
heuristic and called it "Sequential Dropping." Also Blake
has proposed a very similar heuristic and called it
"Goldfish." The fact that these heuristics have been
proposed by different people demonstrates that these
people have understood not only the _definition_ of the
Schulze method but also the _idea_ behind this method.
This demonstrates that the Schulze method is very
intuitive compared to the IBCM method.

******

Example:

   26 voters vote C > A > B > D.
   20 voters vote B > D > A > C.
   18 voters vote A > D > C > B.
   14 voters vote C > B > A > D.
   08 voters vote B > D > C > A.
   07 voters vote D > A > C > B.
   07 voters vote B > D > A = C.

   Then the matrix of pairwise defeats looks as follows:

   A:B=51:49
   A:C=45:48
   A:D=58:42
   B:C=35:65
   B:D=75:25
   C:D=40:60

DCD:

   (1) The pairwise defeat A:C is dropped because it is
       in a directed cycle C > A > B > D > C.
   (2) The pairwise defeat A:B is not in a directed
       cycle and is therefore not dropped.
   (3) The pairwise defeat A:D is not in a directed
       cycle and is therefore not dropped.
   (4) The pairwise defeat C:D is dropped because it is
       in a directed cycle D > C > B > D.
       The DCD heuristic stops because there are no
       directed cycles any more. As there are two
       undominated candidates (A and C) the DCD heuristic
       is re-applied amongst these two candidates.
       As candidate C pairwise beats candidate A,
       candidate C is the IBCM winner.

iterative Schwartz:

   (1) The pairwise defeat A:C is dropped because it is
       in a directed cycle C > A > B > D > C.
       The iterative Schwartz heuristic stops because
       candidate A has become a Schwartz winner.
       Therefore candidate A is the Schulze winner.

In the example above, the DCD heuristic terminates after
4 steps while the iterative Schwartz heuristic terminates
after one step. In so far as in every step of the DCD
heuristic the same pairwise defeat is considered and the
same pairwise defeats are scanned (to decide whether this
currently considered pairwise defeat is in a directed cycle)
as in the iterative Schwartz heuristic, more pairwise defeats
are taken into consideration and more pairwise defeats are
scanned in the DCD heuristic than in the iterative Schwartz
heuristic in the example above.

Question: Is it possible to create examples where the
DCD heuristic needs fewer steps than the iterative Schwartz
heuristic? Answer: No! Reason: It is possible that there
is a Schwartz winner although there are still directed
cycles; but it is not possible that there is no directed
cycle any more and still no Schwartz winner. Therefore it
is possible to create examples where the iterative Schwartz
heuristic terminates before the DCD heuristic terminates.
But it is not possible to create examples where the DCD
heuristic terminates before the iterative Schwartz heuristic
terminates.

Therefore, it is possible to create examples where the
DCD heuristic takes more pairwise defeats into consideration
(to decide whether this pairwise defeat has to be dropped)
and scans more pairwise defeats (to find out whether the
currently considered pairwise defeat is in a directed cycle)
than the iterative Schwartz heuristic. But it is not possible
to create examples where the iterative Schwartz heuristic
takes more pairwise defeats into consideration or scans more
pairwise defeats than the DCD heuristic.

Therefore it is possible to create examples where the IBCM
winner depends on more elements of the pairwise matrix than
the Schulze winner. But it is not possible to create examples
where the Schulze winner depends on more elements of the
pairwise matrix than the IBCM winner.

This additional information on which the IBCM winner depends
is superfluous to guarantee that the used election method
meets Local Independence from Irrelevant Alternatives,
Complete Independence from Clones and Monotonicity. But this
additional information offers additional possibilities to the
voters to manipulate the result of the elections by voting
insincerely.

Therefore an election method should not only meet many
non-manipulability criteria. The winner should also depend
on as few information as possible. In so far as the Schulze
winner usually depends on fewer information than the IBCM
winner and in so far as the Schulze method meets all
non-manipulability criteria which are met by the IBCM method,
the Schulze method is -to my opinion- better than the IBCM
method.

******

Steve wrote (13 May 2000):
> Many people in this maillist have commented on how complex 
> and abstract the Schulze definition may seem to the lay public.  

Steve didn't identify the participants in this maillist who
commented on this. He neglected that the iterative Schwartz
heuristic for the Schulze method and Mike's DCD heuristic for
the IBCM method are almost identical. And he neglected that
the Schulze method and the IBCM method are based on the same
concept of beat paths.

******

Steve wrote (13 May 2000):
> I think it was Norm who wrote about a month ago that a simpler 
> wording of Schulze had been posted, but I haven't seen it.  If 
> there's a simpler wording, please let me know how to find it in 
> my EM archive.

Steve is either talking about Norman's 9 Apr 2000 mail or about
Norman's 10 Apr 2000 mail.

In his 9 Apr 2000 mail, Norman presents a polynomial algorithm
to calculate the Smith winners, the Schwartz winners and the
Landau winners. Unfortunately, Norman doesn't write anything
about the Schulze winners or the IBCM winners in this mail.
 
In his 10 Apr 2000 mail, Norman writes:
> I did not "reject mathematics", or criticize its use in
> the anlysis of voting methods here on EM, or anywhere else.
> Indeed, mathematics can be a very useful tool in the analysis
> of many things, including voting methods.  Proofs that
> demonstrate unresolveable conflicts between seemingly
> reasonable criteria (such as Arrow's theorem) are very useful.
> The proofs I like best are those that actually allow for
> simplification.  For example, a while ago, Markus posted a
> proof that beatpaths cannot be cyclic.  This proof made it
> possible to redefine the Schulze method without reference
> to the Schwartz set, which I (at least) regarded as a
> simplification.  Mathematics like this I appreciate greatly.
> Also, if mathematicians find it easier to understand a
> particular voting method when it is described in their
> language, I think that's a perfectly reasonable thing to do,
> and it may be helpful by revealing ambiguities/imprecision
> in the definition of the method that need to be resolved.

Norman is talking those mails in which I prove that the
iterative Schwartz heuristic and the beat path heuristic
for the Schulze method are identical. These mails are very
important because of several reasons. Example: The proof that
the Schulze method meets monotonicity and independence from
clones is significantly more simple when you use the beat path
heuristic than when you use the iterative Schwartz heuristic.

******

Steve wrote (13 May 2000):
> When MTM (or IBCM) and Schulze are both decisive but disagree
> on the winner, the MTM (or IBCM) winner beats pairwise the
> Schulze winner more often than vice versa.  (And the IBCM
> winner beats the MTM winner more often than vice versa,
> suggesting IBCM is best of the three.)  These claims are
> based on computer simulations using randomly generated voter
> rankings.

That's a flawed argument.

Steve claims that if the winner of election method B pairwise
beats the winner of election method A more often than vice
versa then election method B is better than election method A.
If Steve's claim was true then to every election method A a
better election method B could be created as follows: If there
is no candidate who pairwise beats the winner of election
method A then the winner of election method B is the winner of
election method A; if there are candidates who pairwise beat
the winner of election method A then the winner of election
method B is chosen arbitrarily from those candidates who
pairwise beat the winner of election method A. Therefore
Steve's claim is circular reasoning.

(For example, I define the following election method B: If
there is no BCM winner who pairwise beats the IBCM winner then
the winner of election method B is the IBCM winner. If there
is an BCM winner who pairwise beats the IBCM winner then the
winner of election method B is that BCM winner who pairwise
beats the IBCM winner with the largest surplus. The winner
of this method pairwise beats the IBCM winner more often than
vice versa and therefore election method B is -due to Steve's
claim- better than the IBCM method.)

Another problem of Steve's claim that the IBCM winner pairwise
beats the Schulze winner more often than vice versa is the fact
that his claim is based on the unrealistic presumption that
the voters vote randomly. My observation that the IBCM winner
usually depends on more elements of the pairwise matrix than
the Schulze winner is not based on this unrealistic presumption.

******

Steve wrote (17 May 2000):
> It seems pretty clear to me that in numerous recent messages, 
> Markus Schulze has been desperately trying to dodge the issue 
> (whether his claim that his voting method is better than Tideman 
> is reasonable or not) by making quite a few false claims and 
> unwarranted attacks on my character.
> 
> After Markus' February 28 message ("Re: Tideman and GMC"), I 
> received some private email from EM subscribers commenting on 
> the nasty tone of that message.  A few weeks ago Mike Ossipoff 
> felt moved to publicly scold Markus for continuing to do more of 
> the same.  Markus' recent messages appear to me to be more of 
> the same.
> 
> I have confidence in the ability of EM subscribers to recognize 
> the antisocial quality of his tactics.  However, in case I've 
> misunderstood what Markus has been saying, or in case I've made 
> errors in my arguments, I hope some subscribers (other than 
> Markus, of course) will take the time let me know.

(1) Steve claimed that his IBCM method meets monotonicity. In so
far as his IBCM method is a successive elimination method, it is
automatically suspected of violating monotonicity. Therefore
I asked Steve to demonstrate that his IBCM method meets
monotonicity.

(2) Steve claimed that he has found an example "showing the
Schulze method preferred a candidate even though no voter
preferred it to the Tideman winner which beat it pairwise."
I asked him to repost this example. But that example that Steve
reposted was impossible. Therefore I told Steve that this example
was impossible.

If Steve believes that my behaviour is "asocial" then I have to
answer: Even if somebody else claims that a given election
method meets a given criterion I will -if this claim isn't
obviously true- ask him for a heuristic or a proof. Even if
somebody else uses an impossible example to demonstrate a
violation of a given criterion I will tell him that this example
is impossible.

(By the way, I believe that the misunderstandings between Mike
and me were caused by the fact that I used "you" in the meaning
of "one" while Mike believed that I used "you" in the meaning
of "Mike" e.g. when I wrote: "Independently on whether you think
that a given property is important, you have to find a
mathematical formulation of this property to be able to discuss
it in a non-trivial manner." or "Actually, Alternative Voting
violates participation. But to be able to check this, you have
to find a mathematical formulation of participation."
Actually, these were general statements and not a criticism of
a special person or a special criterion.)

******

Therefore, my main arguments against the IBCM method and
in favour of the Schulze method are:

(1) It is not clear that the IBCM method meets monotonicity.
(2) The IBCM method violates beat path GMC.
(3) The IBCM winner usually depends on more elements of the
    pairwise matrix than the Schulze winner.

It appears to me that Steve has failed to offer any
substantive criticism of my argument that IBCM appears to
be worse than Schulze. Since he didn't attempt to rebut my
argument, we can presume (until he rebuts it) that he can't.
Steve's flawed and fallacious argument in favour of his IBCM
method reminds me of Don Saari's argument that all criteria
failed by Borda, including manipulability, are failed by
other voting methods, so Borda is better because Borda
satisfies participation and reinforcement.

It is very strange that Steve -although he has proposed his
IBCM method more than two months ago- hasn't yet presented
a detailed analysis of his IBCM method. He hasn't yet
demonstrated that his method meets the claimed criteria,
he hasn't yet introduced an authoritative definition of his
method (e.g. for those situations where his method results
in a tie) and he hasn't yet presented an efficient algorithm
to calculate the winner of his method. This shows that Steve
isn't really interested in discussing his IBCM method
seriously.

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