[EM] UncDMC

[Jobst Heitzig]

[private mail!]

Dear Forest,

seems promising. But I'm a bit sceptical concerning IPDA. Can you prove 
it?

Yours, Jobst

PS: Can we object anything to Mike's truncation examples?

> Here's a Monotone method (UncDMC) that chooses from the uncovered
> set, and always picks the DMC winner in the three candidate case:
>
> 1. List the candidates in approval order, highest to lowest, top to
> bottom.
>
> 2. Modify the list according to the following rule: as long as some
> candidate in the list is pairwise defeated by its immediate inferior
> in the list, swap the members of the highest such pair in the list.
>
> 3. Initialize a set S with the highest member of the modified list. 
> As long as no current member of S is uncovered, add to S the highest
> member of the modified list that covers each of the current members
> of S.
>
> 4.  The last candidate added to S is the winner.
>
> This UncDMC method is monotone, clone proof, independent from Pareto
> dominated alternatives, and independent from Smith dominated
> alternatives, and always picks from the uncovered set.
>
> If I am not mistaken, previously, the only known deterministic method
> to satisfy all of these criteria was Jobst's TACC.
>
> A careful comparison of UncDMC and TACC in the three candidate case
> would be helpful.
>
> The UncDMC winner is either the DMC winner or a candidate that covers
> the DMC winner.  In the three candidate case the DMC winner is always
> uncovered, so it is also the UncDMC winner.
>
> We ought to examine three candidate cases where DMC and TACC produce
> different winners.
>
> Now a proof of UncDMC's monotonicity:
>
> Suppose that the UncDMC winner X improves in approval or in pairwise
> defeats relative to the other candidates (which retain their same
> relative approvals and pairwise defeats relative to each other).
>
> Then X is still uncovered, X still covers all of the candidates that
> it covered before, and the part of the modified list above X is a
> subset (in the same order) of the part of the modified list that was
> above X before X's improvement.
>
> So X will still be the last member added to the set S, retaining the
> win.
>
> Thanks,
>
> Forest
> ----
> election-methods mailing list - see http://electorama.com/em for list
> info
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20070312/192baf53/attachment-0003.pgp>