Cloneproof tournaments
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
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@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
On 3/24/23 18:26, Forest Simmons wrote:
What if we just put the RP winner at good end of the agenda?
I'm pretty sure it can be done with SPE, because SPE eliminates one
candidate at a time. But it has to be a little more carefully designed
than this. Suppose A is the RP winner and we have a complex (e.g.
twisted prism) Smith set, then it's possible that whoever ends up next
to A beats A pairwise. But I think it's doable like this: suppose we
split the Smith set into A himself, everybody who beats A, and everybody
A beats. Call the latter two sets BeatsA and ABeats.
Then arrange the agenda so that all the BeatsA candidates come first
(closer to the start of the agenda), then someone in ABeats who beats
whoever it is that remains standing, then all the ABeats in some random
order, then A. Now you need to make sure that there exists someone in
ABeats who beats someone in BeatsA, and then you have to arrange the
order of BeatsA so that the "sacrificial candidate" comes last -- but
this seems to be doable through recursion.
Although remember the mathematician joke about the basket fire :-) I
haven't actually proven this.
The hard instance, though, that I was mentioning, is elimination
tournaments, which eliminates half the candidates every round (quarter
finals, semifinals, etc). This produces much less freedom to manipulate
the order to get A to win.
Large honest non-noisy Smith sets are completely unrealistic for
anything happening in practice, at least today, but a clone independence
proof would have to cover all the bases, even the unrealistic ones.
Otherwise there could be a technical clone dependence failure with a
Smith set of a thousand candidates all carefully arranged just so.
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.
That's right, so you're giving the SPE order from the good end to the
bad. Everything non-Smith dies to C, then B wins C vs B, then A wins B
vs A, got it. Here BeatsA is C and ABeats is B, so this follows my pattern.
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.
That's a good point, and I didn't see it. The ABeats candidate who beats
whoever remains in BeatsA can be transposed by one because the SPE
mechanism will compare two sequential candidates; but in this case, the
ABeats candidate must beat the BeatsA candidate just below him (one step
closer to the bad side) too. In an ABCA there aren't any more
candidates, so there's no additional BeatsA candidate to possibly jam up
the works.
Maybe you could recursively do something like this for all odd-size
Smith sets, given the parity point you make. But the following-the-cycle
idea should work? I think?
-km