[EM] An odd case for Ranked-Pairs

[Markus Schulze]

Dear Eric,

you wrote (14 Jan 2003):
> Would you care to point to the algorithm you used that
> would pick B:E as a kept-defeat.

There is no directed path from candidate E to candidate B
with a strength of 4 or more. Therefore, when Ranked Pairs is
being used and you get to that point where you have to decide
whether B > E (of strength 4) has to be locked or skipped, it
is clear that B > E has to be locked because locking B > E
cannot result in a directed cycle.

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.

Markus Schulze

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