Tuesday, May 22, 2012

Bracketology (in a very real and very literal sense)

Or: What Happened To Double Elimination?

Earlier today I was playing in an online tournament that was run using the Challonge! website (for the morbidly curious, you can see the bracket there at the link).  It was a double-elimination bracket, and as I had a couple of bye rounds in a row, I was watching the bracket fill in when I realized a couple of weird things.  First, all the first-round losers (including the "first round second round" games such as mine, where both players had a bye during the first round proper and so played our second round game while the others were playing their first round game) were separated -- after the first round games were finished, no one could play a consolation game as none of the bottom games were filled in.  (It's a little hard to see now in the finished bracket, but if you trace down all the first-round losers you will see that none of them play each other.)  The other realization took a little while: the losers dropped down in a nice neat pattern -- but in every other round (rather than immediately after they lost).

Now for our purposes, that's actually a good thing: the consolation bracket was run using 60%-length games, so getting through two of them in the time the championship bracket could get through one was not a completely outrageous idea.  But in a "normal" situation, this would lead to some sitting around in the top bracket.  I don't remember ever coming across this in my more active running-things-on-a-double-elimination-system days, other than a mostly-serious proposal to FIDE to change their single-elim to a double-elimination tournament in this same two-for-one style (literally, as the main matches were two-day affairs, and he proposed putting in two one-day consolation matches for each).

I had myself, once upon a time (in graduate school), made a program that automatically created brackets for any size group (well, up to 64 anyway).  Granted, it was not fancy on the web (it was definitely a command-line program, which cranked out a .tex file that could be converted to PDF), and the version that I found on my computer didn't have the consolation bracket part in it (I think I never quite got the layout right anyway).  But I remember what I did, so I thought I'd compare what I did (with the losers dropping down immediately) compared to the current state-of-the-art.  I've put a spreadsheet up with the two versions (each in their own sheet) on the web via GoogleDocs, so you can follow along.  (Or, if you happen to need a 32-team double-elimination bracket soon, well, now you've got two to choose from.)  Here I am just comparing the effect of the two-for-one round system, ignoring the effect of how I treated byes differently at the beginning (which is why I am using a 32-team bracket: no byes!).

The championship brackets are basically the same for each (not much you can really do with those).  In the Challonge version, the consolation rounds go as: 16 R1 losers; 8 winners + 8 R2 losers; 8 winners; 4 winners + 4 R3 losers; 4 winners; 2 winners + 2 R4 losers; 2 winners; 1 winner + 1 R5 loser.  There are some advantages here, especially for automated bracket building: every round has a 2^n number of teams (meaning no additional working out of seeding--almost), and in each round where teams drop down from above, there are exactly as many winners coming through from the previous consolation round, so each matchup features one loser from above playing one winner from before.  A downside is that the seeding works a little too well: if you follow the seeding exactly, every single drop-down round will feature a rematch between two teams (so you have to do some fiddling: instead of (say) 15v18 and 16v17, you do 15v17 and 16v18).  In my version, the consolation rounds go as: 16 R1 losers; 8 winners + 8 R2 losers; 8 winners + 4 R3 losers; 6 winners + 2 R4 losers; 4 winners; 2 winners + 1 R5 loser.  You do have the same seeding problems in the second consolation round, plus the "4 winners" round towards the end.  However, you finish in one fewer round (that is, if you can handle all 16 first- and second-round games at the same time, you can finish my schedule in 10 rounds, but you need 11 for the Challonge version).

I thought about running some simulations to see what the types of results would be, but I would need some sort of function that tells me how often seed m beats seed n in a game, and I don't have a well-tested one to hand (or, really, any at all).  I may still do this simulation, with the caveat that it will be for entertainment purposes only.  (Well, I'll be entertained.)  But you can still do a little bit of analysis about the results of the two brackets: the Challonge version definitely rewards winning championship bracket games more than the mine (as a result of the extra byes).  For instance, a team who wins two and then loses (ie loses in the "quarterfinals") would be guaranteed a four-way tie for 9th in the Challonge version, versus a six-way tie for 11th in mine; a team who wins three and then loses (ie loses in the "semifinals") would be guaranteed a two-way tie for 5th in the Challonge version versus a four-way tie for 7th in mine; the losing finalist is guaranteed bronze in the Challonge version, where I only guarantee 4th place.  Also, the teams who go farther in the championship bracket will play fewer games (with the extra byes) in the Challonge version: to win, you must go 10-1 if you lose in the first two rounds, 9-1 if you lose in the third round, 8-1 if you lose in the fourth round, or 7-1 if you lose in the fifth round.  (In my version, you play virtually the same number of games no matter when you lose, if you come up through the consolation bracket.)

Which is better?  Well, obviously I prefer mine, as I don't like standing around and I'm not sure I think that winning championship bracket games should be worth double winning a consolation bracket game.  I don't see a good tournament-related (other than convenience of drawing the bracket) reason for skipping the rounds, but if you can come up with one I'm willing to hear it.

No comments: