I find myself playing in a lot of Magic tournaments. Sometimes I would find myself in big tournaments with hundreds of people. The longest I took part in lasted ten rounds, each taking a bit over an hour. For that whole time, I didn't leave the tournament room.
There are a number of ways to run such an event, and likely the easiest is to just hold a single-elimination tournament. Now, in order to determine a champion, only (log_2 (n) +1) rounds are needed with n players. The problem is that this is very unsatisfying for many players, especially those like myself, who aren't necessarily all that great and are just hoping to play a bunch of games. Tournament organizers want to attract as many players as possible and thus they use "Swiss Seating", a method of pairing opponents that have similar records. This works well and, as I recall, their format usually has (log_2 (n) + (2 or 3)) rounds. After that, the top eight players enter a single-elimination bracket to determine the overall winner.
This method is nice for a few reasons: it works while having a very small number of contests between players but still creates a sturdy ranking. Swiss seating is used for a number of combinatorial game tournaments (often with their own variations) but it can't be implemented everywhere.
American college football is plagued with controversy about who the best team is in a season. I won't get into all the details about these rankings, but there are a few major restrictions on the sport. The first is that the level of intensity and preparation for each game requires that teams can only play at most once per week. This means that teams play at most 13 games during the regular season and it means there is (probably) no time for an end-of-season tournament at the end aside from the current one-round system (the top two teams play each other).
Well, you might think, there are only about 120 total college football teams (in the top division. Overall, there are more like 650). 13 games is more than enough to come up with a swiss tournament that does a good job of picking out the top two teams. Unfortunately, swiss seating requires that teams don't know in advance who they're going to be playing. In college football, the schedule is usually prepared over a year in advance!
In order to overcome this, rankings are done with human input. This, of course, leads to the above-mentioned controversy: determining who the two top-ranked teams are leads to no end of discussion. Worse still, many of the voters used for input are people tied to teams themselves; each of the coaches gets to vote!
Are there any interesting tournament solutions that handle "bad seating" without introducing a human element? It seems feasible, except that perhaps more than just wins and losses would be needed in the data (amount a team won by, for example).
A Domino-Covering Problem
2 weeks ago