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.