[EM] Tideman and GMC

Sat Mar 11 22:36:01 PST 2000

Dear Markus,

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

My point was, that one would expect that changes that are strictly in support of a given ranking should not overthrow it, in the same sense that changes strictly in support of a given candidate should not overthrow that candidate.

Of course, by denying that Schulze's method is intended for full rankings, this loses some of its force.  However, I see the fact that the same principles used to find the Schulze winner are not to be trusted to find a complete ranking is a defect, rather than an asset of Schulze's 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.

Using a majoritarian rather than a proportional method does have some advantages in this case.  It ensures that there will be some consistency between the candidates running for the same party, and it reduces the ability for parties and groups to "raid" the list.  I think that the parties themselves would prefer Schulze or Tideman to a PR system, for these reasons.  

In particular, parties may find it embarassing to have certain ideologies represented in their slate.  If you have a party with a membership of which 10% are basically racist, then in a majoritarian method, the 90% can keep them out.  In a proportional system, this 10% will get on the list, and monopolize news coverage for the party.  Parties are likely to find they win more seats if they use a majoritarian system for choosing their list.

What I envision is different factions within a party drawing up their own lists, hopefully with a great deal of overlap.  Then, each party member would vote for one faction's list.  Each individual's vote would be tabulated as if they ranked all the candidates on their ballot in the way described by their chosen faction.  Tideman's method would then determine the resultant combined ranking.

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

I mean that Schulze and Tideman are equivalent for reward, but Tideman is more likely to punish.

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

But we can't guarantee within a Condorcet method that truncation will have no effect.
Do you mean,
"GMC is usually defined so that truncation has no effect"
or
"Adherence to GMC implies that truncation will usually have no effect"?

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

This is addressed by one of the Tideman bad-examples you gave.

Here's the example you gave:
> 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.

> 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.
>
> Tideman would elect candidate C.
> But it is possible that candidate A is a SASW and candidate C is no SASW
> and it is not possible that candidate A is no SASW and candidate C is a
> SASW. Therefore rather candidate A than candidate C should be elected.

The only possible truncators are the B>D>A=C voters.
If their true preference was B>D>C>A, then C would also have won if they voted sincerely, so the truncation had no effect.  If their sincere preference is
B>D>A>C, then if the truncation causes C to be elected instead of A, they have been punished.

So, if this example represents a result changed through truncation, it shows truncators being punished.  So, presumably it is possible to ensure that truncators are punished without knowing their sincere preferences.

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

I see a distinction, however, between saying that it is necessary to find the complete ranking, and saying that it is necessary to verify that some such ranking is possible.

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

I don't find your argument convincing, but after trying large numbers of examples, I have come to believe your conclusion, that Tideman usually relies on more contests than Schulze.

That this offers greater opportunities for strategy seems doubtful to me.  It is more important how often opportunities for strategy occur, than how many different pairwise contests can be used to change a result.

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

If I understand you correctly, that is true, but it isn't my point.

What I am saying is, if all you know is that A is preferred to B,
1.  Which method is more likely to rank A over B?

The answer is Tideman.  The reason is that Tideman only over-rules a majority (does not place it in the final ranking) when this is necessary to honour higher majorities (by placing them in the final ranking).

That is, in Tideman, if a majority decision cannot be honoured in the final ranking, it isn't used at all.  This ensures that it does not over-rule a lower ranking that still can be honoured.  As a result, more majority decisions find their way into the final ranking.

This is why, as has been pointed out, the Tideman winner usually pairwise defeats the Schulze winner, when they are different.  I don't use that argument itself in favour of Tideman, however, because it is always possible to construct a method that tends to pairwise defeat any other method.

1.  Find the CW (based on the votes).  If the CW exists, elect it.  Otherwise go on to step 2.
2.  Find the winner of the original method.
3.  Elect the candidate by which the original winner is most defeated.

---

If we consider the A vs. B contest as direct evidence for which is better, and all other contests as indirect evidence, we have the following surprising result.  Tideman tends to be affected less by indirect evidence, but by more contests providing indirect evidence.  Schulze is more affected by indirect evidence, but by fewer contests providing it.

---

Here is another interesting point.  If one starts from a pairwise matrix with no cells equal, Tideman guarantees a complete ranking.  Schulze does not.

A>D b+2
A>B b+7
C>D b+6
C>A b+9
B>C b+5
D>B b+8

In this example, the best path from A to D is equal to the best path from D to A, because they share the B>C contest.

---
Blake Cretney