# What is the fairest order for stage-striking (and is it the Thue-Morse sequence)?

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.

• Wait, how exactly does perfect information make the problem trivial? Consider the two-player p.i. game where each player has a set of $n+1$ stage values (known to both) and strike out stages in some order (also known), and each tries to maximize their value for the last stage: are the optimal strategy and gain for each player obvious? It's not obvious to me! – Gro-Tsen Nov 28 '18 at 12:28
• – Richard Stanley Nov 28 '18 at 17:24

Just a remark : with your weights (0,...,n) you have an simple formula to calculate the expectation. $$v_1(1b_1b_2\cdots b_n)=1+v_1(b_1\cdots b_n)$$ $$v_1(0b_1b_2\cdots b_n)=\frac{1}{n+2}+\frac{n+3}{n+2}v_1(b_1 \cdots b_n)$$ Proof : Let us call $$Y$$ the value obtained by the first player with a sequence $$b_1 \cdots b_n$$. Now consider the same sequence where we add a digit at the beginning. We note $$\tilde{Y}$$ the new value of the first player.

If it is a $$1$$, the first player will erase the $$0$$ stack and we are reduce to the previous problem but with stack $$k+1$$ instead of $$k$$. and then $$\tilde{Y}=Y+1$$. And therefore

$$v_1(1b_1b_2\cdots b_n)=\mathbb{E}(\tilde{Y})=\mathbb{E}(Y)+1= v_1(b_1\cdots b_n)+1$$

If it is a 0, then the second player erase randomly one stack $$X$$. We are reduce to the previous problem but with stack $$k$$ if $$k and $$k+1$$ if $$k\geq X$$ instead of $$k$$. The rest of the game follow identically but at the end $$\tilde{Y}=Y$$ if $$X> Y$$ or $$\tilde{Y}=Y +1$$ if $$Y\geq X$$. Therefore $$\mathbb{E}(\tilde{Y})=\sum_{i=0}^{n}i\times\mathbb{P}(Y=i)\mathbb{P}(X>i)+(i+1)\times\mathbb{P}(Y=i)\mathbb{P}(X\leq i)$$ $$\mathbb{P}(X\leq i)=\frac{i+1}{n+2}$$and we have

$$\mathbb{E}(\tilde{Y})=\sum_{i=0}^{n}i\times\mathbb{P}(Y=i)+\mathbb{P}(Y=i)\frac{i+1}{n+2}$$ and then $$\mathbb{E}(\tilde{Y})=\frac{n+3}{n+2}\mathbb{E}(Y)+\frac{1}{n+2}$$ which can be written as $$\mathbb{E}(\tilde{Y}+1)=(\frac{n+3}{n+2})\mathbb{E}(Y+1)$$ Exemple : $$v(01101)+1=\frac{7}{6}\times(1+1+\frac{4}{3}\times 2)=\frac{98}{18}$$ so $$v(01101)=\frac{40}{9}$$ (as numerically calculated by Claude).

• I keep getting this wrong. Here is your great result in another form : $v_1(1 b_1b_2\dots b_n) = 1 + v_1(b_1b_2\dots b_n)$ and $v_1(0b_1b_2\dots b_n) = \frac{1}{n+2} + \frac{n+3}{n+2} v_1(b_1b_2\dots b_n)$. – Claude Chaunier Nov 27 '18 at 20:46
• Oh, wonderful! With this, it's easy to compute; no need to program anything complicated. Can check possibilities much more easily. :) You may want to go back and clean this up, you seem to have gotten some things mixed up in the middle, but your statement in the comment I can certainly verify. – Harry Altman Nov 28 '18 at 5:25
• @Claude Chaunier yes that it (sorry I made the calculation on paper for weight = 1,2,...,n and I miss the 0)! Ok let me correct it. – RaphaelB4 Nov 28 '18 at 8:45
• OK, Claude was first, but this is easily the most helpful answer, so I'm going to award this one the bounty! – Harry Altman Nov 30 '18 at 4:21
• I agree, this gives some structure to the problem :) – Claude Chaunier Nov 30 '18 at 12:11

Here are the fairest sequences with $$v_0\ge v_1$$ for small $$n =$$ $$1,$$ $$2,$$ $$\dots,$$ $$14$$, according to an exhaustive search, where $$v_b$$ denotes the expected score for the player who can choose when the binary digit is $$b$$.

The reverse Thue-Morse sequence do look better than the Thue-Morse sequence but its score is far from the fairest. The Thue-Morse sequence looks like alternating between being worse and better than the simple alternating sequence. Their scores are tabulated farther below for $$1 \le n \le 17$$.

EDIT: RaphaelB4 formula allows fast computation and might lead to some other theorems. Harry also asked for the number of fairest sequences. Here they are (with $$v_0\ge v_1$$) for $$n$$ up to $$28$$. I don't see any pattern in them. The value $$222$$ for $$n=23$$ is striking.

$$\begin{array}{c r*{27}} n&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\ \#&1&1&1&1&1&4&1&6&1&6&1&6&1&18&1\\ \end{array}$$

$$\begin{array}{c r*{27}} n&16&17&18&19&20&21&22&23&24&25&26&27&28\\ \#&124&2&11&2&18&1&9&222&2&3&1&72&3\\ \end{array}$$

$$\begin{array}{rccccc} n&\text{fairest with }v_0\ge v_1&v_0&v_1&v_0-v_1&\text{approx.}\\ \hline 2&10&5/3&3/2&1/6&0.16666\,66667\\ 3&001&5/2&7/3&1/6&0.16666\,66667\\ 4&0110&10/3&16/5&2/15&0.13333\,33333\\ 5&11010&62/15&33/8&1/120&0.00833\,33333\\ \\ 6&000011&5&5&0&0.00000\,00000\\ &001110&5&5\\ &110001&5&5\\ &111100&5&5\\ \\ 7&1000101&377/64&88/15&23/960&0.02395\,83333\\ \\ 8&00110110&61/9&27/4&1/36&0.02777\,77778\\ &10000011&61/9&27/4\\ &10001110&61/9&27/4\\ &10110001&61/9&27/4\\ &10111100&61/9&27/4\\ &11110010&61/9&27/4\\ \\ 9&011000101&245/32&574/75&7/2400&0.00291\,66667\\ \\ 10&0100110110&77/9&94/11&1/99&0.01010\,10101\\ &0110000011&77/9&94/11\\ &0110001110&77/9&94/11\\ &0110110001&77/9&94/11\\ &0110111100&77/9&94/11\\ &0111110010&77/9&94/11\\ \\ 11&00101101001&3309/350&8417/891&2369/311850&0.00759\,66009\\ \\ 12&101000001101 &1481/143 &559/54 &37/7722&0.00479\,15048\\ &101001000011 &1481/143 &559/54 \\ &101001001110 &1481/143 &559/54 \\ &101001110001 &1481/143 &559/54 \\ &101001111100 &1481/143 &559/54 \\ &101011001001 &1481/143 &559/54 \\ \\ 13&0110100111010 &2534/225 &13873/1232 &463/277200&0.00167\,02742\\ \\ 14& 00001010010011 & 1205/99 & 426/35 & 1/3465 & 0.00028\,86003\\ & 00001010011110 & 1205/99 & 426/35 \\ & 00111000110110 & 1205/99 & 426/35 \\ & 00111010000011 & 1205/99 & 426/35 \\ & 00111010001110 & 1205/99 & 426/35 \\ & 01111010011010 & 1205/99 & 426/35 \\ & 00111010110001 & 1205/99 & 426/35 \\ & 00111010111100 & 1205/99 & 426/35 \\ & 00111011110010 & 1205/99 & 426/35 \\ & 10001010010101 & 1205/99 & 426/35 \\ & 10001011010110 & 1205/99 & 426/35 \\ & 10111010000101 & 1205/99 & 426/35 \\ & 11111000010110 & 1205/99 & 426/35 \\ & 11111010010001 & 1205/99 & 426/35 \\ & 11111010011100 & 1205/99 & 426/35 \\ & 10111011000110 & 1205/99 & 426/35 \\ & 11111011010010 & 1205/99 & 426/35 \\ & 10111011110100 & 1205/99 & 426/35 \\ \end{array}$$

$$\begin{array}{rlccr} n&\text{Thue-Morse}&v_0&v_1&v_0-v_1 \text{ approx.}\\ \hline 1 & 0 & 1 & 1/2 & 0.50000\,00000 \\ 2 & 01 & 3/2 & 5/3 & -1.66666\,66667 \\ 3 & 011 & 2 & 11/4 & -0.75000\,00000 \\ 4 & 0110 & 10/3 & 16/5 & 0.13333\,33333 \\ 5 & 01101 & 15/4 & 40/9 & -0.69444\,44444 \\ 6 & 011010 & 77/15 & 34/7 & 0.27619\,04762 \\ 7 & 0110100 & 19/3 & 53/10 & 1.03333\,33333 \\ 8 & 01101001 & 234/35 & 554/81 & -0.15379\,18871 \\ 9 & 011010011 & 85/12 & 284/35 & -1.03095\,23810 \\ 10 & 0110100110 & 1639/189 & 1853/220 & 0.24923\,03992 \\ 11 & 01101001100 & 399/40 & 712/81 & 1.18487\,65432 \\ 12 & 011010011001 & 338/33 & 136/13 & -0.21911\,42191 \\ 13 & 0110100110010 & 1582/135 & 6599/616 & 1.00585\,61809 \\ 14 & 01101001100101 & 23955/2002 & 75109/6075 & -0.39808\,69336 \\ 15 & 011010011001011 & 86/7 & 713/52 & -1.42582\,41758 \\ 16 & 0110100110010110 & 44540/3159 & 127340/9163 & 0.20220\,33021 \\ 17 & 01101001100101101 & 2799/196 & 11260/729 & -1.16520\,39417 \\ \end{array}$$

$$\begin{array}{rrccr} n&\text{reverse Thue-Morse}&v_0&v_1&v_0-v_1 \text{ approx.}\\ \hline 1 & 0 & 1 & 1/2 & 0.50000\,00000 \\ 2 & 10 & 5/3 & 3/2 & 1.66666\,66667 \\ 3 & 110 & 7/3 & 5/2 & -1.66666\,66667 \\ 4 & 0110 & 10/3 & 16/5 & 0.13333\,33333 \\ 5 & 10110 & 73/18 & 21/5 & -0.14444\,44444 \\ 6 & 010110 & 91/18 & 173/35 & 0.11269\,84127 \\ 7 & 0010110 & 109/18 & 199/35 & 0.36984\,12698 \\ 8 & 10010110 & 554/81 & 234/35 & 0.15379\,18871 \\ 9 & 110010110 & 1235/162 & 269/35 & -0.06225\,74956 \\ 10 & 0110010110 & 1397/162 & 3263/385 & 0.14813\,21148 \\ 11 & 00110010110 & 1559/162 & 3567/385 & 0.35852\,17252 \\ 12 & 100110010110 & 10994/1053 & 3952/385 & 0.17571\,07090 \\ 13 & 0100110010110 & 12047/1053 & 11933/1078 & 0.37107\,24901 \\ 14 & 10100110010110 & 38761/3159 & 13011/1078 & 0.20044\,88751 \\ 15 & 110100110010110 & 41381/3159 & 14089/1078 & 0.02982\,52600 \\ 16 & 0110100110010110 & 44540/3159 & 127340/9163 & 0.20220\,33021 \\ 17 & 10110100110010110 & 849419/56862 & 136503/9163 & 0.04105\,87768 \\ \end{array}$$

$$\begin{array}{rlccr} n&\text{alternating}&v_0&v_1&v_0-v_1 \text{ approx.}\\ \hline 1 & 0 & 1 & 1/2 & 0.50000\,00000 \\ 2 & 01 & 3/2 & 5/3 & -0.16666\,66667 \\ 3 & 010 & 8/3 & 17/8 & 0.54166\,66667 \\ 4 & 0101 & 25/8 & 17/5 & -0.27500\,00000 \\ 5 & 01010 & 22/5 & 61/16 & 0.58750\,00000 \\ 6 & 010101 & 77/16 & 181/35 & -0.35892\,85714 \\ 7 & 0101010 & 216/35 & 709/128 & 0.63236\,60714 \\ 8 & 01010101 & 837/128 & 439/63 & -0.42919\,14683 \\ 9 & 010101010 & 502/63 & 1867/256 & 0.67528\,52183 \\ 10 & 0101010101 & 2123/256 & 2029/231 & -0.49058\,10335 \\ 11 & 01010101010 & 2260/231 & 9285/1024 & 0.71616\,69710 \\ 12 & 010101010101 & 10309/1024 & 4553/429 & -0.54567\,08006 \\ 13 & 0101010101010 & 4982/429 & 22237/2048 & 0.75514\,34568 \\ 14 & 01010101010101 & 24285/2048 & 80141/6435 & -0.59601\,36977 \\ 15 & 010101010101010 & 86576/6435 & 414893/32768 & 0.79239\,43129 \\ 16 & 0101010101010101 & 447661/32768 & 173867/12155 & -0.64262\,51278 \\ 17 & 01010101010101010 & 186022/12155 & 948703/65536 & 0.82809\,57089 \\ \end{array}$$

• Thanks! Heh, guess I should've tried brute-forcing before asking; oh well. Anyway, this is interesting. Doesn't match TM or reverse TM unless $n\le 4$, it seems; it looks a little closer to reverse though? (For $n=3$, it matches that, but I could've told you that.) There's an obvious followup question here, which is "Is this always unique for $n$ odd?" -- but that's clearly a separate question. Anyway, going to wait a day to see if other answers, otherwise I'll accept this, because this does seem to answer my question. Meanwhile going to play around with this some. :) – Harry Altman Nov 26 '18 at 6:02
• @HarryAlman You may wait a few more days as well. And I'll improve on brute-force. Any consecutive run of $k$ random strikes could easily take $k!$ times less time. And computing upper and lower bounds on the values to expect after some binary prefix might help ruling it out before trying to lengthen it. – Claude Chaunier Nov 26 '18 at 8:27
• Well, OK! If you're already planning to do more computation, do you mind if I ask you also: Just how close do Thue-Morse and reverse Thue-Morse come? Thanks! – Harry Altman Nov 27 '18 at 3:52
• ok, I'll do it. I wonder if other weights than $0,1,\dots,n$ makes the Thue-Morse the fairest. – Claude Chaunier Nov 27 '18 at 6:44
• The fairest difference for $n=16$ is $0$ as it is for $n=6$. What is the next such $n$ ? – Claude Chaunier Nov 27 '18 at 23:26

Here is a counter-intuitive result that gets us as far as possible from the Thue-Morse sequence. Infinitely many sequences which are alternating only once are among the fairest sequences of all. Their score differences are 0.

Let's use free-monoid notations and write $$1^40^2$$ for $$111100$$. Then

$$v_0(1^40^2) = v_1(1^40^2) = 5$$

$$v_0(1^{12}0^4) = v_1(1^{12}0^4) = 14$$

$$v_0(1^{24}0^6) = v_1(1^{24}0^6) = 27$$

$$v_0(1^{40}0^8) = v_1(1^{40}0^8) = 44$$

$$v_0(1^{60}0^{10}) = v_1(1^{60}0^{10}) = 65$$

$$v_0(1^{84}0^{12}) = v_1(1^{84}0^{12}) = 90$$

More generally,

$$v_0(1^{2k(k+1)}0^{2k}) = v_1(1^{2k(k+1)}0^{2k}) = k(2k+3)$$

for any integer $$k\ge 0$$.

EDIT: for exactly the same lengths $$n = 2k(k+2)$$ as above, there are perfectly fair sequences with as many $$0$$'s as $$1$$'s, provided you allow two alternations instead of only 1.

$$v_0(0^2 1^3 0) = v_1(0^2 1^3 0) = 5$$

$$v_0(0^6 1^8 0^2) = v_1(0^6 1^8 0^2) = 14$$

$$v_0(0^{12} 1^{15} 0^3) = v_1(0^{12} 1^{15} 0^3) = 27$$

$$v_0(0^{20} 1^{24} 0^4) = v_1(0^{20} 1^{24} 0^4) = 44$$

$$v_0(0^{30} 1^{35} 0^5) = v_1(0^{30} 1^{35} 0^5) = 65$$

$$v_0(0^{42} 1^{48} 0^6) = v_1(0^{42} 1^{48} 0^6) = 90$$

and more generally

$$v_0(0^{k(k+1)}1^{k(k+2)}0^k) = v_1(0^{k(k+1)}1^{k(k+2)}0^k) = k(2k+3)$$

for any integer $$k\ge 0$$.

$$Proof$$: As RaphaelB4 commented, his insight about the simple multiplicative form of his recursion, $$v_1(0b_1\dots b_n)+1 = \frac{n+3}{n+2}\left(v_1(b_1\dots b_n)+1\right)$$ iteratively yields $$v_1(0^{i}b_1\dots b_n)+1 = \frac{n+2+i}{n+2}(v_1(b_1\dots b_n)+1)$$ so that

$$v_0(1^{2k(k+1)}0^{2k}) + 1 = v_1(0^{2k(k+1)}1^{2k}) +1$$ $$= \frac{2k+2+2k(k+1)}{2k+2} (v_1(1^{2k})+1)$$ $$= (k+1) (2k+1) = k(2k+3) + 1$$

and

$$v_1(1^{2k(k+1)}0^{2k}) + 1 = 2k(k+1) + v_1(0^{2k})+1$$ $$= 2k(k+1) + \frac{0+2+2k}{0+2} = k(2k+3) + 1$$

which proves the first equality. The second equality with two alternations is similar. It is also easy to prove there isn't any other solutions with one or two alternations.

• Not only are those monotonic sequences of length $n = 2k(k+2)$ as fair as a sequence can ever get, but the score both players expect with them is asymptotically $n-o(n)$, leaving them both quite satisfied ! – Claude Chaunier Nov 28 '18 at 11:46
• Oh well, maybe most sequences score $n-o(n)$. That's something to check. – Claude Chaunier Nov 28 '18 at 11:52
• Hi Claude, your conjecture can be easily proved using that $v_1(0^k b_1...b_n)+1=\frac{n+2+k}{n+2}(v_1(b_1...b_n)+1)$ – RaphaelB4 Nov 28 '18 at 12:04
• Wow, thanks @RaphaelB4. I detailed your insightful one-line proof in the answer. – Claude Chaunier Nov 28 '18 at 13:49
• Also worth noting: The total $n$ in these cases is is $2(k+1)^2-2$. So for $n$ of the form $2(k^2-1)$, we get an optimal difference of $0$. Nice! – Harry Altman Nov 28 '18 at 22:25