Suppose two captains, A and B, are choosing people for their teams. To make things fair, the two captains alternate choices: A, B, A, B, etc. This is much better than simply letting A choose his team first and leaving B the dregs, but it still gives A a substantial advantage. If each captain picks the best remaining player on each term, A will get the best player in each pair of choices.
How could we do better? One proposed strategy is the Thue-Morse sequence. Someone has to choose first, so let’s say it’s A. Then B chooses next. At this point A is still at an advantage, so we let B choose again before giving A the next pick. So the first four choices are ABBA. The next four choices reverse this: BAAB. Then the next eight choices reverse the pattern of the first eight choices. So the first 16 choices are ABBABAABBAABABBA. This process has been called “taking turns taking turns.”
In terms of 0’s and 1’s, the sequence is defined by t0 = 0, t2n = tn, and t2n+1 = 1 − t2n.
How well does this procedure work? Let’s simulate it by generating random values representing skill levels. We’ll sort the values and assign them to the two teams using the Thue-Morse sequence and look at the difference between the total point values on each team. Equivalently, we can sum the values, alternating the signs of the terms according to the Thue-Morse sequence.
import numpy as np
# Thue-Morse sequence
TM = np.array([1, -1, -1, 1])
# Simple alternating signs
Alt = np.array([1, -1, 1, -1])
N = 1000000 # number of simulations
y = TM # change y to Alt to swap out strategies
total = 0
for _ in range(N):
x = sorted(np.random.random(4), reverse=True)
total += sum(x*y)
print(total/N)
When we use the alternating sequence, there’s an average skill difference between the two teams of around 0.4. This is a huge imbalance relative to expected total skill of 2. (Each skill is a uniform random value between 0 and 1, so the total skill of all four players is 2 on average.)
When we use the Thue-Morse sequence, the average difference in my simulation was 0.000144. With one million simulations, our results are good to about three decimal places [1], and so the difference is indistinguishable from 0 to the resolution of our simulation. (When I repeated the simulation I got -0.000635 as the average difference.)
There are several ways to explore this further. One would be to work out the exact expected values analytically. Another would be to look at distributions other than uniform.
* * *
[1] The error in the average of N simulations is on the order of 1/√N by the central limit theorem.
For 8 players, is the Thue-Morse sequence ABBABAAB somehow better than the repeated 4-player sequence ABBAABBA? Thue-Morse gives ‘mod-4 parity’, but I expect only mod-2 parity is important.
This is a fun sequence to be pronounced by a computer, f.e. type “say abbabaabbaababbabaababbaabbabaab” in the command line on a Mac.
Assuming a uniform (or at least symmetric, e.g. normal) distribution, it should be easy to prove that, for $a_i$ the ability of the i-th best player, the expected values satisfy $E(a_i) = 1-E(a_{n-i+1})$. So any symmetric sequence of choices should lead to both teams having the same expected total ability.
I consider the sequence ABBAABBAABBAABBAABBA… (sometimes called 12*) as a good first-order approximation of the Thue-Morse sequence.
In many context this simpler sequence may be easier to remember, analyze and implement than the Thue-Morse sequence.
Ah, one of my favorite problems and one of my favorite sequences brought together.
Question: Given a team size n, is Thue-Morse optimal for all n, or just when 2n is a power of 2? I *think* that Joshua Cooper and Aaron Dutle (http://people.math.sc.edu/cooper/ThueMorseDueling.pdf) proved Thue-Morse is best for all n, but I’m not sure.
Another question: Most treatments consider a simple ranking of team members; in effect, the 2n participants have skills in the set {1, … 2n}. What happens if we consider different distributions? In particular, suppose the skill levels of the players are normally distributed.
How about simplifying the division: Captain A picks the best and the worst player in his first step, then captain B picks the best and the worst from the remaining group then A again continues in the same way. Would the result be unfair? Why? Why not?
@xpil: It will work if both captains are able to agree on a common ranking AND the number of players is multiple of 4 AND the qualities are distributed symmetrically.
Carlos: ok thanks for the clarification. I didn’t realize that the Thue-Morse sequence was more universal.
This can be proven exactly using the kth-order statistic for a sequence of n uniform random variable. It holds that Ord(k, n) is distributed as Beta(k, n – k + 1) with mean k / (n+1).
For n = 4, the Alt sequence then has expectation of ((4 + 2) – (3 + 1)) / 5 = 2/5 = 0.4. The TM sequence has expectation of ((4 + 1) – (3 + 2)) / 5 = 0.
The tennis tie-break sequence of A B B A A B B A… is also fair for multiples of 8, since 1 + 4 + 5 + 8 = 2 + 3 + 6 + 7 = 18.
In fact, for uniformly distributed skills, any even-length palindrome in A/B (e.g. A A B B B B A A) is also a fair way to choose teams.