Round-robin scheduling with regard to rest differences

Abstract

Fairness is a key consideration in designing sports schedules. When two teams play against each other, it is only fair to let them rest the same amount of time before their game. In this study, we aim to reduce, if not eliminate, the difference between the rest durations of opposing teams in each game of a round-robin tournament. The rest difference problem proposed here constructs a timetable that determines both the round and the matchday of each game such that the total rest difference throughout the tournament is minimized. We provide a mixed-integer programming formulation and a matheuristic algorithm that tackle the rest difference problem. Moreover, we develop a polynomial-time exact algorithm for some special cases of the problem. This algorithm finds optimal schedules with zero total rest difference when the number of teams is a positive-integer power of 2 and the number of games in each day is even. Some theoretical results regarding tournaments with one-game matchdays are also presented.

Appendices

Appendix 1: Reference solutions

For reference purposes, we provide the optimal schedules for the $\text{RDP}(10,3\vert 2,2,1),$ $\text{RDP}(12,3\vert 2,2,2),$ and $\text{RDP}(16,6\vert 2,2,1,1,1,1)$ (Tables 10, 11, 12).

Table 10 An optimal schedule ($\text{RD}=16$) of the $\text{RDP}(10,3 \vert 2,2,1)$

Table 11 An optimal schedule ($\text{RD}=0$) of the $\text{RDP}(12,3 \vert 2,2,2)$

Table 12 An optimal schedule ($\text{RD}=56$) of the $\text{RDP}(16,6\vert 2,2,1,1,1,1)$

Appendix 2: Proof of Theorem 4

Theorem

The method given by Algorithm 2 results in a schedule with zero $\text{RD}$ when n is a positive-integer power of 2 where $n \ge 8,$ and when the number of games on each day is even.

Proof

Let’s say we have a tournament where there are only two games (with four teams) on each day. Let those teams playing on the same day finish all the possible games among each other. We now define certain swap operations that will help constructing a schedule with zero total rest difference. Consider two different days, and swap two teams from each day with each other so that they will face different teams in the next round, say $r_b.$ Due to the swap operation, teams that played on different days in round $r_b-1$ will have to play each other in round $r_b.$ Observe that one can swap two games played in round $r_b-1$ involving the swapped teams (colored grey in Table 13) to get rid of this rest difference (see Table 13). Notice that this operation will work any time when teams from two different days are swapped between two different days in a round. In Table 13, the game between teams 3 and 4 should be swapped with the game between teams 5 and 6 to get rid of the rest difference that will otherwise occur in round $r_b.$ In Table 13, it was assumed that the teams playing in round $r_a$ have never faced each other before. Table 14 shows a situation where the teams playing in a round that were not swapped have already faced each other before a team swap operation. In Table 14, games between team 1 and team 2, team 3 and team 4, team 5 and team 6, and team 7 and team 8 were assumed to have been played. Still, with a game swap in round $r_b-1$ (among the greyed games) the rest difference in round $r_b$ can be eliminated. $\square$

Table 13 Eliminating rest differences of a swap operation

Table 14 Eliminating rest differences of a swap operation

Assume that $n = 8$ with two days where there are only two games on each day. When n is less than 8, we cannot have a tournament with more than one day where all days have two games each. Let’s build our tournament so that the whole tournament consists of intermediate rounds (not consecutive) where the groupings (teams that will play among each other) in those rounds have been determined by team swap operations between two days only (such as in rounds $r_a$ and $r_b$ in Tables 13 and 14). The resulting groupings (not the actual games to be played) with 8 teams is shown in Table 15. Teams playing on the same day will actually finish all the games among each other in a fashion as explained in Tables 13 and 14. Thus, the whole tournament can be built performing team swap operations between two different days, and we already know that if that is possible then we have a way of getting rid of the rest differences. In round $r_b,$ teams 3 and 4 are swapped with teams 5 and 6; and in round $r_c,$ teams 5 and 6 are swapped with teams 7 and 8. Those three (if the number of teams is equal to n then the number of different groupings is $n/2-1$) sets of groupings constitute all the possible team combinations necessary to have a round-robin tournament with $n=8$ teams where each team should play all other teams once. The resulting schedule shown in Table 16 demonstrates that there will be no rest differences using the prescribed swap operations when $n=8$ after all games are played.

Table 15 Team groupings for $n=8$

Table 16 Finished schedule for the $\text{RDP}(8,2 \vert 2,2)$

Let’s now double n to 16. We are interested in obtaining a round-robin tournament schedule with n/4 days in each round with two games on each day, i.e. there will be four teams playing on each day. Teams are numbered from 1 to n. We can build the team groupings so that initially teams from 1 to n/2,  and $n/2+1$ to n are grouped together forming two separate groups of size n/2. Let these sets of n/2 teams finish the games among each other using swap operations. Then, let teams 1 to n/4 match with teams $n/2+1$ to 3n/4,  and teams $n/4+1$ to n/2 match with teams $3n/4+1$ to n forming two different sets of n/2 teams. This grouping can be achieved via swap operations. In the round just before the matching, teams $n/2+1$ and $n/2+2$ are grouped together either with teams $3n/4+1$ and $3n/4+2,$ or with $n-1$ and n. On the other hand, $n/2+3$ and 3n/4 are grouped with the other pair among teams from $3n/4+1$ through n teams $n/2+1$ and $n/2+2$ are not grouped with. In the other half’s grouping among teams from 1 to n/2,  teams 1 and 2 are grouped either with $n/4+1$ and $n/4+2,$ or with $n/2-1$ and n/2; also teams 3 and 4 are grouped together with the pair from $n/4+1$ to n/2 that teams 1 and 2 are not grouped with. Thus, one can swap $n/4+1$ and $n/4+2$ with either $n/2+1$ and $n/2+2,$ or with $n/2+3$ and 3n/4; and also $n/2-1$ and n/2 with the other pair from $n/2+1$ to 3n/4. After the matching, let the matched teams finish their remaining games among each other (the way these teams are grouped is again determined via swap operations). Finally, let teams 1 to n/4 match with teams $3n/4+1$ to n,  and teams $n/4+1$ to n/2 match with teams $n/2+1$ to 3n/4. This matching can also be achieved via swap operations in a manner similar—albeit with different team indices—to the swap operations done when teams 1 to n/4 were matched with teams $n/2+1$ to 3n/4,  and teams $n/4+1$ to n/2 were matched with teams $3n/4+1$ to n. Once these groups, each of size n/2,  also finish their remaining games among each other (again via swap operations) the tournament is complete because all teams have already played against every other team. Table 5 shows the groupings when $n=16$ whereas Table 7 shows the resulting optimal schedule when finished.

In a similar fashion, when $n \ge 32,$ groupings of teams can be obtained by creating different sets of n/2 teams in three stages as shown in Table 17. The first column in the table indicates the number of groupings that will result from the matchings in the table. In the second and third stages there will be less groupings because some teams were already grouped together (thus played against each other) before. Since we already know how to form consecutive groups via swap operations for n/2 teams, and how then to schedule their games with zero rest difference, we can also find a schedule with no rest differences whenever n is further doubled.

Table 17 Building a schedule’s team groupings

Above discussion shows that, when the number of teams is a power of 2, tournaments of zero $\text{RD}$ with two games on each day can be generated. Due to Proposition 1, rest differences in those schedules can be eliminated whenever the number of games in all days is a multiple of 2 such as in the case of the $\text{RDP}(16,2 \vert 4,4),$ $\text{RDP}(16,2 \vert 6,2),$ $\text{RDP}(16,3 \vert 4,2,2)$ and $\text{RDP}(16,3 \vert 2,4,2).$ Thus, in tournaments with n teams where n is a power of 2 and where the number of games on each day is a multiple of 2, one could first build a schedule with a zero $\text{RD}$ for the $\text{RDP}(n,n/4)$ with two games on each day, and then days in that schedule can be combined to obtain the desired schedule with no rest differences.

Thus, the algorithm will work for any instance of the $\text{RDP}(n,p \vert \gamma _{1}, \ldots ,\gamma _{p})$ where the team number can be expressed as a power 2, i.e. $n=2^k$ ($n \ge 8$) where $k \in {\mathbb {Z}}^+,$ and the number of games in each period is divisible by 2, i.e. $\gamma _{d} \bmod 2 = 0$ $\forall d \in D.$

Appendix 3: Pseudocode and complexity of the polynomial-time exact method

We provide a pseudocode for the proposed polynomial-time exact method that is applicable to some special cases of $\text{RDP}(n,p)$ as explained in the main text.

In the pseudocode, the block numbers from 1 to 6 refer to a specific location within the block of the previous level of the recursion as shown in Table 17. Thus, the position of a specific grouping of four teams can be identified upon return by checking the block numbers associated with each level of the recursion stored as a list in groupingBlockInfo.

The implementation of Algorithm 2 has polynomial-time complexity. The recursion used for generating the groupings (line 35) stops when all necessary four-team groupings have been generated. The number of these groupings, i.e. the number of recursive calls with four teams, is $n/4 \cdot (n/2-1)$ (n/4 two-game days in $n/2-1$ grouping rounds). The recursion finishes after $\text{log}_2 n-2$ (the procedure starts with groupings of size n/2 and stops with four-team groupings) levels. Hence, the complexity related to this part is $O(n^2 \cdot log_2 n),$ and is thus bounded by $O(n^3).$ The final ordered grouping (line 36) is obtained (such as the one in Table 5) by traversing the location information stored in groupingBlockInfo of length $\text{log}_2 n - 2$ for n/4 two-game days in $n/2-1$ grouping rounds ($r_a,$ $r_b,$ etc.) resulting in $O(n^2 \cdot \text{log}_2 n)$ complexity. The actual games are generated (line 37) using the circle method. Since there are $n-2$ rounds after the first round where the games of the rounds are determined by shifting $n-1$ teams (one team has a fixed position), that complexity is $O(n^2).$ When the rest differences are eliminated via swap operations (lines 38 and 39), n/4 team pairs in the groupings of certain rounds need to be searched among the n/4 groupings (each grouping contains 4 teams) of the previous round to find the positions of the games to be swapped. Since there are $n/2-2$ rounds for which swaps are needed, the resulting complexity is $O(n^3).$ Finally, the day label of each game in each round can be changed with $O(n^2)$ complexity in the aggregation step (line 40). Therefore, the overall complexity of Algorithm 2 is $O(n^3).$ Since, in the worst case, there are n/4 days, the size of the input is $O(n \cdot log_2 n)$ being linear in $O(n^3).$ Thus, the algorithm for the special cases of the $\text{RDP}(n,d)$ is polynomial.