[EM] Tideman and GMC

[Steve Eppley]

Markus S wrote:
> Dear Steve, you 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.)

A crucial item left unspecified in Mike's example is the set of 
voters' rankings which can produce his six given majorities.  
It's not clear to me that the example can actually occur.  As I 
recall, Mike posted a message saying Bruce Anderson had claimed 
and proved that any set of pairings can be reached through at 
least one set of voters' rankings, but I haven't seen Bruce's 
claim or proof.  Maybe Bruce claimed only that any set of 
*margins* can be reached.

It seems to me that the following must hold:

   For all distinct alternatives x and y, let x#y denote
   the number of voters who ranked x strictly ahead of y.

   For all distinct alternatives x, y, and z, x#y - x#z <= z#y.

In Mike's example, C#B=0, so if my conjecture is correct, 
D#B - D#C cannot exceed 0.  But D#B=10 and D#C<2, so either the 
example is impossible or my conjecture is incorrect.

For the record, Mike no longer believes the example shows a 
problem with Tideman.

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

> ******
> You wrote (11 May 2000):
> > Markus wrote (10 May 2000):
> > > _Every_ Condorcet method can be manipulated by burying
> > > [=lower a candidate with respect to sincere placement in the
> > > hopes of defeating it] and compromising [=raise a candidate
> > > with respect to sincere placement in the hopes of electing
> > > it]. Actually, the Condorcet methods don't differ in how
> > > much they are vulnerable by burying and compromising.
> >
> > How is that vulnerability measured?
> 
> Blake Cretney introduced "burying" and "compromising" and
> claimed that he can measure the vulnerability. I asked him for
> further details but he didn't answer.

One should avoid repeating a claim one doesn't understand.

> ******
> You wrote (11 May 2000):
> > The example above shows that Schulze can be manipulated too.
> 
> Every acceptable election method can be manipulated.

We all agree on this.  

Markus has snipped my sentence out of context.  The context of 
my message was that Schulze appears at least as manipulable as 
MTM and IBCM (a.k.a. DCD).  Since he didn't attempt to rebut my 
argument, we can presume (until he rebuts it) that he can't.  
Readers will have to look up my argument in my previous message 
however, because Markus avoided copying any of its substance 
into his reply.

> ******
> You 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?
-snip-

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.

> Condorcet is not a cult. It is not blasphemy to say that
> Condorcet methods are not perfect. Is it?

Since we are discussing which of a small subset of Condorcet-
consistent methods is best, I don't understand Markus' point.

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

Markus used MinMax as his "counter-example" since he couldn't 
justifiably claim that the paradox in question will never occur 
given the Schulze method.

* *

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.  Even that argument is dubious, for 
several reasons:  

1. The same paradox Markus complains about in Tideman also can 
occur in Schulze, since Schulze's outcome can also depend on 
pairings of "unrelated" candidates (since beatpaths can be 
sequences longer than 3 alternatives).  

2. 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.)

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

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

Lest Markus misunderstand (the way he has shown himself prone to 
misunderstand, since he is overly sensitive to criticism of his 
namesake method): I'm not saying the Schulze method is a bad 
method.  I consider it one of the best methods, not THE best but 
close to it.  And for the record, though Markus accused me in 
February of hating him, that's utterly false.


---Steve     (Steve Eppley    seppley at alumni.caltech.edu)