Monday, November 23, 2009

Round-Robin Tournament Scheduling

For the last several years, I've held an in-class tournament on the last class day before Thanksgiving. Everybody's mind is elsewhere anyway, so the positive vibes generated by an hour spent hootin' and hollerin' are far more valuable than class content that would be forgotten long before the turkey made it into the oven.

Tomorrow's the big day, so I've spent part of today working out the tournament schedule. As usually seems to be the case, I have a different number of teams this year from past years, so I had to make a new schedule from scratch. I keep forgetting how I did it last time, but I always seem to converge back on the same technique. I finally decided to write down the technique so I can just look it up next year. Also, I'm hoping somebody can tell me what this technique is called, since it can't possibly be original.

Unless I have too many teams, I like to run a round-robin tournament, where everybody plays everybody else. There's a well-known algorithm for scheduling such a tournament by hand. I'll illustrate this algorithm with 6 teams, numbered 0–5. Start by writing the teams down in two rows, as follows:

   0 1 2
   5 4 3
The columns say which teams play each other. In this case, team 0 plays team 5, team 1 plays team 4, and team 2 plays team 3.

Now, leave team 0 in place, but rotate teams 1–5 one position clockwise.

   0 5 1
   4 3 2
In this round, team 0 plays team 4, team 5 plays team 3, and team 1 plays team 2. This process continues for three more rounds:
   0 4 5
   3 2 1

   0 3 4
   2 1 5

   0 2 3
   1 5 4
For an even number of teams, this technique generates a schedule with N−1 rounds, and N/2 games per round. For an odd number of teams, you add an extra dummy team, yielding a schedule with N rounds and (N−1)/2 games per round. In each round, the team scheduled against the dummy gets a bye.

Many games have a slight asymmetry, such as a homefield advantage or a first-move advantage. For my game, the “red” team has a very small advantage over the “blue” team. In tournaments for such games, it is important to balance the number of “home” games and “away” games played by each team. In the above algorithm, this is accomplished by making the top row the home team in odd-numbered rounds and the bottom row the home team in even-numbered rounds. (Note that, when N is even, half the teams will get one extra home game.)

Okay, so the above technique is easy, but it has a major drawback for my purposes, at least when N is odd. Because the tournament must be completed by the end of the class period, I need to be ready to drop games from the schedule if it looks like we're running long. The easiest way to accomplish this is to drop an entire round. But when N is odd, one team has a bye, which means that that team will end up playing a different number of games from everybody else, which in turn can make it difficult to determine the winner of the tournament.

To avoid this problem, I use the following technique. I organize the schedule in N/2 rounds, rounded down if N is odd. In each round (except possibly the last), every team plays twice: one home game and one away game. The rule is that, in round R, team X plays at home against team (X+R) mod N, and away against team (X−R) mod N. (If you don't remember how mod works, it simply means that the team numbers wrap around.) For example, here is a schedule for 7 teams, numbered 0–6.

   Round 1: 0-1 1-2 2-3 3-4 4-5 5-6 6-0

   Round 2: 0-2 1-3 2-4 3-5 4-6 5-0 6-1

   Round 3: 0-3 1-4 2-5 3-6 4-0 5-1 6-2
Each game is listed as HOME TEAM–AWAY TEAM.

If N is even, then the last round is treated specially. As described so far, the last round in an 8-team tournament would look like

   Round 4: 0-4 1-5 2-6 3-7 4-0 5-1 6-2 7-3
This involves repeat games, such as 0-4 and 4-0. To prevent such repeats, we chop off the second half of the last round when N is even.

Again, the advantage of this scheduling algorithm is that I can delete a round on the fly without causing an imbalance in the number of games that each team plays. Deleting a round also maintains the balance between home games and away games for each team, although that's a lesser concern.

6 comments:

stick said...

Sir - have you tried the Blitzkreig ants against any from this year?

Chris Okasaki said...

I just tried Blitzkrieg four times against this year's winner. They got out a quick egg killer that hamstrung your strategy, so they won 4-0.

Sjoerd Visscher said...

This only works for virtual competitions. If you would do this in the real world for 7 teams f.e., you can only do 3 matches at the same time, so one round takes 3 match lengths.

Chris Okasaki said...

@Sjoerd: It's certainly true that you can't play all the matches in a round at the same time, so it shouldn't be used in situations where that is important. I use it for running a tournament where each individual match takes less than a minute, and the matches are run sequentially. But it could also be used in a real-world tournament where each team plays in two out of every three time units.

David Feuer said...

This tournament design problem sounds like a wonderful homework exercise for the week before the tournament. Lay out your fairness and cut-short requirements and challenge your students to come up with an algorithm. Allow them to decide how to balance the home-away fairness against the desire to run many pairs of teams against each other if the tournament is cut short. Bonus points for an algorithm that offers some sort of tuning factor for this.

Chris Okasaki said...

@David: Great suggestion!