[EM] Tideman Properties

[Blake Cretney]

I'm going to prove some interesting properties of Tideman's method, in
particular in comparison to Schulze's method.

Both methods can be interpreted in a natural way to supply a complete
ranking of the candidates.  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.

-------

Another Tideman property following from the first shown is that if another
ballot is added that ranks the candidates in the order already ranked by
Tideman, the ranking is unchanged.  I think my example above for Schulze shows
that this is not the case there, although I'd have to actually figure out that
complete ranking to be thorough.

-------

Recall that any change in keeping with the Tideman ranking doesn't alter the
ranking.  If a candidate is ranked first by Tideman, it can be modified to be
first on all ballots, without changing the total ranking.  Consider what would
then happen.  First off, a victory would be locked from this candidate against
all others.  Tideman would then proceed locking victories between the
remainders as if the first candidate did not exist.  So, you could remove this
candidate without having any effect on the ranking of the remainder.  By the
reverse argument, the same is true of the last ranked candidate (as Steve
Eppley recently pointed out).

So, for example,

A>B b+7
C>A b+8
B>C b+9
B>D b+3
D>A b+2
C>D b+4

The Schulze ranking is B>C>A>D.
Tideman B>C>D>A
Remove B,
Schulze C>D>A
note the change
Tideman C>D>A
The removed order for Schulze is B, C, D, A
and for Tideman is B, C, D, A
The successive removal in Tideman gives the complete Tideman ranking. 
Successive removal in Schulze is different than the Schulze ranking.

One way of responding might be that Schulze was not defined to give a
complete ranking, and that the successive removal of the Schulze winner is a
superior way of producing a complete ranking.  However, this violates reversal
symmetry.  Consider the reverse ballots,

B>A b+7
A>C b+8
C>B b+9
D>B b+3
A>D b+2
D>C b+4

Schulze winner, D
remove D, winner is A
remove A, winner is C
remove C, winner is B

So, successive removal originally gave B>C>D>A
The reverse gave D>A>C>B, which is not the reverse order

---
Blake Cretney