Sports Scheduling

Do you like watching sports? Today I will be introducing sports scheduling, which deals with the problem of how to create a schedule for sports matches. The following is a simple introduction to sports scheduling.

At the start of every season, various sports will announce the schedule for games. Let's consider a simple example from soccer (J League). For J1 League games, all the teams have to play each other twice in a double round-robin schedule. Since there are currently 18 J1 teams, that means each team will play the 17 other teams twice each, leading to 2 X 17= 34 slots for the schedule.

Since 18 teams are too many, let's look at an example of the first round of matches for 6 teams (Figure 1). Each row on the figure represents a team with the letters in the rows showing which team will be their opponent for that slot. In the schedule shown in Figure 1, team A will be playing team C for the first slot, and then play teams D, E, F and B in that order.

You can see that each team is playing some other team for every slot. Even in J League with each team playing 34 games, they manage to fit them into 34 slots. Don't you find this strange? Every slot teams have games, with no rests, and all the games fit into 34 slots. How could a schedule like this be created?

If you think you can just figure it out as you go along, you are mistaken. If you fill up the first slot randomly, you will find there is no way to fit all the games into 34 slots by the time you reach the end. Even with only 6 teams, if you fill in slots randomly as in Figure 2, it becomes impossible to fill in 6 matches in the fourth and fifth slots. This schedule is quite the puzzle. In fact, in 1847 a mathematician by the name of Kirkman showed that if the number of teams is even, a schedule can always be made. Math is present even in this unexpected situation.

Home and Away Games

For J League matches, the two teams always play on the home pitch of one of the teams. Therefore, there is an away game where the team plays on the opponents' pitch, and a home game played on the team's own pitch. (Generally) no team likes to play away. The number of away games is the same for every team, so that is fair, but what about playing continual home or away games? Table 1 shows an example for J League and Serie A. H is home games, A is away games. The total number of continuous H or A (referred to as a 'break', and underlined in the table) is listed at the end of each row. Urawa has 2 instances of continuous H, and 2 of continuous A (the series of 3 as can be counted as 2 separate instances of continuous A) for a total of 4 breaks, which isn't balanced with the other teams. If you compare this with the Serie A schedule, you can see better balance between the teams.

I hope you see how trying to create a schedule with balanced numbers of continuous H and A for the teams makes a fairly difficult puzzle.

Creating Schedules with Computers

In recent years, it has become more common for sports schedules to be created using a computer. One of those reasons is probably because sports have become big business. For American Major League Baseball, computers are used not only to make a schedule that has few continuous away games, but to determine where TV broadcast rights should be sold to. It was big news in 2005 when a group lead by a professor from Carnegie Mellon University was hired to create the MLB schedule.

Japan's J League also started using computer software a few years ago, and became able to create better schedules. Recently, professional sports in Japan have started to face a period of change in the area of management (a good example is the fuss about baseball team takeovers a few years ago). In the next few years, it is certain that details of earnings are made public, including the creation of schedules. By seeing if your favourite team has been losing money on scheduling, you might be able to enjoy watching sports from a different angle.

(Offered by: Kusa no Midori (The Greeness of Grass) No.215)