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
