Do Two Singles Make a Double?

An interesting design problem from a reader.

The tourney is for “Cold War”, a two-handed version of the famous board game Diplomacy. As many as 64 players are expected. The chief limitation is time – apparently even in its two-handed form, the game takes a long time to play. So minimizing the number of rounds is crucial.

A single elimination 64 bracket takes six rounds to play. A full double elimination can take as many as 13 rounds, but since time is at a premium, that can be pared down to 10 rounds. One round is saved by not having a recharge, and two more by shifting the lower bracket.

But an unusual feature of this particular game offers a third possible bracket structure. Each player can easily play two games at the same time! So perhaps we can give players a second chance by simply playing two separate 64 brackets at the same time, with a playoff between the two bracket winners as a seventh round if the two brackets are not won by the same person.

This is marvelously efficient. Each player gets to play until they lose twice, but you save at least three rounds, and maybe four if you would otherwise insist on a recharge, because a recharge is never needed.

How should such a bracket be drawn, and how does it compare with conventional single and double elimination brackets in the item of fairness (C)?

Drawing the bracket is very simple in one respect, but rather tricky in another. The simple part is just using a standard 128 single elimination bracket, with each player being entered on one line in the top half, and another in the bottom half.

The tricky part is in allocating the entries to avoid, as much as possible, repeat pairings. Repeats are particularly unfortunate for this sort of tourney. In a standard 64DE bracket, repeats can be avoided through the first five rounds of the lower bracket. But in the double-single bracket, repeats can be avoided only through the first three rounds.

The technique is well illustrated by the bracket drawn by the sponsor of the Cold War tourney:

I’m ordinarily not a fan of this “butterfly” bracket style, but here it makes sense. Each side can be seen as being composed of eight groups of eight players, drawn in such a way that no two players in a group of eight on the left occur in the same group of eight on the right. This means that no pairing on one side will recur on the other through the first three rounds. After that, all bets are off – there can, and probably will, be rematches anywhere in rounds four through seven.

The sponsor generated the two sides of the draw using “reverse binary”. For example, player 6, binary representation 000110, is placed opposite binary 011000, or player 24. There are other ways to achieve the same result, but that’s an ingenious one. Before seeing this bracket, I hit on much the same result by grouping the players by INT(n/8) on the left, and FRAC(n/8) on the right.

The numbering of the players shown above is convenient for showing the way the draw is made, but it does not serve the purposes we’re accustomed to seeing with seeding lines on more conventional brackets. Let’s leave aside, for the time being, the thorny question of how such a bracket should be drawn if the tourney is seeded. But even blind draw tourneys make use of the seeding lines to allocate byes, and the player numbers on the bracket shown above would be particularly poor for this purpose.

(NOTE: the next paragraph was revised after I found an error in the suggested sequence of byes)

To get byes well spaced through both brackets, you can begin by allocating the first eight byes so that there’s one in each group of eight on each side, which can be done by striking the only common members of the groups across from each other. Thus, one could strike, in order, these player numbers: 0, 63, 33, 30, 18, 45, 51, and 12. After that, the next eight byes can be 8, 55, 41, 22, 26, 37, 59, and 4. These numbers can be found through a process of finding a number in each of the groups of four without a bye that is also without a bye on the other side. If still more byes are needed, they can be chosen from any of the numbers that do not already draw a bye on the other side.

OK, assuming you have the lines carefully arranged, how does the bracket perform? Somewhat to my surprise, this peculiar bracket does run in my simulator, but the simulator does not appear to give reliable figures for fairness (C). So, in a throwback to the early days of simulation, I’ll judge the performance of the bracket solely on the average skill level (i.e., the Z score) of the tourney’s champion (so that, unlike fairness (C), higher numbers are better, up to a limit of 2.344, which is the average skill level of the best player):

As expected, double elimination is considerably better than single elimination, and the “double single” falls somewhere in between. What may be a little surprising is that the double single isn’t somewhat closer, in performance, to the full double elmination. After all, the double single bracket plays the same number of games as the double elimination, which is twice as many as in the single elimination. But all those extra games seem to be doing much less good.

I suspect that this is because of the way rematches occur. Consider that, at luck = 0, the double elimination will always give second place to the second-best player. The only match in which the second-best can encounter the best player for a second time is in the final. In the double single, in contrast, such an encounter can occur as early as the fourth round. In general, the double single bracket is more prone to eliminating good players by re-matching them against other good players early.