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

[Xavier Mora]

Hello,

On jueves, mayo 20, 2004, at 22:38 Europe/Madrid, Markus Schulze wrote:

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

I agree: If we imagine the tie-breaking rule as asking for somebody's 
preferences as to which proposition should be given priority, certainly 
if he prefers A to B and C to D then he would like to give priority to 
adopting the proposition C>D before B>A, and A>B before C>D.

In spite of the problem that you are pointing out, both Cretney's rule 
and LeGrand's one (but not Zavist's) still have the property that if 
the TBRC is immune to majority complaits in the sense of Eppley (a 
stack in the terminology of Zavist and Tideman) then the final result 
is guaranteed to coincide exactly with the ranking TBRC. You can find a 
proof of this fact in my paper  
http://mat.uab.es/~xmora/articles/iss2Aen.pdf  (Theorem B.4.4 and 
Corollary B.4.5). Corollary B.4.5 is concerned with Cretney's rule, but 
what really matters is satisfying a certain condition (HS). and this 
condition is satisfied also by LeGrand's rule.

Having said that, I agree that the situation described in your examples 
is not desirable.

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

In plain words, Schulze(I) can be stated as follows: “Assume that we 
have a tie between several propositions. In order to decide which one 
to consider first, we apply successively the following criteria:  1. 
The propositions that agree with the TBRC are given priority before 
those that disagree with it.  2. When the preceding criterion does not 
decide, we identify the preferred item and the unpreferred item of each 
proposition, and we apply successively the following criteria:  2.1. 
That the preferred item be ranked better in the tie-breaker ranking;  
2.2. That the unpreferred item be ranked worse in the tie-breaker 
ranking.”

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

A description of Schulze(II) in plain words would be as above but 
interchanging 2.1 and 2.2.

Not surprisingly, Schulze(I) and Schuze(II) have also the property that 
the final result coincides with TBRC whenever the latter is immune to 
majority complaints. This is covered also by Theorem B.4.4 of my paper, 
where condition (HT) is the one relevant to this case.

On the other hand, Schulze(I) and Schuze(II) also share with Cretney 
and LeGrand the monotonicity property that I prove in my paper: if some 
of the input rankings, including the TBRC, are changed so as to promote 
a particular item  x  to a better rank, without affecting the relative 
ordering of the other items, then  x  will never be demoted to a worse 
rank in the final result. This property is guaranteed whenever the 
tie-breaker satisfies a condition (HM) which can be explained as 
follows:

A tie-breaking strategy is an ordering of the (ordered) pairs  ij  
which is used to choose between several paired-comparison propositions 
with the same score.  Let us denote by  H[ij]  the rank of the pair  ij 
  in that ordering.  If  ij  and  mn  have the same score, we shall give 
priority to the pair  ij  before  mn  whenever  H[ij] < H[mn].

Condition (HM): If TBRC[i] =< TBRC[m] and TBRC[j] >= TBRC[n] with at 
least one of the inequalities being strict, then H[ij] < H[mn].

This condition is satisfied by the tie-breaking rules of Cretney, 
LeGrand, Schulze(I) and Schulze(II), but not by Zavist's one.

************

So, the preceding results are not able to discriminate between the 
tie-breaking rules of Cretney, LeGrand, Schulze(I) and Schulze(II).

I've done a small computational exploration to see how often the final 
result of Schulze(I) differs from Cretney. With 4 items and 9 random 
rankings, the case of different results is relatively rare, once or 
twice every 10000. Here is one example:

1: a > d > c > b
1: b > a > c > d
1: c > a > d > b
1: c > b > a > d
2: c > d > b > a
2: d > a > b > c
1: d > b > a > c

scores =
	a	b	c	d
	----------------------
a	*	4	5	4
b	5	*	4	2
c	4	5	*	5
d	5	7	4	*

Results with a > b > c > d as TBRC:
Cretney = d > b > a > c
Schulze(I) = a > c > d > b

In this case Schulze(I) is *nearer* to the TBRC (2 inversions) than 
Cretney (4 inversions).

Anyway, I'm with you, Markus, that your proposals are more “natural” 
than Cretney's (which I called “natural” in my paper) and LeGrand. In 
fact, since my paper is still a preliminary draft I will consider 
seriously the possibility of adopting Schulze(I) instead of Cretney's 
rule.

Xavier Mora