[EM] Tideman and GMC

[Markus Schulze]

Dear Steve,

you wrote (13 May 2000):
> Markus wrote (12 May 2000):
> > Steve wrote (11 May 2000):
> > > The older "Tideman fails GMC" example posted by Mike O was even
> > > more extreme, showing the Schulze method preferred a candidate
> > > even though no voter preferred it to the Tideman winner which
> > > beat it pairwise.
> > 
> > I don't remember that Mike posted an example where the Schulze
> > method chose a Pareto inferior candidate.
>
> If by "Pareto inferior" Markus means that all voters strictly
> prefer another candidate, Mike didn't.  Mike posted on 7-31-1998
> (subject "Tideman problem") the following 4-candidate example,
> in which a lot of voters are indifferent between B and C:
>
>    A beats D 12
>    B beats A 11
>    D beats B 10
>    C beats A  5
>    C beats D  2
>    B beats C  1
>
> Each number shown in the example is the number of voters who 
> ranked the pairwinner ahead of the pairloser.  Note that the BC1 
> pairing implies no voter ranked C ahead of B.
>
> The Schulze method calculates the "strongest beatpaths":
>
>    BA11  > ADB10   ==>  B finishes ahead of A.
>    CA5   > ADBC1   ==>  C finishes ahead of A.
>    AD12  > DBA10   ==>  A finishes ahead of D.
>    CADB5 > BC1     ==>  C finishes ahead of B.
>    BAD11 > DB10    ==>  B finishes ahead of D.
>    CAD5  > DBC1    ==>  C finishes ahead of D.
>
> So Schulze elects C even though no voter ranked C ahead of B. 
> B is the winner according to "majoritarian Tideman."  (A.k.a. 
> MTM, "Minimize Thwarted Majorities.  The social ranking BCAD 
> reverses only the DB10 majority, whereas CBAD reverses both the 
> DB10 majority and the BC1 majority.  Since B leads the "MTM-
> best" ranking BACD, MTM elects B.)

Your example is impossible. If no voter strictly prefers
candidate C to candidate B then it is not possible that
simultaneously candidate C wins against candidate D pairwise
and candidate B is beaten by candidate D pairwise.

******

You wrote (13 May 2000):
> Markus wrote (12 May 2000):
> > Steve wrote (11 May 2000):
> > > As I wrote in February, criteria such as this one suggest that 
> > > the Schulze criterion is too strong.
> > 
> > What do you mean with "Schulze criterion"?
>
> Sorry about the ambiguity.  In the message to which I was 
> replying, Markus wrote the following:
>
>    "What I criticize is that Tideman depends unnecessarily on the
>    strengths of too many pairwise defeats. In the example above,
>    whether candidate A or candidate C is the Tideman winner
>    depends on how many voters prefer candidate B to candidate D.
>    To my opinion, the strength of the pairwise defeat B:D
>    doesn't contain any information about whether candidate A
>    or candidate C is better.
>
>    "Therefore, to my opinion, whether candidate A or candidate C
>    is elected shouldn't depend unnecessarily on the strength of
>    the pairwise defeat B:D."
>
> That constitutes a vaguely worded criterion.  I'd be interested
> in seeing a rigorous wording.  I anticipate that the rigorous
> wording will resemble the following:
>
>    Alternative x must be defeated if there exists an alternative
>    y such that the strongest beatpath from y to x is stronger
>    than the strongest beatpath from x to y.

The main justification of the Schulze method is beat path GMC:

   "X >> Y" means that an absolute majority of the voters
   strictly prefers candidate X to candidate Y.
   "There is a majority beat path from X to Y" means that
   (1) X >> Y or 
   (2) there is a set of candidates C[1],...,C[n] with
       X >> C[1] >> ... >> C[n] >> Y.

   If there is a majority beat path from candidate A to
   candidate B and no majority beat path from candidate B
   to candidate A, then candidate B must not be elected.

If you want to call a criterion "Schulze criterion" then it
should be beat path GMC. In so far as Mike wrote that he
doesn't promote beat path GMC any more, this criterion has
become a orphan and needs a new father.

******

You wrote (13 May 2000):
> Markus wrote (12 May 2000):
> > Steve wrote (11 May 2000):
> > > Markus' argument 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.
> > 
> > Why does everybody believe that I promote the Borda method? It
> > is true that I introduced the participation criterion to this
> > list. It is true that I introduced to this list Moulin's proof
> > that the Condorcet criterion and the participation criterion
> > are incompatible. But the unique reason why I did this is that
> > if you are in a public discussion outside the internet then you
> > will have to know what to answer when you are confronted with
> > Moulin's proof.
>
> If Markus rereads my paragraph more carefully, he will notice 
> that I did NOT write anything which even remotely suggests he 
> promotes the Borda method. I was merely drawing an analogy 
> between Markus' promotion of the Schulze method and Saari's 
> promotion of Borda: Saari's fallacious argument in support of 
> Borda is analogous to Markus' fallacious argument in support 
> of Schulze.

The aim of my reply was to give you the possibility to
withdraw your polemic accusation without losing your
honour. Unfortunately, you didn't observe this.

******

You wrote (13 May 2000):
> Markus wrote (12 May 2000):
> > Steve wrote (11 May 2000):
> > > Markus wrote (10 May 2000):
> > > > But it is more difficult to argue why -in the Tideman
> > > > method- the winner should be changed from candidate C to
> > > > candidate A when some voters uprank B ahead of D or
> > > > downrank D behind B.
> > >
> > > It's another one of the paradoxes of voting, to which we
> > > should be accustomed, but which are hard to explain to the
> > > lay public.
> > 
> > That's not true. There are acceptable election methods that
> > cannot be manipulated by this strategy. Example: The MinMax
> > winner cannot be changed from candidate A to candidate B
> > by changing the strength of the pairwise defeat between two
> > completely different candidates X:Y. The MinMax method is a
> > very good method because it meets Condorcet, Monotonicity,
> > Positive Involvement and No Show. (Unfortunately, on the
> > other side the MinMax method violates Local Independence
> > from Irrelevant Alternatives, Independence from Clones and
> > Reversal Symmetry.)
>
> Markus misunderstood my point.  I didn't mean that any
> particular paradox can occur in every method.  I just meant
> that every method has at least one paradox which may be hard
> to explain to voters.

A "paradox of voting" is an unwanted property that every
acceptable election method has.

******

You wrote (13 May 2000):
> It appears to me that Markus has failed to offer any
> substantive criticism of my argument that Schulze appears
> at least as manipulable as methods like MTM and IBCM. His
> only argument still standing is that it may be harder to
> explain MTM or IBCM to the public than Schulze.

I don't remember that I said that the Schulze method was
less difficult to explain to the public.

******

You 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.  
> (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.)

The unique reason why I defined and analysed the Schulze method
in great detail is that I wanted to give every participant
of this list the possibility to implement this method and to
make computer simulations (e.g. with randomly generated voter
rankings).

You have to admit that (if you want to calculate the Tideman
winner in a polynomial time) the exact algorithm to calculate
the Tideman winner is also very long and abstract.

******

You 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.

This argument is problematic because it can be cyclic.

Suppose that somebody else would propose a new election method
and would demonstrate that the winner of his election method
beats pairwise the MTM winner more often than vice versa and
that the Schulze winner beats the winner of his election method
more often than vice versa. What would you conclude?

******

You wrote (13 May 2000):
> I think more people will accept the (vaguely worded) 
> criterion that when x beats y pairwise, y shouldn't 
> "unnecessarily" finish ahead of x, sooner than they will accept
> the (vaguely worded) criterion that the choice between x and y
> shouldn't "unnecessarily" depend on pairings between two other
> alternatives.

The main justification of the Schulze method is beat path GMC.
I don't agree with you that beat path GMC is "vaguely worded."

******

You wrote (13 May 2000):
> Markus wrote (13 May 2000):
> > Steve wrote (11 May 2000):
> > > The older "Tideman fails GMC" example posted by Mike O was even
> > > more extreme, showing the Schulze method preferred a candidate
> > > even though no voter preferred it to the Tideman winner which
> > > beat it pairwise.
> >
> > I couldn't find in the archives Mike's example where the Schulze
> > method chooses a Pareto inferior candidate. Could you please
> > repost this example?
>
> I didn't make that claim about Mike's example. See another
> message I just posted for the example in question.

There are two definitions of "Pareto inferior": a strong one and a
weak one.

"Candidate X is strongly Pareto inferior to candidate Y" means:
Every voter strictly prefers candidate Y to candidate X.

"Candidate X is weakly Pareto inferior to candidate Y" means:
No voter strictly prefers candidate X to candidate Y and at
least one voter strictly prefers candidate Y to candidate X.

You wrote that no voter preferred the Schulze winner to the
Tideman winner and that the Tideman winner beat the Schulze
winner pairwise. Therefore you wrote that the Schulze method
chose a weakly Pareto inferior candidate.

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