[EM] An odd case for Ranked-Pairs

[Markus Schulze]

Dear Eric,

Tideman's Ranked Pairs method has the property that when
candidate X pairwise beats candidate Y with the strength xy
and there is no directed path from candidate Y to candidate X
with a strength of at least xy then candidate X must be
ranked ahead of candidate Y in the final ranking (because
locking the pairwise defeat X > Y cannot create a directed
cycle). With this simple observation it is possible to exclude
in advance a large number of rankings.

Therefore, I suggest that when Ranked Pairs is being used then
you should at first calculate the beat paths from each candidate
to each other candidate and that you should lock in advance all
those pairwise defeats X > Y where (1) X pairwise beats Y and
(2) there is no directed path from candidate Y to candidate X
which is at least as strong as the pairwise defeat X > Y.

For example, you wrote (14 Jan 2003):
> The pairwise matrix is:
>
>    - 4 4 2 3 4
>    2 - 4 3 4 5
>    2 2 - 4 3 4
>    4 3 2 - 3 2
>    3 2 3 3 - 3
>    2 1 2 4 3 -

In your example the beat path defeats are:

     - 4 4 4 4 4
     4 - 4 4 4 5
     4 4 - 4 4 4
     4 4 4 - 4 4
     3 3 3 3 - 3
     4 4 4 4 4 -

Because of the considerations above, when Ranked Pairs is being
used then the defeats B > E and B > F can be locked in advance.

Markus Schulze

----
For more information about this list (subscribe, unsubscribe, FAQ, etc), 
please see http://www.eskimo.com/~robla/em