[EM] strength vs. length: Short Ranked Pairs (SRP)

[Jobst Heitzig]

Some correction:

I defined SRP as follows:

> Definition: SHORT RANKED PAIRS (SRP)
> ------------------------------------
> Affirm the lexicographically maximal *short* acyclic subset of all defeats.
>
> Def.: SHORT ACYCLIC SET OF DEFEATS
> ----------------------------------
> An acyclic set of defeats is *short* if whenever a beatpath X>...>Y is
> affirmed, also a beatpath X>...>Y of length at most 2 is affirmed (that
> is, either the defeat X>Y or a beatpath X>Z>Y).

That doesn't work since a lexicographically maximal short acyclic subset as 
defined above need not have a unique top element. I missed that point since
a lexicographically maximal *general* acyclic subset *has* a unique top.
So, that requirement has to be put into the above definition, and in order to
guarantee cloneproofness, we even need to assure that there is also a unique
second, third, and so on. Hence the corrected definition is this:


Correct Def.: SHORT ACYCLIC SET OF DEFEATS
------------------------------------------
An acyclic set of defeats is *short* if for each pair of candidates X,Y,
some beatpath of length at most 2 is affirmed from X to Y or from Y to X.


With this definition, SRP constructs a social order with the property that
each candidate beats all later candidates either directly or via a single
other candidate. In particular, the winner is always uncovered (I conjecture
that the winner is even in the Banks set).

In order to prove that SRP is well-defined one has to show that there is at 
least one short acyclic subset of all defeats. This can be seen as follows:
Pick an arbitrary "pivot" candidate X. Let S1 be the set of all candidates 
defeated by X, and S2 the set of all other candidates (i.e., those defeating X).
Affirm all defeats between X and S1 and all between X and S2. Repeat the 
process inductively inside each of the two sets S1 and S2. The resulting set
of affirmed defeats is a short acyclic set. (By the way, if the pivot elements
are picked uniformly at random, this construction is equivalent to ROACC!)


Jobst


__________________________________________________________
Mit WEB.DE FreePhone mit hoechster Qualitaet ab 0 Ct./Min.
weltweit telefonieren! http://freephone.web.de/?mc=021201