[EM] Cloneproof tournaments

[Kristofer Munsterhjelm]

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