[EM] Cloneproof tournaments (and SPE)

[Kristofer Munsterhjelm]

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