[EM] Immunization against Second Place Complaints

[Kevin Venzke]

Forest,

--- "Simmons, Forest" <simmonfo at up.edu> a écrit :
> MinMax Pairwise Opposition (MMPO) is an example of a method that satisfies the FBC, but fails
> Smith.  If we could immunize it against 2nd place complaints, then the resulting immunized
> method I(MMPO) would satisfy Smith, and therefore would not be as clone dependent as MMPO.
>
> Here's an attempt at this:
> 
> 1. For each alternative (i.e. candidate) X let X' denote the alternative that would (by this
> method applied recursively) win the election if alternative X were withdrawn from consideration.
> 
> 2. For each alternative X, if X is beaten pairwise by X', disqualify X.
> 
> 3. If step two would disqualify all alternatives, then disqualify none.
>  
> 4. Use MMPO to choose an alternative from among the undisqualified alternatives.

Let's give this a whirl... Take 49 A, 24 B, 27 C>B. The pairs of candidates
(X and X') are A and C, B and A, C and B.

In none of these pairs, is X defeated by X'.

So it would remain a BC tie.

Trying 20 ABCD, 20 BCAD, 20 CABD, 13 DABC, 13 DBCA, 13 DCAB:
Pairs are A B, B C, C A, D (tie among ABC). Only D is disqualified.

So it looks like Smith-efficiency works in this example...

> This immunizatin attempt will be successful if and only if step three turns out to be
> unnecessary.
>  
> In other words, the method I(MMPO) will be immune from second place complaints as long as there
> is always at least one disqualified alternaive to choose from.  But if there is a case in which
> all alternatives are disqualified, then any winner would be beaten by the second place
> alternative.
>  
> So the big question: is there always some X that is not beaten by X' ?
>  
> Perhaps this could be proven by induction.

I think in general (not just with MMPO), it must be false, just because there is
not necessarily any relationship between the mechanism you use to determine X' for 
each X, and the pairwise contest that ISPC cares about.

It might be possible to disprove the statement by crafting a method specifically
for that purpose.

Kevin Venzke



	

	
		
___________________________________________________________________________ 
Appel audio GRATUIT partout dans le monde avec le nouveau Yahoo! Messenger 
Téléchargez cette version sur http://fr.messenger.yahoo.com