[EM] A Comparison of the Two Known Monotone, Clone Free Methods for Electing Uncovered Alternatives

[Jobst Heitzig]

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