Hallo, Tideman suggests to take successively the strongest pairwise defeat XY and to lock it in its original direction X > Y if it does not create a directed cycle with already locked pairwise defeats and in its opposite direction Y > X otherwise. The winner of Tideman's ranked pairs method is candidate Z with Z > W for every other candidate W.
Therefore, the first step of Tideman's ranked pairs method is to rank the N*(N-1) pairwise defeats according to their strength in a decreasing order. A problem occurs when there are pairwise defeats of equal strength. A frequently proposed way to circumvent this problem is to calculate a "Tie-Breaking Ranking of the Candidates" (TBRC) and to use this TBRC to rank pairwise defeats of otherwise equal strength. For example, this TBRC could be created as follows: a) Pick a random ballot and use its rankings; consider ties as unsorted with regard to each other. b) Continue picking ballots randomly from those that have not yet been picked. When you find one that orders previously unsorted candidates, use the ballot to sort them. Do not change the order of the already sorted. c) If you go through all ballots, and some candidates are still not sorted, order them randomly. Suppose "TBRC[i]" is the position of candidate i in this TBRC. Then "TBRC[i] < TBRC[j]" means "candidate i is ranked higher than candidate j in the TBRC". Many different ways to use this TBRC to rank pairwise defeats of otherwise equal strength have been proposed. ************* Thomas Zavist suggested that when ij and mn have the same strength then ij should be ranked higher than mn if and only if one of the following conditions is met: 1) min { TBRC[i], TBRC[j] } < min { TBRC[m], TBRC[n] }. 2) min { TBRC[i], TBRC[j] } = min { TBRC[m], TBRC[n] } and max { TBRC[i], TBRC[j] } < max { TBRC[m], TBRC[n] }. The problem of Zavist's tie-breaking strategy is that it violates monotonicity. ************* Blake Cretney suggested that when ij and mn have the same strength then ij should be ranked higher than mn if and only if one of the following conditions is met: 1) TBRC[i] < TBRC[m]. 2) i = m and TBRC[n] < TBRC[j]. So when the TBRC is ABCDEFG then pairwise defeats of otherwise equal strength are sorted: AG, AF, AE, AD, AC, AB, BG, BF, BE, BD, BC, BA, CG, CF, CE, CD, CB, CA, DG, DF, DE, DC, DB, DA, EG, EF, ED, EC, EB, EA, FG, FE, FD, FC, FB, FA, GF, GE, GD, GC, GB, GA. Blake Cretney explains his tie-breaking strategy as follows (22 Feb 2001): > If you have two pairs of equal margin, you take the one whose > winner is higher in the tie-breaking ranking first. He also > suggests that where the winner is the same, you can order by > loser. However, this is unnecessary, as pairs with the same > winner can be processed in arbitrary order without affecting > the result. Blake Cretney's tie-breaking strategy is also promoted by Xavier Mora under the name "natural tie-breaking": http://mat.uab.es/~xmora/articles/iss2Aen.pdf ************* Rob LeGrand suggested that when ij and mn have the same strength then ij should be ranked higher than mn if and only if one of the following conditions is met: 1) TBRC[n] < TBRC[j]. 2) j = n and TBRC[i] < TBRC[m]. So when the TBRC is ABCDEFG then pairwise defeats of otherwise equal strength are sorted: AG, BG, CG, DG, EG, FG, AF, BF, CF, DF, EF, GF, AE, BE, CE, DE, FE, GE, AD, BD, CD, ED, FD, GD, AC, BC, DC, EC, FC, GC, AB, CB, DB, EB, FB, GB, BA, CA, DA, EA, FA, GA. Rob LeGrand explains his tie-breaking strategy as follows (27 Sep 2001): > I realized, when a pairwise victory is locked, it usually > hurts the loser much more than it helps the winner. So it > seems more logical to order the pairs by loser than by > winner. For example, if the tiebreaking ranking were A>B>C>D, > I would lock a C>D before a B>A of equal margin. In my > implementation, I gather together all the pairs (that are > individually consistent with the locked pairs so far) with > the highest margin that hasn't been locked or skipped. Of > all the losers in that group, I pick the one lowest in the > tiebreaking ranking, then I lock at once all the pairs in > the group with that loser, which never causes a contradiction. Later (29 Sep 2001), Blake Cretney introduced the term "TBRC-lower" for Rob LeGrand's tie-breaking strategy. Rob LeGrand's tie-breaking strategy is also promoted by Steve Eppley: http://www.alumni.caltech.edu/~seppley ************* In my opinion, a problem of Cretney's and LeGrand's tie-breaking strategies is that they sometimes rank a pairwise defeat that is in contradiction with the TBRC higher than a pairwise defeat (of otherwise equal strength) that is in accordance with the TBRC. Example 1: Suppose the TBRC is ABCD. Suppose BA and CD have the same strength. Then Cretney's tie-breaking strategy would rank BA higher than CD although BA is in contradiction with the TBRC and CD is in accordance with the TBRC. Example 2: Suppose the TBRC is ABCD. Suppose AB and DC have the same strength. Then LeGrand's tie-breaking strategy would rank DC higher than AB although DC is in contradiction with the TBRC and AB is in accordance with the TBRC. In my opinion, example 1 and example 2 are implausible. Therefore, to circumvent this problem, I propose the following two tie-breaking strategies Schulze(I) and Schulze(II). Schulze(I) is more like Cretney's tie-breaking strategy while Schulze(II) is more like LeGrand's one. Schulze(I): When ij and mn have the same strength then ij should be ranked higher than mn if and only if at least one of the following conditions is met: 1) TBRC[i] < TBRC[j] and TBRC[n] < TBRC[m]. 2) TBRC[i] < TBRC[j] and TBRC[m] < TBRC[n] and TBRC[i] < TBRC[m]. 3) TBRC[j] < TBRC[i] and TBRC[n] < TBRC[m] and TBRC[i] < TBRC[m]. 4) i = m and TBRC[n] < TBRC[j]. 5) j = n and TBRC[i] < TBRC[m]. So when the TBRC is ABCDEFG then pairwise defeats of otherwise equal strength are sorted: AG, AF, AE, AD, AC, AB, BG, BF, BE, BD, BC, CG, CF, CE, CD, DG, DF, DE, EG, EF, FG, BA, CB, CA, DC, DB, DA, ED, EC, EB, EA, FE, FD, FC, FB, FA, GF, GE, GD, GC, GB, GA. ************* Schulze(II): When ij and mn have the same strength then ij should be ranked higher than mn if and only if at least one of the following conditions is met: 1) TBRC[i] < TBRC[j] and TBRC[n] < TBRC[m]. 2) TBRC[i] < TBRC[j] and TBRC[m] < TBRC[n] and TBRC[n] < TBRC[j]. 3) TBRC[j] < TBRC[i] and TBRC[n] < TBRC[m] and TBRC[n] < TBRC[j]. 4) i = m and TBRC[n] < TBRC[j]. 5) j = n and TBRC[i] < TBRC[m]. So when the TBRC is ABCDEFG then pairwise defeats of otherwise equal strength are sorted: AG, BG, CG, DG, EG, FG, AF, BF, CF, DF, EF, AE, BE, CE, DE, AD, BD, CD, AC, BC, AB, GF, FE, GE, ED, FD, GD, DC, EC, FC, GC, CB, DB, EB, FB, GB, BA, CA, DA, EA, FA, GA. Markus Schulze ---- Election-methods mailing list - see http://electorama.com/em for list info