[EM] Tideman and GMC

[Blake Cretney]

Dear Markus,

> Steve Eppley wrote (9 Jun 1999):
> > When calculating the size of a pairwin, Cretney uses the pairwise
> > margin of victory. (Schulze uses the number of voters who ranked
> > the pairwinner ahead of the pairloser.) Blake made a philosophical
> > argument for preferring pairwise margins of victory, but I don't
> > find it more compelling than the philosophical argument for
> > preferring pairwise support (or call it opposition, depending on
> > which side you're on). More important than philosophical criteria,
> > in my opinion, are other criteria we usually use for comparing
> > voting methods.
> 
> I have to agree with Steve Eppley. It seems to me that you put too
> much emphasis on heuristics. It is true that on the one hand it is
> advantageous for campaign purposes to have a simple heuristic for
> a given election method. But on the other hand in the end only the
> properties of this election method are important. And if we look at
> the properties then the Schulze Method is superior to the Tideman
> Method in so far as there is no desirable criterion that is met by
> Tideman and that is not met by Schulze and there is at least one
> criterion that is met by Schulze and that is not met by Tideman and
> that is important to at least a few participants of this mailing
> list: Schulze guarantees that never unnecessarily a candidate is
> elected who is not in the sincere top set.

I think it is important to realize that we are really talking about
four methods here:  Schulze (margins), Schulze (winning-votes),
Tideman (margins), and Tideman (winning-votes).
It is possible to create criteria that favour margins over
winning-votes, or winning-votes over margins.  We differ on which
criteria are more desirable.

Comparing Tideman (m) to Schulze (m) or Tideman (wv) to Schulze (wv)
is much more difficult, as it is harder to come up with persuasive
criteria to differentiate them.  This is why I have used more
"heuristics".

> The problem of heuristics is that they usually contain many
> implicite presumptions. The most severe implicite presumption of
> Tideman's heuristic is the presumption that the task of an election
> method is to find the most probably best _ranking_ and not the most
> probably best _candidate_. 

Can you show that Tideman is based on this presumption and that
Schulze is not?

Let me suggest that we have good reason to believe that finding the
best ranking and finding the best candidate are linked.  Consider the
following example:

A>B 40+b
B>C 50+b
C>A 60+b
A,B,C>D 10+b

Note: I use b because according to my recent proof, this example must
exist for some b.

In the old days, it was argued that D was the least defeated and the
closest to being a Condorcet winner, and therefore should be the best
choice.  By choosing D we don't have to over-rule any of the three
highest pairwise majorities.  We can say that in some sense all three
of these highest majorities are being honoured.

It seems to me that a new way of looking at this example involves
noting that much as we would like to honour them all, the three
majorities A>B, B>C, and C>A cannot all be right.  Even though we can
avoid giving an explicit ranking, we know that one must exist, and
that this ranking must over-rule one of these majorities.  If we
realize that one has to be over-ruled anyway, the argument for
selecting D collapses.

In fact, I believe that the reason Schulze handles this example
correctly, is that it is also a ranking-finding method, even if this
was not your intent.

> To my opinion, Tideman's implicite
> presumption is not justifiable.  To my opinion, the parties and the
> voters are interested only in which candidate wins and they are not
> interested in which candidate gets which position in the ranking.

For most, but not all uses, that will be the case.  For example, a
party might want to use the method to sort a large number of their
candidate for use in list PR.

> ******
> 
> You wrote (31 Jan 2000):
> > What about
> >
> > 25 A D B C
> > 35 B A D C -> B
> > 30 D C A B
> > 4  A D C B
> > 6  C A D B
> >             winning-votes
> > A->D 35-30   35
> > A->B 65-35   65
> > C->A 36-29   36
> > B->C 60-40   60
> > D->B 65-35   65
> > D->C 59-6    59
> >
> > Here, A is in the SASW; D is not.  A wins in Tideman (winning-votes),
> > but D wins in Schulze.
> 
> I don't understand your example. What do you want to demonstrate with
> your example? Do you want to criticize the mathematical formulation of
> beat path GMC? Or do you want to criticize the Schulze Method?
> 
> First: The intention of beat path GMC is that a voter should rather be
> punished than rewarded for truncating his votes. In your example, beat
> path GMC does exactly what it was designed to do. Those 35 voters whose
> sincere opinion is B > A > D > C truncate their votes and change the
> winner from candidate A to candidate D. Thus the truncators are
> punished. In so far as beat path GMC does exactly what is was designed to
> do, your example cannot be interpreted as a criticism of beat path GMC.

But in your bad example for Tideman, the truncators were punished as
well.  It does seem, however, that Schulze converts some situations
where truncators are punished into situations where they have no
effect.  This may well be a positive effect.  I do, therefore, now see
the rationale for favouring Schulze (winning-votes) over Tideman
(winning-votes) as being slightly less likely to be affected by
truncation.  This doesn't mean that truncation is a more useful
strategy in Tideman (winning-votes), in fact it is worse.  

I hope I have helped to clarify the difference between Schulze (wv)
and Tideman (wv) with regard to truncation.  

-----
> The Tideman winner usually depends on more elements of the matrix of
> pairwise defeats than the Schulze Method. The reason: The Schulze
> Method tries to find the most probably best _candidate_ and not the
> most probably best _ranking_. 

Since I have no justification for believing the premise, that the Schulze
method differs from Tideman in only trying to find the best candidate, the
conclusion, that Tideman usually depends on more elements of the matrix, is
unsupported.

> Therefore very often it is possible to
> "guess" the Schulze winner and then -by calculating the beat paths
> from this guessed winner to every other candidate and from every
> other candidate to this guessed winner- to verify whether this guess
> is correct. On the other hand the Tideman Method tries to find the
> most probably best _ranking_ and not the most probably best _candidate_.
> Therefore if you want to calculate the Tideman winner you always have
> to calculate the complete Tideman ranking.

That isn't true.  As soon as all but one candidate has a pairwise
majority/victory locked against it, the remaining candidate is clearly the
Tideman winner, whether or not a complete ranking has been established.

Example,
A->B 30+b
A->C 20+b
B->C 10+b

Lock A over B
Lock A over C

A is the winner, but we do not yet know whether the complete ranking is
A B C or A C B

> 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
> 
> Tideman:
> 
>    Tideman would
>    1) lock B > D,
>    2) lock C > B,
>    3) skip D > C because it would create a directed cycle
>       with the other already locked pairwise defeats,
>    4) lock A > D,
>    5) lock A > B,
>    6) lock C > A.
> 
>    Thus the Tideman ranking is C > A > B > D and the Tideman
>    winner is candidate C.
> 
> Schulze:
> 
>    A has 58 votes against B via the beat path A > D > C > B.
>    A has 58 votes against C via the beat path A > D > C.
>    A has 58 votes against D via the beat path A > D.
> 
>    B has 48 votes against A via the beat path B > D > C > A.
>    B has 60 votes against C via the beat path B > D > C.
>    B has 75 votes against D via the beat path B > D.
> 
>    C has 48 votes against A via the beat path C > A.
>    C has 65 votes against B via the beat path C > B.
>    C has 65 votes against D via the beat path C > B > D.
> 
>    D has 48 votes against A via the beat path D > C > A.
>    D has 60 votes against B via the beat path D > C > B.
>    D has 60 votes against C via the beat path D > C.
> 
>    Candidate A is the Schulze winner because candidate A defeats
>    every other candidate via beat paths.
> 
> In the Schulze Method, the strength of the pairwise defeat B:D
> has no influence on the final winner; even if we set B:D=100:0
> or B:D=0:100, candidate A stays the Schulze winner. On the other
> hand, if we set B:D=59:41 then the Tideman winner is changed from
> candidate C to candidate A.
> 
> You seem to believe that the fact that the Tideman winner usually
> depends on more elements of the matrix of pairwise defeats is a
> selling point. 

Although it is clearly true that examples can be constructed in which Tideman
depends on more elements, I don't see a persuasive argument for why this
should be the case generally.

What I consider to be more important, however, is that Tideman is more likely
than Schulze to honour the result of an individual pairwise victory.  That is,
if a majority of those with a preference rank A over B, Tideman is more likely
to ensure that this is reflected in the final ranking, including the ranking
for first place.

To put it more precisely, Tideman over-rules a pairwise majority only if this
is necessary in order to honour a greater pairwise majority.  If it is unable
to honour it, it skips it.  This ensures that a majority that can't be
honoured does not end up over-ruling a majority that can, as can happen in
Schulze.

Consider your example.  In Schulze, A is the winner instead of C, despite the
fact that C has a pairwise majority over A.  The reason is simple, in Schulze,
it is easier to construct longer paths that over-rule direct comparisons. 
Here we have A>D>C over-ruling C>A.  In Tideman, the D>C victory is skipped,
so the more direct comparison decides between C and A.  Of course, if A had a
pairwise majority over C, then A would win in Tideman as well.

> I view this fact of Tideman to be the fatal flaw in
> this method. The reason: If the question whether candidate A or
> candidate C is elected unnecessarily depends on how many voters
> prefer candidate B to candidate D then it is possible to manipulate
> the result of the elections by ranking B respectively to
> candidate D insincerely.
> 
> In other words: If an election method should be as difficult as
> possible to manipulate then it should not only meet monotonicity,
> local independence from irrelevant alternatives, complete
> independence from clones, and beat path GMC, the result of the
> election method should also depend on as few irrelevant information
> as possible.

First, it isn't clear to me that strategy-resistance should be the only goal.
 It might well be that we would accept slightly greater strategic
possibilities, for slightly better results in the absence of strategy.  After
all, if we really saw strategy-resistance as the only goal, we would favour
random-ballot.

Second, it is not clear that Tideman is more open in general to the kind of
manipulation you suggest, although it is in the example you mention.

Third, you state that a method should rely on as little irrelevant
information as possible.  You claim that Schulze relies on as few pairwise
contests as possible.  These two are not necessarily the same.

Fourth, even if Tideman is more open to manipulation in the way you show, it
may be less open to manipulation in other ways.  In the example you give.

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

Tideman C, Schulze A

Now, what if we had the change
18 voters vote A > D > C > B -> A > C > D > B

C would now win in both.

If we change back,
18 A > C > D > B -> A > D > C > B

we have an example where Schulze is affected by burying, but Tideman is not.

> ******
> 
> You wrote (31 Jan 2000):
> > There are three major kinds of strategic voting (as far as I know).
> >
> > Burying-  Lower a candidate (with respect to sincere placement) in
> > the hopes of defeating it.  This is what SPC prevents.
> > Compromising- Raise a candidate in the hopes of electing it. This
> > is impossible to eradicate in a non-random method, but some methods
> > are more affected than others.
> > Push-over- Lower a candidate in the hopes of electing it.  This is
> > what monotonicity prevents.
> 
> Example 1:
> 
> Suppose that the sincere opinion of a given voter is A > B > C > D.
> Suppose that this given voter votes B > A > C > D to change the
> winner from D to C.
> 
> Example 2:
> 
> Suppose that the sincere opinion of a given voter is A > B > C > D.
> Suppose that this given voter votes A > C > B > D to change the
> winner from D to A.
> 
> Is this Burying, Compromising or Push-over?

None of the above.  When I wrote that, I was trying to list "major" kinds of
strategic voting.  Techniques that are frequently discussed, and seem somewhat
practical.  I must admit, I didn't even consider the kind of strategic voting
you mention here.
 
---
Blake Cretney