[Math] What’s the fairest turn sequence for n players

Question

For two players, in some sense, the fairest possible turn order is the Thue-Morse-sequence:

01101001100101101001011001101001....  

It arises by taking turns taking turns taking…, so:

01|01|01|01|01|01|01|01 ->  
01 10|01 10|01 10|01 10 ->  
01 10 10 01|01 10 10 01 ->  
01 10 10 01 10 01 01 10 ...

And, among many other nice properties, it happens to have the advantage the first player gets at turn 1 to converge away to 0 over time.
This idea, the fairness of a given turn-order, is my sole concern here.

Now there already is a question asking what the n-player generalization of the Thue-Morse-sequence is: https://math.stackexchange.com/a/1549434/49989
However, all it mentions is how to generate these generalized sequences. Not whether, or in what sense they share the same properites. For instance, from that answer, here is the 3-player variant:

0, 012, 012120201, 012120201120201012201012120

arrived at by starting with 0 and using the following replacement rules:

(0→012),(1→120),(2→201)

Since our set now contains 3 elements which can be arranged in 6 ways, there are, however, more sequences that might ultimately be equivalent. For instance, what about the following? Is it at a disadvantage over the sequence given by the answer above?

(0→021),(1→102),(2→210)
0, 021, 021210102, 021210102210102021102021210

As far as I can tell, no: All it effectively did was to switch around the players with the label 1 and 2 respectively, leaving alone 0.

However, if you can pick either sequence, you could once again go with a take turns taking turns approach:

(0→ 012|021 ),(1→ 120|102),(2→ 201|210)

Though at this point I'm not sure which variant to take here: Either you'd just take the thue-morse sequence per-step or per-digit to determine which one of the two to pic, or perhaps each digit should have its own thue-morse sequence attached to it to pick which one to go first. Here are the first couple steps in either case (these are hand-computed so hopefully I made no mistake):

thue-morse: 01101001100101101001011001101001...
3 player thue-morse per-step
0, 012, 021102210, 021210102102021210210102021,...
3 player thue-morse per-bit
0, 012, 012102210, 012102210120021210210120012,...
3 player thue-morse per-player
0, 012, 012120201, 012120201102210021210021102,...

So it's probably hard to tell from those sequences what exactly I did for each of them, so let's be a bit clearer:

• for per-step, I simply generated each partial sequence with the substitution rules where I alternated what rule to pick per step.
  0 -> 012 because the first bit of the thue-morse sequence is 0
  012 -> 021102210 because the second digit is 1
  021102210 -> 021210102102021210210102021 because the third bit is 1, the next step would go with the first rule set again since its bit is 0.

• for per-bit, I simply picked what rule to apply based on what digit we are looking at.
  0 is the first digit. The first digit in the Thue-Morse-sequence is 0. Therefore, use the 1st substitution rule: |0| -> |012|.
  1 is the second digit.
  The second digit in the Thue-Morse-sequence is 1. Therefore, use the 2nd substitution rule: 0|1|2 -> 012|102|.
  2 is the third digit.
  The third digit in the Thue-Morse sequence is 1. Therefore, use the 2nd substitution rule: 01|2|102 -> 012102|201|…

• for per-player I kept track of the occurrence of each digit individually, the 1st 0, 1, and 2 respectively would use the 1st substitution rule, the 2nd and 3rd (each corresponding to 1) the 2nd respectively, the 4th occurance the 1st again…

Though except for the 1st case, I didn't use the rule for substitution but rather as recursion, so I just tacked the next three digits to the end of the sequence based on the current digit and the current rule.

And perhaps there are other fairly natural rules (the most natural-seeming one to me is the per-digit rule)

Now, back to my question. As said, I'd like to know the fairest possible turn order for n players. Does the (comparatively simple) method in the answer I linked fulfill that criterion, or would that price go to a different sequence, perhaps one of my suggested alternatives? If the latter then I assume a similar generalization would have to be taken for higher player counts: For four players 0123 there could be six plausible substitution rules which could either be fixed or chosen in an alternating pattern that combines the best 3-player sequence and the thue-morse sequence. And in general, for $n$ players, the $\left(n-1\right)!$ choices of presumably fair sequences could all be shuffled up further for each of the n-1 fair sequences that come before them.

Answer 1

I have found an answer in the shape of an essentially brute-force Python 3 program I threw together. I will not accept my own answer because I'm hoping there are better takes on this, like a proper recursion or Lindenmayer system to quickly construct this solution. I am not entirely sure at this point, whether the resulting sequence generalizes Thue-Morse in all possible ways regarding "turn order fairness" but it at least does in one particular way:

• Say there are two players taking turns, each trying to be the first to score a point throwing basketballs through hoops.
• Both players have a low probability $\epsilon \approx 0$ of making the shot.
• Conversely, they have a chance of $1-\epsilon$ to miss.
• Acknowledging that a naive alternating turn order gives an unfair advantage to player 1, they decide on the following policy:
• Whoever currently is the "underdog", that is, they have a lower probability of winning the game, goes next.
• This, it turns out, gives the Thue-Morse-sequence of turns in the limit $\epsilon \to 0$.

Here is how it works:

The two players assign who may go first with a random coin flip. That person will be called player $A$, the other one player $B$. The current probability score for each player can be kept track of in a pair $(p_1, p_2)$. So after the first throw the score looks like this: $(\epsilon, 0)$.
Player $B$ has now become the underdog and gets the next turn. Since the game might already have ended, their winning probability is slightly lower though: $\left(\epsilon, \epsilon\left(1-\epsilon\right)\right) = \left(\epsilon, \epsilon-\epsilon^2\right)$
So at this point they still are the underdog and get to throw again: $\left(\epsilon, \epsilon\left(1-\epsilon+\left(1-\epsilon\right)^2\right)\right) = \left(\epsilon, 2\epsilon - 3\epsilon^2 + \epsilon^3\right)$.
At this point, since $\epsilon \approx 0$, $2\epsilon-3\epsilon^2$ will definitely be larger than $\epsilon$, so the next turn goes to player $A$ again. The turn order thus far was $A, B, B, A$ and if you keep following this process, you will generate the entire Thue-Morse sequence. (The referenced paper, however, mentions this other paper to construct a strictly fairer sequence. If I read it right, that sequence can't be easily constructed though. Unless somebody has further insight into this, I will stick with Thue-Morse for now.)

Here is the same algorithm now applied to three players. Initially, nobody has taken a turn. Since the turn order is determined by linear combinations of $(1-\epsilon)^n$ after $n$ turns, the matrix you see simply contains the (positive) integer coefficients if you expand the corresponding turn value. The top row denotes whether the column counts positively or negatively. We are always looking for the currently most disadvantaged player, so we are looking, from left to right, which player has the lowest winning probability. (Note, since I pulled out the sign to the top of the table, for negative columns we are looking for the maximum instead. Or just keep in mind that those values have a $-$ in front, then we are always minimizing.)

$$ \begin{matrix} & + \\ A & \mathbf{0} \\ B & 0 \\ C & 0 \end{matrix} $$

In a patt situation (As far as I could tell this only ever happens at the very beginning, but a proof of that would be nice), I give the first player the move. Below the matrix you can see the current sequence:

$$ \begin{matrix} & + \\ A & 1 \\ B & \mathbf{0} \\ C & 0 \end{matrix} \\ a $$

Higher turns require more columns for keeping track of everything:

$$ \begin{matrix} & + & - \\ A & 1 & 0 \\ B & 1 & 1 \\ C & \mathbf{0} & 0 \end{matrix} \\ ab $$

Let's jump ahead a little , to turn 6. The fat element denotes which element determines the next turn's player:

$$ \begin{matrix} & + & - & + & - & + & -\\ A & 2 & 5 & 10 & 10 & 5 & 1 \\ B & 2 & 5 & 6 & 4 & 1 & 0 \\ C & 2 & 5 & \mathbf{4} & 1 & 0 & 0 \end{matrix} \\ abccba $$

So the next turn goes to player $C$. Since they just got to play, this player now gets penalized with a term $(1-\epsilon)^6$ which will have coefficients according to $(-1)^k \begin{pmatrix} 6 \\ k \end{pmatrix}$, where $\begin{pmatrix} n \\ k \end{pmatrix}$ is the binomial coefficient, so, after adding another column to make room for all of the values, the following will be added to $C$'s row: $\begin{pmatrix}1 & 6 & 15 & 20 & 15 & 6 & 1\end{pmatrix}$, so:

$$\begin{matrix}& 2 & 5 & 4 & 1 & 0 & 0 & 0 \\ + &1 & 6 & 15 & 20 & 15 & 6 & 1 \\ \hline & 3 & 11 & 19 & 21 & 15 &6 & 1 \end{matrix}$$

The other two rows remain unchanged, save for the additional 0, so the next step would look like this:

$$ \begin{matrix} & + & - & + & - & + & - & +\\ A & 2 & 5 & 10 & 10 & 5 & 1 & 0 \\ B & 2 & 5 & \mathbf{6} & 4 & 1 & 0 & 0 \\ C & 3 & 11 & 19 & 21 & 15 &6 & 1 \end{matrix} \\ abccbac $$

and the next turn would go to b. This same basic idea can be applied to any number of players.

---

EDIT: I was externally asked to include some pseudo code. So there you go:

Definitions:

• Let ${n\choose k} = \frac{n!}{k!\left(n-k\right)!}$ be the usual binomial coefficient.
• Let ${\text{turn}_n}{\left(\tau\right)}$ be the $\tau^\text{th}$ turn in a game of $n$ players.
• Let ${P^\tau}{\left(\epsilon\right)}$ be the polynomial $\left(1-\epsilon\right)^\tau$, associated with turn $\tau$.
• Let $P_k^\tau$ be the $k^\text{th}$ coefficient of $P^\tau$: $\left(-1\right)^k {\tau \choose k}$.
• Let $_iP^\tau$ be the polynomial of the $i^\text{th}$ player.
• Let $_iP_k^\tau$ be the $k^\text{th}$ coefficient of $_iP^\tau$.

Initialize:

• $_iP^0 = 0$

for each turn $\tau$, do:

• find the player $i$ where the coefficient $_iP_0^\tau$ is minimal.
• If multiple qualify, discard the disqualified ones, and check the next coefficient $_iP_1^\tau$ of the remaining players, and so on.
• If a subset of players have the exact same associated polynomial $_iP^\tau$, arbitrarily pick the first one. (This will only happen initially and define the turn order.)
• ${\text{turn}_n}{\left(\tau\right)}=i$
• $_iP^{\tau+1} = {_iP^\tau} + P^\tau$
• $i$ here is only the minimal-coefficient player $i$ found before! Not all of them.

---

Next, here is a Python implementation (I'm sure there are plenty of ways to optimize this still, aside from just finding a proper recursion or substitution solution):

import functools
from itertools import count


@functools.lru_cache(maxsize=None)
def binomial_coeff(n, k):

    if n < 0:
        return 0
    if k > n // 2:
        return binomial_coeff(n, n - k)
    if k < 0:
        return 0
    if k == 0:
        return 1
    if k == 1:
        return n
    return binomial_coeff(n-1, k-1) + binomial_coeff(n-1, k)


def turns(player_count):
    # first n turns are always just the the players in standard order
    sequence = [turn for turn in range(player_count)]
    yield from sequence
    # setting up state to where it would be after first n turns plus some house keeping
    players = [[1, 0] for _ in range(player_count)]
    column_turn_number = [player_count, 1]
    column = 1
    sign = -1
    # once that's done, for every turn,
    for turn_number in count(player_count):
        # start with updating the current column to the most recent state
        for turn in range(column_turn_number[column], turn_number):
            players[sequence[turn]][column] += sign * binomial_coeff(turn, column)
            column_turn_number[column] += 1
        # then search for all occurrences of the minimum value in that column
        target_column = [player[column] for player in players]
        min_in_column = min(target_column)
        duplicates = [duplicate[0] for duplicate in
                      filter(lambda x: x[1] == min_in_column, enumerate(target_column))]
        # if there are more than one, then
        while len(duplicates) > 1:
            column += 1  # move to the next column and update it
            sign *= -1  # and update the sign accordingly
            try:
                for turn in range(column_turn_number[column], turn_number):
                    players[sequence[turn]][column] += sign * binomial_coeff(turn, column)
                    column_turn_number[column] += 1
            except IndexError:  # if it doesn't exist yet, just add a new column and try again
                for player in players:
                    player.append(0)
                    column_turn_number.append(column)
                for turn in range(column_turn_number[column], turn_number):
                    players[sequence[turn]][column] += sign * binomial_coeff(turn, column)
                    column_turn_number[column] += 1
            target_column = [players[index][column] for index in duplicates]
            min_in_column = min(target_column)
            duplicates = [duplicate[0] for duplicate in
                          filter(lambda x: x[1] == min_in_column, zip(duplicates, target_column))]
        turn = duplicates[0]  # once all duplicates are gone, the remaining value is your next turn
        yield turn  # return the turn,
        sequence.append(turn)  # store it for future reference, and
        column, sign = 0, 1  # reset the column and sign

Be careful: The way I implemented this, It's lazily generating more and more elements as I request them. If you try generating a list via list-comprehension it'll try generating the entire list for you which, it being infinitely long, will crash your computer.
Instead, use it like this:

turn = turns(3)  #  "3" for 3 players
print([next(turn) for _ in range(99)])  #  "99" for 99 turns

This will give you the first 99 turns for 3 players:

>>> [0, 1, 2, 2, 1, 0, 2, 1, 0, 0, 1, 2, 1, 2, 0, 0, 2, 1, 0, 2, 1, 1, 2, 0, 2, 1, 0, 0, 1, 2, 1, 0, 2, 2, 0, 1, 0, 2, 1, 1, 2, 0, 2, 1, 0, 0, 1, 2, 1, 0, 2, 2, 0, 1, 0, 2, 1, 1, 2, 0, 1, 2, 0, 0, 2, 1, 0, 2, 1, 1, 2, 0, 2, 1, 0, 0, 1, 2, 0, 1, 2, 2, 1, 0, 2, 1, 0, 0, 1, 2, 1, 0, 2, 2, 0, 1, 2, 0, 1]

Here are the first 100 turns for four players:

>>> [0, 1, 2, 3, 3, 2, 1, 0, 3, 2, 1, 0, 0, 1, 2, 3, 2, 1, 3, 0, 0, 3, 1, 2, 0, 3, 1, 2, 2, 1, 3, 0, 1, 3, 2, 0, 0, 2, 3, 1, 2, 0, 3, 1, 1, 3, 0, 2, 3, 1, 0, 2, 2, 0, 1, 3, 0, 1, 2, 3, 3, 2, 1, 0, 2, 1, 3, 0, 0, 3, 1, 2, 3, 0, 1, 2, 2, 1, 0, 3, 1, 2, 0, 3, 3, 0, 2, 1, 0, 2, 3, 1, 1, 3, 2, 0, 3, 2, 1, 0]

and, to show that it also generates Thue-Morse, here are the first 100 turns for two players:

>>> [0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0]

As you can see, none of the various series in my question actually are the fairest possible turn order. None of them start $0, 1, 2, 2, 1, 0$.

---

Open subjects:

• are there nice substitution or recursion rules to generate the n-player series in this sense?
• are there other reasonable notions of "fair" turn order which result in different sequences?

---

EDIT: I tried plotting what happens for a large number of players $n$. Unfortunately I can't check with sufficient resolution but I conjecture that, as $n$ approaches $\infty$, each subset of $2n$ turns (excluding turns in previous subsets, so the set of turns $0\dots 2n-1$, $2n\dots 4n-1$, etc.) gives a (in the player limit) continuous boundary that ought to likely look fractal. (in the limit of turns $2n + i | i \in \left\{0\dots 2n-1 \right\} , n \to \infty$)

With the code as stated I fairly quickly run into memory problems, but here are the first few thousand turns that my computer could handle.

Note how each image is mirror symmetric. This is true for every $2n$ turns with $n$ players. To get much farther (more players, more turns) I need a more efficient approach.

$128$ players, moves $0 - 4607$, in chunks of $256 \ (= 2\times 128)$ moves each. Horizontal axis denotes turn, vertical the player ID (labelled from $0-127$).

(There is no text past these images.)