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 ---- Election-methods mailing list - see http://electorama.com/em for list info