Choosing up Sides, Again

by Brian Hayes

Published 12 April 2007

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:

ABAB vs. ABBA vs. AABB graph