[EM] Re: Markus' request

[Ted Stern]

On 17 Feb 2005 at 15:07 PST, Markus Schulze wrote:
> Dear Ted,
>
> Jobst Heitzig wrote (12 Jan 2005):
>> A set A is a covering set if each candidate x from outside
>> A is covered in A+{x}. In other words, if for each x from
>> outside A there is some y in A with y>x but no z in A
>> with x>z>y. The minimal covering set is the intersection
>> of all covering sets.
>
> Situation #1:
> (The defeats are sorted according to
> their strengths in a decreasing order.)
>
>   D > A
>   A > B
>   B > C
>   C > A
>   C > D
>   B > D
>
> Situation #2:
>
>   A > C
>   D > A
>   A > B
>   B > C
>   C > D
>   B > D
>
> If I understand this definition correctly, then the Dutta
> set is {A,B,C} in situation #1 and {A,B,D} in situation #2.
> Therefore, Dutta//MinMax chooses candidate A in situation #1
> and candidate D in situation #2 so that monotonicity is
> violated.
>
> Is everything correct?
>
> Markus Schulze

Yes, same example as you posted a few days ago.  You've nailed the problem --
Reducing to the uncovered set (or minimal uncovered set) is not monotonic.

I think Jobst's definition might need a bit of clarification.

As I understand it, A is a covering set iff for each y in A, x not in A,

        - y>x or y>w>x, w in A.

        - for each z not in A such that x>z,
          either y>z or y>w>z, where w is in A and w>x.

Perhaps Forest or Jobst can correct me if I've misinterpreted something.

Ted
-- 
Send real replies to
	ted stern at u dot washington dot edu

Frango ut patefaciam -- I so break that I may reveal