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

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}$$

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<X$ 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).

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.