When $2$ players are given an infinite stream of items to divide between them. There is no way to quantify the value of the items, but their value is strictly decreasing. Which person should take the $n$th item is given by the Thue-Morse sequence:

$0110100110010110100101100110100110010110011010010110100110010110\cdots $

First player, then second player, then second player, then first player, and so on. Without any other information, this is the fairest possible sequence.

What would be the generalization of this sequence for $n$ players?

There are likely multiple ways to define such a sequence that result in different sequences. So here is the one I am interested in.

  • The players go in order for the first $n$ items, so the first $n$ terms will be $0,1,2,\cdots,n-1$.
  • On later turns, the player with the least total value takes the next item.
  • The value of item $i$ is $\lim_{\varepsilon\to 0^+}(1-\varepsilon)^i$.

This comes from a simple game where on any given turn, there is a $\varepsilon$ chance the player whose turn it is wins, and a $1-\varepsilon$ chance the game continues. If we multiplied the item value by $\varepsilon$, the item value becomes the probability of winning on that turn, and a player's total item value for the entire infinite sequence is their chance of winning the game, which should be $\frac{1}{n}$, the fairest possible value.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.