[EM] Cloneproof tournaments

[Forest Simmons]

What if we just put the RP winner at good end of the agenda?

Assuming the sequntial elimination starts at the bad end (as in SPE) it
works for any ABCA cycle ... so it must also work for any cycle of such
cycles, if not for the twisted prism ... which we should check.

For practical purposes the top cycle will not be as complicated as the
twisted prism.

Here's how the ABCA cycle works:

First note that SPE ignores the non Smith candidates.

If the agenda order of the top cycle is in the cyclic order like A>B>C,
then nothing from below C survives the encounter with C ... and the A>B>C
order is preserved.

If the agenda order is anti-cyclic ... like
A>C>B, everything before B is eliminated ... so the first Smith comparison
eliminates C ... leaving A>B, etc.

The way I think of it is in terms of bubble sorting. SPE is like the first
pass of bubble sorting from below. The bubble sort top will never change
after that pass.

Every order has even or odd parity relative to the cycle ... and every swap
changes the parity.  If the 3 member Smith set starts out with even parity
(zero swaps from the ABCA  cyclic beat order) it will stay that way because
bubble sorting swaps only Pairs out of pairwise order. If it starts out
with odd parity, the first swap will restore it to even parity ... so the
swapping never reaches the Smith candidate highest in the agenda order.

Does that make sense?

-Forest



On Fri, Mar 24, 2023, 6:16 AM Kristofer Munsterhjelm <km_elmet at t-online.de>
wrote:

> I got to thinking about whether it's possible to make a cloneproof
> elimination tournament-based voting method, and I thought I should start
> at the obvious (way too strong) formulation:
>
> Suppose that we let the seeding order be provided by some function f of
> the election. (This is cheating, but I'm trying to see if I can devise a
> cloneproof f; if I can't, then it definitely isn't cloneproof under
> normal conditions.)
>
> Then intuitively, the following should work: Let f be a seed order so
> that the Ranked Pairs winner wins. Then the tournament augmented with f
> is cloneproof because Ranked Pairs is, and the RP winner is made to
> always win. Of course, this treats the elimination tournament as a mere
> afterthought.
>
> But, to make this rigorous, I would have to show that for any Smith set
> candidate, it is possible to arrange a seeding order so that that
> candidate wins. This seems intuitively correct, but intuition isn't proof.
>
> So suppose that we have a Smith set of size 2^n. Then we have to show
> that it's possible to arrange the brackets so that we can make any half
> of the set drop out. My idea then would be something in the vein of:
> suppose A and B are in the Smith set and we need them to be eliminated.
> Then A and B can't be beating everybody else in the Smith set; otherwise
> those other candidates wouldn't be in the Smith set. So pair A with some
> X who beats A pairwise, and pair B with some Y who beats B pairwise.
>
> But the difficult part is that we can't ensure that X and Y are
> different candidates. Put differently, we would need to show that for
> any partition of the Smith set into two equal parts, it's possible to
> arrange the candidates in the first set so that the kth candidate in the
> first set beats the kth in the second. Is that always possible? I'm not
> actually sure! This sounds very demanding. So perhaps it isn't that
> easy... Suppose we have sets {ABC} and {DEF}, and it's possible, and the
> arrangement is "A beats D, B beats E, C beats F". Now consider the sets
> {ABF}, {DEC}. How could there still be a viable rearrangement since C
> beats F?
>
> Any ideas?
>
> (I'm leaving byes out of it for now.)
>
> -km
> ----
> Election-Methods mailing list - see https://electorama.com/em for list
> info
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20230324/4266cd5e/attachment.htm>