# [EM] Tie-breaking for Ranked-Pairs and other methods

Stephane Rouillon stephane.rouillon at sympatico.ca
Tue Jan 14 11:12:17 PST 2003

```Eric --

I do not say it is easy to compute,
but your algorithm should try to minimize the
sum of violated pairwise-victory within all
the pairwise victories of the same strength.
For this example it leads to lock all 4:2 victories
except for D>A.
At least and I think it is what Mike sent previously,
you should identify B>E as not being part of any cycle
and thus lock it.

Now finding all cycles created by previous lock and
all current pairwise victory of the same strength is
easy. I dentifying the minimal number of arcs to remove
and which arcs to break all cycles might not.

But suppose you do and you end up stuck with
only pure cycles without overlap (A>B>C>A, all 7 to 3 victories)
I can suggest you a systematical and random tie-breaker.

The advantage of being random is obvious: it is necessary
for fairness reasons. The advantage of being systematical
is less known. It permits two computers to obtain the same
result from the same set of ballots. So you can use different computers
to count the ballots and they should always find the same result
even when ties occur. Good bye random tie-breaker ballot, welcome
computerized counting of the votes that can prevent fraud.

Steph.

Eric Gorr a écrit :

> This example was recently brought to my attention.  Consider:
>
>    A>C>B>F>D>E
>    B>C>E>F>D>A
>    D>B>A>F>E>C
>    E>A>B>C>F>D
>    E>D>A>B>C>F
>    F>C>D>A>B>E
>
> The pairwise matrix is:
>
>    0 4 4 2 3 4
>    2 0 4 3 4 5
>    2 2 0 4 3 4
>    4 3 2 0 3 2
>    3 2 3 3 0 3
>    2 1 2 4 3 0
>
> Now, with Ranked-Pairs, the only kept-defeat will be B:F.
>
> However, once all of the defeats have been considered, there will be
> no kept-defeats for <someone>:E, which allows E to participate in a
> tie (according to my computations).
>
> Now, the problem with this appears to be that E also does not have
> any pairwise-victories, which would seem to indicate that it should
> not have the opportunity to be selected as the victor.
>
> Now, it would seem to me that, in the case of a tie, I should verify
> that each option in the tie did have at least one pairwise-victory
> and if they did not, eliminate them from the tie.
>
> Would anyone else agree or have I made a mistake in here somewhere?
>
> ----