This is a belated update to my most recent post (which is not at all recent!). If you recall, we were discussing simple playground protocols for assigning players to teams. In one case the captains of teams A and B choose players in the order ABAB…; the alternative order is ABBA…. I presented some simulation results showing that the ABBA algorithm gives more evenly matched teams, at least for a certain range of parameters. Soon after that article appeared, my friend Leonardo Maffi wrote to say that he had re-implemented my program. His results agreed with mine in the ABAB case, but they were different for ABBA. Knowing from experience that Leonardo usually gets things right, I went looking for a bug in my code.
At this point the story gets a little twisted. It turns out that Leonardo had interpreted the problem differently and had therefore implemented a different algorithm; no surprise, then, that our results diverged. But that doesn’t mean my results were correct! On looking closely at my code I found that I had indeed made a clumsy mistake, which led to bogus output for the ABBA simulation. The ABBA protocol is still superior to ABAB, but by a smaller margin. For the record, here’s a corrected version of the table from the earlier post. I’ve also added results for the one remaining four-turn protocol, AABB.
discrepancy
n m ABAB ABBA AABB exact
4 4 1.4 0.9 3.0 0.7
6 8 3.3 1.7 9.0 0.9
8 16 7.0 2.7 14.1 1.2
10 32 14.5 5.5 33.0 1.7
12 64 29.5 9.3 59.0 2.3
14 128 59.7 18.7 129.0 3.6
16 256 120.4 33.0 240.9 5.7
18 512 242.5 66.3 513.1 8.4
20 1024 487.7 120.0 975.2 14.2
22 2048 979.4 240.8 2049.0
24 4096 1966.1 442.8 3932.4
26 8192 3944.2 889.9 8194.7
28 16384 7909.3 1654.7 15821.0
30 32768 15853.9 3317.9 32774.0
32 65536 31768.5 6245.8 63554.1
And here is the corresponding graph:
