Thue-Morse sequence as a fair-share sequence

Let’s suppose a simple game that I’ll call The Greed Game: there’s several coins (gil) on the table. The rules are simple: we take turns and we may take one gil. You and me taking one turn will be defined as a round.

Is this a fair game? It is, as long as we keep playing full rounds. At the end of each round we both have one gil, so it doesn’t matter who goes first.

Let’s also imagine what I’ll call The Weighed Greed Game. It’s almost the same as before, but this time instead of single coins, there are piles of coins. To keep it simple, let’s imagine the piles have 1, 2, 3, 4, 5, 6, 7 and 8 gil. The game is the same: Andy and Bob take turns, but this time we can take one and only one pile of gil.

I’ll go first.I take 8 gil. What do you do?

You’ll probably take the pile with 7 gil. Then I’ll take 6… and you can see where this is going. At the end, I have 20 gil and you have 16.

This seems unfair, right? At the beginning of each round, I always take the largest pile, leaving you with the second largest. Wouldn’t it be better if we took turns being the first each round?

1 A regular 4-turn order

Let’s try again, with a smaller example: only 4 piles—with 1, 2, 3 and 4 gil—, but this time we take turns being the first in a round. In other words, the turn order is now Andy, Bob, Bob, Andy (ABBA for short)

I’ll take 4, you’ll likely take 3; now it’s your turn again, so you’ll likely take 2 and I’ll take 1. final score: we both have 5 gil. Fair division!

So we can just repeat this algorithm to divide 8 coins equally, right? Let’s see what happens with 8 coins:

• A takes 8
• B takes 7
• B takes 6
• A takes 5
• A takes 4
• B takes 3
• B takes 2
• A takes 1

Total: 18 gil for A; 18 gil for B. Hooray! This works and we can go home, right?

2 The long run

However, this works under the assumption that we always play full rounds. Moreover, our 4-turn strategy only works perfectly if the number of turns is a multiple of 4—in other words, if the number of rounds is even—and still has a bias that favors the Player A for reasons that I will demonstrate later.

Suppose that we play the Greed Game—or the Weighed Greed Game— with piles of 1, 2, …, 23 and 24 gil. But this time there’s the extra catch that I can cut the game short at any turn. What’s the most fair turn order?

Let’s keep a running score with both strategies. The score is as follows:

• Every time Andy has more money, it will be worth 1 point to the score
• Every time there’s a tie, it will be worth 0 points
• Every time Bob has more money, it will be worth -1 points

This way, a fair turn order should end up with a score of 0 (or close to it). Let’s see how our game starts, assuming we have 24 piles of gil.

The regular turn order goes as follows:

No surprises here. The regular order always gives an advantage to the first player and from the table, it’s evident that Andy will always have more gil. What happens with the 4-turn order?

Immediately we can see that this is better, but there’s a catch: notice how the average score is always positive and seems to tend to 0.25. Look at the third column for a hint: in any four consecutive turns, Andy wins two, B wins one and they are tied in one. This order, while better, still gives Andy an edge. Can we do better?

3 Thue-Morse Sequence

Why not extend the idea of taking turns in taking turns? As we’ve seen, using only the 4-turn order gives an advantage to Andy. What if every 4 turns the 4-turn is reversed? This way, we could get an 8-turn order… but using it could also be unfair, right? why not then take the 8-turn order and reverse it after 8 turns? And then after 16 turns…

You get the idea of how this goes. In general, we can always construct a fair sequence by taking the sequence so far and reversing it. In essence, doing this forever will give us the Thue-Morse sequence. But, how does it fare against the other strategies?

This is way better. Look at the last column: now there’s three things to notice:

1. The running average is sometimes positive and sometimes negative, which means Andy doesn’t always have the advantage;
2. There are many zeroes, which means there are many (cutting) points at which the whole sequence is fair; and
3. The absolute values of the running average get smaller and smaller and tend toward zero, meaning that the longer this sequence goes, the most likely it is to be fair at any one point.

So, what gives? The Thue-Morse sequence is thus a fair(-er) way of “taking turns” if we don’t know ahead of time how long the game will go on. the Weighed game serves to illustrate a situation that may be encountered in many situations in life: there’s a limited resource to draw from and being first matters. With two parties vying to get it, the Thue-Morse sequence offers a first approach as to how to allocate that resource in a fair way.

You can see my amateurish code and illustrative graphics by pointing your browser to this jupyter notebook and watching it, maybe even running it in your own home Python console (numpy and matplotlib required)