Hi again, I wrote: > Unfortunately, I fear Short Ranked Pairs might not be monotonic. One > would habe to check. And I'm not sure your description of an algorithm > for Short Ranked Pairs is valid -- after all, I only defined it > abstractly by saying that one has to find the "lexicographically maximal > short acyclic set" without giving an algorithm to find it.
Maybe my gut-feeling was incorrect. Short Ranked Pairs is probably monotonic. As it is also clone-proof and uncovered, we really have a third type of method with those three properties, just as Kristofer remarked! Now why should it be monotonic? Assume that... s(x,y) is the strength of the defeat x>y, s1>s2>s3... is the descending sequence of all defeat strengths, x1>y1,x2>y2,x3>y3,... are the corresponding defeats, D is the lexicographically maximal short acyclic set of defeats, w is the top option of D and I is the set of ranks i of defeats in the above numbering that belong to D, so that D = { xi>yi : i in I }. Then no defeat x>w is in D, hence all defeats w>y are in D since otherwise adding them won't construct a cycle. Now assume some defeat w>a is reinforced, moving it up in the ordering x1>y1,x2>y2,x3>y3,... by one place. Let j be the index of w>a in this list before the reinforcing, so that w=xj, a=yj. Also introduce a new numbering of the defeats corresponding to the new ranking of defeats: x'1>y'1,x'2>y'2,x'3>y'3,... Then x'i=xi and y'i=yi for all i different from j and j-1, and x'j=x(j-1), y'j=y(j-1), x'(j-1)=xj=w, y'(j-1)=yj=a. D consists of those defeats x'i>y'i with ranks i in the new set J = I with j and j-1 exchanged. We will prove that after the reinforcing, D is still lexicographically maximal. Assume that it is not. Then there is another short acyclic set of defeats D' that is lexicographically larger than D in the new ranking of defeats. Hence there is some new rank k such that the defeat x'k>y'k is in D' but not in D, and such that for all i<k, the defeat x'i>y'i is either in both D' and D or in neither of the two. If k were different from j-1, then D' would be already lexicographically larger than D in the original ranking of defeats, which was not the case as D was maximal there. But k can't be j-1 since the defeat x'(j-1)>y'(j-1) is the defeat w>a and thus belongs to D. Hence there is no such D' as assumed, D is still lexicographically maximal, and w is still the winner after the reinforcement of the defeat w>a. That is, Short Ranked Pairs is monotonic. > I propose to proceed as follows: Check how that lexicographically > maximal short acyclic set can be found in the simpler case in which we > define defeat strength as approval of defeating option. This is still open and I don't see a simple algorithm coming to my mind... > This will also > allow us to compare the method to DMC since DMC is the result of > applying ordinary Ranked Pairs with this definition of defeat strength, > so applying Short Ranked Pairs to them should not be too much different. > > The resulting short acyclic set will contain all defeats from the > approval winner to other options, but I don't see immediately whether > one can somehow continue to lock in defeats similar to ordinary Ranked > Pairs, skipping certain defeats that would destroy the defining > properties of a short acyclic set. I somehow doubt that since that > defining property is not that some configurations must not exist but > than some configurations must exist. Anyway, in the case where defeat > strength is approval of defeating option, all might be somewhat simpler. > > Jobst > > > >> >> >> I also guess you could make methods with properties like the above by >> constraining monotone cloneproof methods to the Landau set (whether by >> making something like Landau,Schulze or Landau/Schulze). I'm not sure of >> that, however, particularly not in the X/Y case since the elimination >> could lead to unwanted effects. >> >> Is one of the two methods you mention UncAAO generalized? >> ---- >> Election-Methods mailing list - see http://electorama.com/em for list info > ---- > Election-Methods mailing list - see http://electorama.com/em for list info ---- Election-Methods mailing list - see http://electorama.com/em for list info