[EM] Tie-Breaking Strategies for Tideman's Ranked Pairs Method

[Markus Schulze]

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