Here's a fair-sequencing problem that doesn't quite match the usual fair-division problems. I think that, like those, the answer should also be the Thue-Morse sequence ("balanced alternation"), because the same heuristic reasoning that suggests it's the fairest way there works here as well, but the problem doesn't seem to reduce to them, so it's not obvious. (See here for more on using Thue-Morse for fair division, or this earlier MathOverflow question.)
Anyway, the problem is stage-striking (as is used in certain competitive video games for stage selection :) ). There are two players and $n+1$ objects ("stages"). The two players have different preferences regarding the stages (ideally, opposite preferences, but you'll see below why we don't assume that). The two players will take turns (in some order -- thus the question) removing ("striking") stages that have not already been struck; once only a single stage is left, that stage is selected (both players "get" it). The question, then, is what is the fairest order for stage striking; as mentioned above, I suspect it should be Thue-Morse (one player strikes on 0, the other player strikes on 1), for similar reasons that this is the answer to the old problem of what order to take turns in for fair division.
Of course this raises the question of how we're formalizing this and what we mean by "fair". I'll present here the formalization of the problem that (after discussing this with some other people) I think is best, but answers to other ways of formalizing it would also be OK so long as they don't trivialize the problem.
So -- note that if the players assign the stages opposite values (i.e. they agree about which stages give how much of an advantage to who), as you would expect, then the striking order becomes irrelevant, so long as both players get the same number of strikes; regardless of order, the median stage will be selected. So instead we have to assume the players may disagree about which stages advantage who. Also, since we can only really deal with the order of the stages here, we won't allow them to have arbitrary numeric values as in the fair-division problem; rather we'll assume each player assigns the $n+1$ stages the values $0, 1, \ldots, n$, so that the value of a stage to a player depends only on where it falls in their preference ordering.
Now, since perfect information makes the problem trivial, we'll go all the way in the opposite direction -- each player's preferences are uniformly random; or rather, each player sees the other's preferences as uniformly random. What we want to compare, then, and to make as equal as possible, is the expected value that player 1 gets (when player 2 strikes randomly), vs the expected value that player 2 gets (when player 1 strikes randomly).
(I'm pretty sure that, in this formulation, we can assume that each player always strikes their least-preferred stage at each step, and that there is no advantage from deviating from this. But obviously correct me if I'm wrong there...)
So, for instance, in this model, if $n=2$, then the first player to strike gets an expected value of $3/2$ (they eliminate their least preferred stage and get one of the remaining two at random), while the second player to strike gets an expected value of $5/3$ (they have a $2/3$ chance their most-preferred stage is not eliminated, and a $1/3$ chance they have to settle for the median). So we get a difference of $1/6$. You see?
So the question then is, is the Thue-Morse striking order the fairest? Or is it something else? Is it at least the fairest when $n$ is a power of $2$, even if it might not be otherwise?
EDIT: Actually, a thought -- maybe it should be reverse Thue-Morse? (As in, if $n=12$, you would go $011001101001$ rather than $011010011001$; you just reverse the sequence, and then, if necessary, swap the roles of the players so as to start with a $0$.) This seems possible because here it's going later, rather than going earlier, that seems to confer an advantage. Of course, if $n$ is a power of two, this distinction is irrelevant, as reversing the sequence would merely swap the roles of the players.
