EDIT: See further discussion of this question in this SSC thread, particularly this comment by uau. Based on this I decided to ask this MathOverflow question.
EDIT AGAIN: See this /r/smashbros post for a summary of my ultimate conclusions. (No pun intended. :P )
So here's a question I've been wondering about: The stage-striking problem. Partly "what's the answer", but also, how do we even formalize this?
The stage-striking problem comes from competitive Super Smash Bros (or platform fighters more generally). There, the first game of a match ("set", in their terminology, but what other people would call a "match") is played on a stage chosen by stage-striking. Unlike in a traditional fighting game, the stage matters, remember! Stage-striking means that there is a list of available starting stages, and the two players take turns -- in some order, not necessarily in strict alternation -- striking off stages they don't want to play on; the last stage left is the one the game is played on. So with an n-stage list, you strike n-1 stages.
The question then becomes, what is the fairest way to do stage-striking? With a 5-stage list, if we denote one player by 0 and the other by 1, it's done in the order 0110; one player strikes first and last, the other player strikes the two inbetween. But what about with an n-stage list?
I had basically assumed that the correct answer to this was to use the Thue-Morse sequence. I mean that's kind of the obvious generalization, right? In the problem of equitable sequencing -- you have n things that are to be divided up between two people, what's the fairest way to have them take turns choosing things -- there are indeed theorems to the effect that Thue-Morse is the right answer here (possibly after restricting to a set of items which is contested, on which the participants agree on the relative order of the values). So I assumed that would naturally transfer over to this context as well.
And I still suspect it does... but the problem is I realized that I don't actually know how to formalize the problem. After all, when dividing up items, each player might value the items differently, and importantly, you're trying to minimize the discrepancy between the sums of what each player chooses.
But the setting of the stage-striking problem is rather different. You don't get the sum of what you choose; you get the one thing that wasn't struck -- and importantly, when a stage is struck, it doesn't matter who struck it. In fact, if players agree on the relative order of the values of the stages ("value" here being in terms of how much of an advantage it gives to one player over the other), the order that they strike in will be irrelevant, because they'll always end up with the median stage regardless.
So it would seem that, unlike with the problem of fair division, here the interesting, contested case is when the players disagree on the relative order of the stages' values. But what would that mean? If both players have perfect information, they should agree; we have to assume some sort of imperfect information in order for this to make sense, and imperfect information is a pain in the butt to formalize. If instead we assume by fiat that the two players don't necessarily agree on the values, then we have the problem of, what does it even mean to choose fairly? What we want, I think, is for the result to be the median stage (or to maximize the probability of picking the median?), but if stages don't have "true" valuations, then what does it mean to pick the median? I think in order for this to make sense, there have to be true valuations for the stages, but the players have limited (but nonzero) information about them -- perhaps their valuations are a random perturbation of the real valuations? (This is probably easier to formalize if we assume cardinal valuations -- in which case we maybe want not "maximize the probability of picking the median" but rather "get the expected value as close as possible to the median" -- but could probably also be formalized for ordinal valuations.) Again, the players have to have some information about the real values, or the order is once again irrelevant.
(Actually, on that note -- what is a good probability distribution to use on Sn, to have permutations further from the identity to be less likely? Note that we care about the order here, not about being further from the identity on an abstract unordered set; swapping the first and last elements should be a higher distance from the identity than just swapping two adjacent elements. It's likely that the right notion of distance here is just the obvious thing, i.e., number of inversions, but it's not obvious.)
So, yeah, it looks like a mess. Thus the question -- is there any way to formalize the stage-striking problem, that results in a particular answer (up to swapping of the players), and not "the order is irrelevant"? And does the answer end up then being the Thue-Morse sequence?
Beats me, at the moment...
(I think the usual heuristic for why it should be Thue-Morse applies, though. So I do think it should be.)
EDIT: Actually, maybe it should be reverse Thue-Morse? Because going later, rather than earlier, gives an advantage? Not that this matters if n=2k+1.
EDIT AGAIN: See this /r/smashbros post for a summary of my ultimate conclusions. (No pun intended. :P )
So here's a question I've been wondering about: The stage-striking problem. Partly "what's the answer", but also, how do we even formalize this?
The stage-striking problem comes from competitive Super Smash Bros (or platform fighters more generally). There, the first game of a match ("set", in their terminology, but what other people would call a "match") is played on a stage chosen by stage-striking. Unlike in a traditional fighting game, the stage matters, remember! Stage-striking means that there is a list of available starting stages, and the two players take turns -- in some order, not necessarily in strict alternation -- striking off stages they don't want to play on; the last stage left is the one the game is played on. So with an n-stage list, you strike n-1 stages.
The question then becomes, what is the fairest way to do stage-striking? With a 5-stage list, if we denote one player by 0 and the other by 1, it's done in the order 0110; one player strikes first and last, the other player strikes the two inbetween. But what about with an n-stage list?
I had basically assumed that the correct answer to this was to use the Thue-Morse sequence. I mean that's kind of the obvious generalization, right? In the problem of equitable sequencing -- you have n things that are to be divided up between two people, what's the fairest way to have them take turns choosing things -- there are indeed theorems to the effect that Thue-Morse is the right answer here (possibly after restricting to a set of items which is contested, on which the participants agree on the relative order of the values). So I assumed that would naturally transfer over to this context as well.
And I still suspect it does... but the problem is I realized that I don't actually know how to formalize the problem. After all, when dividing up items, each player might value the items differently, and importantly, you're trying to minimize the discrepancy between the sums of what each player chooses.
But the setting of the stage-striking problem is rather different. You don't get the sum of what you choose; you get the one thing that wasn't struck -- and importantly, when a stage is struck, it doesn't matter who struck it. In fact, if players agree on the relative order of the values of the stages ("value" here being in terms of how much of an advantage it gives to one player over the other), the order that they strike in will be irrelevant, because they'll always end up with the median stage regardless.
So it would seem that, unlike with the problem of fair division, here the interesting, contested case is when the players disagree on the relative order of the stages' values. But what would that mean? If both players have perfect information, they should agree; we have to assume some sort of imperfect information in order for this to make sense, and imperfect information is a pain in the butt to formalize. If instead we assume by fiat that the two players don't necessarily agree on the values, then we have the problem of, what does it even mean to choose fairly? What we want, I think, is for the result to be the median stage (or to maximize the probability of picking the median?), but if stages don't have "true" valuations, then what does it mean to pick the median? I think in order for this to make sense, there have to be true valuations for the stages, but the players have limited (but nonzero) information about them -- perhaps their valuations are a random perturbation of the real valuations? (This is probably easier to formalize if we assume cardinal valuations -- in which case we maybe want not "maximize the probability of picking the median" but rather "get the expected value as close as possible to the median" -- but could probably also be formalized for ordinal valuations.) Again, the players have to have some information about the real values, or the order is once again irrelevant.
(Actually, on that note -- what is a good probability distribution to use on Sn, to have permutations further from the identity to be less likely? Note that we care about the order here, not about being further from the identity on an abstract unordered set; swapping the first and last elements should be a higher distance from the identity than just swapping two adjacent elements. It's likely that the right notion of distance here is just the obvious thing, i.e., number of inversions, but it's not obvious.)
So, yeah, it looks like a mess. Thus the question -- is there any way to formalize the stage-striking problem, that results in a particular answer (up to swapping of the players), and not "the order is irrelevant"? And does the answer end up then being the Thue-Morse sequence?
Beats me, at the moment...
(I think the usual heuristic for why it should be Thue-Morse applies, though. So I do think it should be.)
EDIT: Actually, maybe it should be reverse Thue-Morse? Because going later, rather than earlier, gives an advantage? Not that this matters if n=2k+1.
