[EM] Tideman and GMC

[Steve Eppley]

Markus S wrote:
> Dear Steve, you wrote (9 May 2000):
> -snip-
> > For reference, here's the Feb 3 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
> >     8 voters vote:  B>D>C>A
> >     7 voters vote:  D>A>C>B
> >     7 voters vote:  B>D>(A=C)
> >        ==>  Majorities:  BD75, CB65, DC60, AD58, AB51, CA48
-snip-
> > Markus claimed, if I haven't misinterpreted him, that the 
> > example shows Tideman is more manipulable than Schulze, by 
> > pointing out that some of the voters who prefer B to D and A to 
> > C (the 20 "B>D>A>C" voters) can change the Tideman outcome from 
> > C to A by not ranking B ahead of D (since that would reduce the 
> > BD majority to 59 or smaller so DC60 would get locked in).
> >
> > What Markus apparently neglected to notice is that voters can 
> > easily manipulate Schulze in this scenario too, to change the 
> > Schulze winner from A to C.  Some of the voters who prefer C 
> > to A and A to D (the 26 "C>A>B>D" voters and the 14 "C>B>A>D" 
> > voters) can uprank D ahead of A or downrank A behind D, which 
> > would reverse the A>D majority to D>A.  Since the ADC58 beatpath 
> > depends on the A>D majority, the ADC58 beatpath would be 
> > destroyed and Schulze would elect C.
> -snip-
> 
> 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.

Doesn't any beatpath involving 4 or more candidates (e.g.,  
ADCB) include at least one pairing of two candidates which are 
not the two at the ends of the beatpath (e.g., DC)?  The 
strengths of beatpaths in the Schulze method may depend on those 
"unrelated" pairings.  

So what is the criterion for deciding when it is "necessary" to 
depend on them?

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

I've seen the word "unnecessarily" used here before, as in:

   "If candidate x beats candidate y pairwise, then y shouldn't
   unnecessarily be elected."

In my opinion, this criterion is more important.  Since C beats 
A pairwise in the example, and it is unnecessary to elect A 
(since both A&C are in the BCM "minimal defense" set), this 
criterion suggests that A be defeated.  Both majoritarian 
Tideman and IBCM (a.k.a. DCD) will do this.

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.

As I wrote in February, criteria such as this one suggest that 
the Schulze criterion is too strong.

> You now say that the voters can change the Schulze winner from
> candidate A to candidate C by ranking candidate A behind D.
> But it is a difference, whether you can -in the Schulze
> method- make a candidate lose the elections by ranking this
> candidate insincerely low resp. make a candidate win the
> elections by ranking this candidate insincerely high or
> whether you can -in the Tideman method- change the winner
> from one candidate to another candidate by ranking two
> completely different candidates insincerely.
> 
> The difference is:
> 
> (a) _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?

> But the Condorcet methods differ extremely in how much they
> are vulnerable by the other mentioned strategy [=changing
> the winner from candidate X to Y by ranking two completely
> different candidates V:W insincerely.] Example: The MinMax
> method isn't vulnerable at all by this strategy.
> 
> Therefore, I proposed that the manipulability (by voting
> insincerely) of a Condorcet method should be measured by
> how much it is vulnerable by the other mentioned strategy.

In my opinion, that's a bad idea.  The example above shows that 
Schulze can be manipulated too, and suggests that Schulze is 
sensitive to a less drastic misrepresentation of preferences 
(reversing their least preferred and next-to-least preferred 
candidates) and gains more (the election of their favorite) for 
the manipulators than the manipulation in Tideman & IBCM.  Yet 
Markus suggests we utterly neglect the possibility of Schulze's 
manipulability when we compare manipulability.

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.

> (b) It can be argued that -in the Schulze method- if some
> voters uprank D ahead of A or downrank A behind D then
> this means that candidate A becomes less popular and that
> it is therefore legitimate when candidate A loses the
> elections.

That's a flawed argument.  Candidate A is not really less 
popular; it merely appears that way if one trusts the sincerity 
of the votes.

> 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.  
A similar problem arises trying to explain why a winner should 
be changed from x to y when z is added to the ballot.  I suspect 
it would be similarly difficult to argue why A should be elected 
since C beats A pairwise.

But my main point is that it is a serious mistake to consider 
the Schulze method less manipulable than Tideman or IBCM.  
And perhaps a careful analysis would show that Schulze is more 
manipulable, assuming we can agree on a good way to measure 
vulnerability to manipulation.


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