[EM] Tideman and GMC

[Markus Schulze]

Dear Blake,

you wrote (23 Feb 2000):
> Tideman has an interesting property with regard to these
> rankings, as follows: If ballots are modified in agreement with
> Tideman's ranking, Tideman's ranking is unchanged.
>
> I define a change to be in "agreement" with a ranking iff for every X
> and Y, s.t. on some ballot X is moved from below to above Y, X must be
> above Y in the final ranking.
>
> The final ranking is the ranking provided by the method, as opposed
> to an individual ballot.
>
> To see why this is the case, consider an election after Tideman has
> been applied to the results.  Some victories between candidates have
> been locked, others have been skipped.  Every locked victory X over Y
> corresponds to X being ranked over Y, and vice versa.
>
> So, what changes in this result could occur?  Victories that were
> previously locked may be increased.  Victories that were skipped may
> be decreased.  The question is, can these changes affect which
> victories are locked or skipped, and therefore the final ranking.
>
> Consider each skipped victory in turn (from previous highest to
> lowest).  Assume that all previously skipped victories (if any) are
> still skipped.  Since previously locked victories cannot have
> decreased, they must have been processed first. Are any skipped? 
> Since all locked victories are consistent, no previously locked
> victory can be responsible for one being skipped.  Since all
> previously skipped victories are still skipped, they cannot cause one
> to be skipped either.  We must therefore to conclude that they are all
> still locked.  The current victory must then still be skipped.
>
> Since no skip can be overturned without previous skips already
> overturned, the same victories must still be skipped.  It follows,
> therefore, that the same ranking results.
>
> ---
>
> Consider this rather complicated Schulze example.  I'm going to be using
> the +b notation I introduced in my previous email.
>
> 1 C D H I A B E F G J K L
> ... some other ballots
>
> A>B b+21
> B>J b+22
> J>A b+20
> B>I b+101
> D>K b+10
> K>C b+12
> C>D b+9
> H>I b+8
> I>L b+11
> L>H b+13
> F>G b+24
> G>E b+25
> E>F b+23
> G>D b+100
> G>H b+16
> D>E b+15
>
> I apologize for the mess, and hope I didn't leave anything out.  All other
> victories are assumed to be less than the ones given.
>
> In Schulze, the winner is A.  The critical victories are C>D and H>I. 
> Schulze ranks D over C, and I over H.
>
> However, by modifying the separated ballot in keeping with this ranking, by
> changing it to
> 1 D C I H A B E F G J K L
> the winner changes to F.

Remember that there are 479,001,600 possibilities to rank 12 candidates.
Usually there will be not a single voter who votes in agreement with the
Tideman ranking. And even if there was a single voter who votes in agreement
with the Tideman ranking, there is no reason why this single voter should be
so important that this demonstrates an advantage of the Tideman method.

You wrote (24 Feb 2000):
> Markus Schulze wrote (3 Feb 2000):
> > 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.

For this situation, I would recommend neither the Tideman method nor
the Schulze method. I would recommend a method that guarantees some
degree of proportional representation.

You wrote (24 Feb 2000):
> Markus Schulze wrote (3 Feb 2000): 
> > Blake Cretney 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.

You'll have to rephrase this, because I have no idea what you mean.
What do you mean when you say that Schulze was less likely to be affected
by strategical truncation but that didn't mean that truncation is a more
useful strategy in Tideman?

Example: What does "Generalized Independence from Clones" mean?
(a) Does it mean that you are never rewarded and sometimes punished
for nominating a large number of clones? (b) Does it mean that you are
never punished and sometimes rewarded for nominating a large
number of clones? (c) Does it mean that you cannot affect the result
of the elections by nominating a large number of clones?
The answer is (c), because if a large number of similar candidates is
nominated we usually don't know whether this is done to help or to hurt
these candidates. We usually don't know the true opinion of the
nominator. Therefore we cannot ask that this nominator should be
rewarded resp. punished. We can only ask that this nominator should
have no effect.

Therefore it is clear that GMC usually means that truncation has no
effect on the election result. The reason: If a given voter truncates his
vote, then we only know that this voter truncates his vote. Therefore we
can only ask that this truncation should have no effect on the election
result. As we can only see that this voter truncates and we don't know how
this voter whould have voted if he hadn't truncated, we cannot ask that
this voter should be punished.

By the way: How do you know that the truncators are punished in my Tideman
bad example? I haven't made any presumptions about the sincere preferences
of the truncators in my Tideman bad example.

You wrote (24 Feb 2000):
> Markus Schulze wrote (3 Feb 2000):
> > 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.

That isn't true. If you want to calculate the Tideman winner then you cannot
simply lock the strongest pairwise victories successively. You also always
have to check whether this pairwise victory creates a directed cycle with
the already locked pairwise victories. And that means that you always have
to check whether there is a ranking that is compatible to all locked
pairwise victories.

On the one hand: You cannot simply guess the Tideman winner and verify
whether this guess is correct. If the guess is correct, then verifying whether
this guess is correct is always identical with calculating the Tideman winner.

On the other hand: You can simply guess the Schulze winner and verifying
whether this guess is correct by calculating all the beat paths from this
guessed winner to all the other candidates and from all the other candidates
to this guessed winner. And you don't have to worry whether this guess is
compatible with some rankings that meet some criteria.

Already this fact demonstrates that the Tideman winner usually depends on
more pairwise defeats than the Schulze winner.

You wrote (24 Feb 2000):
> Markus Schulze wrote (3 Feb 2000):
> > Blake Cretney 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.

It is a big problem that you don't consider this kind of strategic voting.

All Condorcet methods are vulnerable by burying and compromising.
And it seems to me that the Condorcet methods don't differ significantly
in how much they are vulnerable by burying or compromising. But the
Condorcet methods differ _significantly_ in how much they are
vulnerable by the above described strategy. Example: The MinMax
method isn't vulnerable at all by this strategy.

Also I claim that the Schulze method is less vulnerable by this strategy
than the Tideman method. The reason: The Schulze winner depends on
fewer pairwise defeats than the Tideman winner. (I am only speaking about
the winners because -to my opinion- the task of an election method is to
find the best guess for best _candidate_ and not the best guess for best
_ranking_.) The Schulze winner depends only on the critical arcs of the
beat paths while the Tideman winner depends on all arcs. This is
caused by the fact that in the Tideman method the other arcs decide
which critical arcs are locked and which critical arcs are skipped.

In other words:

   Suppose that candidate A is the Schulze winner. Suppose that S(B)
   is the set of all arcs that are critical is the beat path from candidate A
   to candidate B or in the beat path from candidate B to candidate A.

   Then there are only two possibilities to change the Schulze winner
   from candidate A to candidate B with the above mentioned strategy:

   (1) The set S(B) has to be changed. That means: Other arcs become
   critical in the beat path from candidate A to canddate B or in the
   beat path from candidate B to candidate A.

   (2) The strength of a critical arc has to be changed.

In short: 

    If you want to use the above mentioned strategy to change the Schulze
    winner from candidate A to candidate B then you have to vote in such a
    way that other arcs become critical or the strengths of critical arcs are
    changed.

This is not true for the Tideman method.

You wrote (24 Feb 2000):
> Markus Schulze wrote (3 Feb 2000):
> > 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.

The arc B:D is a critical arc neither in the beat path from candidate A to
candidate C nor in the beat path from candidate C to candidate A.
Therefore the Schulze winner doesn't depend on the strength of this arc.
But the Tideman winner does depend on the strength of this arc because
in the Tideman method the strength of this arc decides which of the
weaker arcs is locked resp. skipped.

You wrote (24 Feb 2000):
> 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.

Both methods (= Tideman and Schulze) minimize the maximum pairwise
defeat that has to be ignored to get a complete ranking.

Can you give me an example where the maximum pairwise defeat that has
been ignored by the Tideman method to get a complete ranking is strictly
weaker than the maximum pairwise defeat that has been ignored by the
Schulze method to get a complete ranking?

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