On Sat, Dec 14, 2002 at 07:53:38PM -0500, Raul Miller wrote:
> I've not been able to prove, to my satisfaction, that "drop options
> which don't satisfy supermajority" satisfies monotonicity, but after
> simulating over a million elections I have not been able to find any
> cases where it fails to satisfy monotonicity.
Proof sketch: Suppose it doesn't. Then there's some series of votes
where the series of votes:
{ <A> }
<B> <C> x <D>
causes option x to win, but
{ <A> }
<B> x <C> <D>
cause some other option y to win. Clearly option x satisfies quorum and
supermajority in both cases: either the first class of votes are enough
to do this, or the default option is part of the block of options <D>,
and the block of votes <A> is one vote short of satisfying either quorum
or supermajority or both for option x. Likewise, option y must satisfy
quorum and supermajority in both cases for similar reasons.
Thus the result is equivalent to some other vote:
{ <A'> }
<B'> <C'> x <D'>
versus
{ <A'> }
<B'> x <C'> <D'>
where the options that didn't meet their quorum or supermajority have
been eliminated already, and CpSSD is applied. But that means we've got
an example where CpSSD is non-monotonic.
Which is to say drop-first-then-CpSSD is at least as monotonic as CpSSD.
Cheers,
aj
--
Anthony Towns <aj@humbug.org.au> <http://azure.humbug.org.au/~aj/>
I don't speak for anyone save myself. GPG signed mail preferred.
``Australian Linux Lovefest Heads West''
-- linux.conf.au, Perth W.A., 22nd-25th January 2003
Attachment:
pgp_7DTJvT9aw.pgp
Description: PGP signature