The question of for court balance in round robins has cropped up a lot. Below is an algorithm that can produce court balance some of the time, also some recommended further reading for those interested.
Ian Wakeling.
Be sure to check out Ian's Excel file or Richard's pageIn many different sports a round robin can be used to schedule
n players (or teams) who meet weekly, fortnightly, or monthly at a central location where enough courts are available for playing each round. Some examples would be tennis, squash, bocce, pool, curling etc. In many, if not all, of these sports it is possible that a court has some unique characteristic specific to how it was constructed, or where it is situated. One player or team who plays often on one court may gain an unfair advantage by learning to use its characteristics, perhaps its uneveness, to improve their chances of winning. To avoid this problem, it is sensible to try to balance the number of times a player plays on each court in the course of the competition.
If
n is odd follow
Richard's cyclic algorithm for constructing the round robin for
n+1 players. Player 1 is then assigned as the ghost player and any player partnered with the ghost is given a bye, then the schedule has a natural court balance with each team playing exactly twice at each court.
Example
n=7. First consider the cyclic schedule for 8 players.
court
1 2 3 4
round
1 ( 1 2 ) ( 3 8 ) ( 4 7 ) ( 5 6 )
2 ( 1 8 ) ( 2 7 ) ( 3 6 ) ( 4 5 )
3 ( 1 7 ) ( 8 6 ) ( 2 5 ) ( 3 4 )
4 ( 1 6 ) ( 7 5 ) ( 8 4 ) ( 2 3 )
5 ( 1 5 ) ( 6 4 ) ( 7 3 ) ( 8 2 )
6 ( 1 4 ) ( 5 3 ) ( 6 2 ) ( 7 8 )
7 ( 1 3 ) ( 4 2 ) ( 5 8 ) ( 6 7 )
The players highlighted in purple are given the bye at each round, so these matches with player 1 from the 8 player tournament are never played and court 1 is not needed. Matches in courts 2, 3 and 4 all derive from the non-fixed positions in the cyclic algorithm, so it should be no surprise that each column contains all 7 players ( 2 to 8 ) exactly twice. It only remains to map players 2 to 8, back to 1 to 7 to give the 7 player court balanced tournament schedule.
If n is even, and is a member of the infinite series 8,14,20,26,32,... [
n=6
i +2: i>=1] or a member of the series 6,12,18,24,30,36,... [
n=6
i : i>=1] then there is a simple modification to the cyclic algorithm that can give the necessary court balance. In essence this is the method of Haselgrove and Leach (1977), see this
article by Jeff Dinitz for a description of a similar algorithm.
(1) Begin with the first round using the standard cyclic algorithm.
(2) Generate subsequent rounds by rotating the players (
n/2)-1 positions, rather than just a single position.
(3) Stop when (
n-1) rounds have been obtained. This gives exactly the same rounds as the cyclic algorithm but in a different order.
(4) Number the rounds of the modified schedule as
r=1...(
n-1). Now court balance may be obtained by making the following adjustments:
for
r=1...(
n/2)-1, swap over pairs from courts 1 and
r+1.
for
r=
n/2...
n-2, swap over pairs from courts 1 and
n-
r.
for
r=
n-1, leave the round unchanged.
Example
n=8. Since (8/2)-1=3, every third row from the cyclic schedule above is used in the construction of the reordered schedule below. Note that after the seventh row the first row is considered to be next. So
r=1...7 below, corresponds with
round=1,4,7,3,6,2,5 above.
court
1 2 3 4
r
1 ( 1 2 ) ( 3 8 ) ( 4 7 ) ( 5 6 )
2 ( 1 6 ) ( 7 5 ) ( 8 4 ) ( 2 3 )
3 ( 1 3 ) ( 4 2 ) ( 5 8 ) ( 6 7 )
4 ( 1 7 ) ( 8 6 ) ( 2 5 ) ( 3 4 )
5 ( 1 4 ) ( 5 3 ) ( 6 2 ) ( 7 8 )
6 ( 1 8 ) ( 2 7 ) ( 3 6 ) ( 4 5 )
7 ( 1 5 ) ( 6 4 ) ( 7 3 ) ( 8 2 )
Following step 4 in the modified algorithm identifies the matches in rounds 1 to 6 that are highlighted in red above. Finally swap these matches over with the blue matches in the first column.
court
1 2 3 4
r
1 ( 3 8 ) ( 1 2 ) ( 4 7 ) ( 5 6 )
2 ( 8 4 ) ( 7 5 ) ( 1 6 ) ( 2 3 )
3 ( 6 7 ) ( 4 2 ) ( 5 8 ) ( 1 3 )
4 ( 3 4 ) ( 8 6 ) ( 2 5 ) ( 1 7 )
5 ( 6 2 ) ( 5 3 ) ( 1 4 ) ( 7 8 )
6 ( 2 7 ) ( 1 8 ) ( 3 6 ) ( 4 5 )
7 ( 1 5 ) ( 6 4 ) ( 7 3 ) ( 8 2 )
Before this is done player 1 plays all their matches on court 1, but afterwards they are distributed as evenly as possible. Remarkably, on any court the two underlined players play once, all other players play twice, so the best possible court balance has been found.
A court balanced tournament schedules is not possible for 4 players. However schedules for the infinite series n=10,16,22,28,34,... [
n=6
i +4 : i>=1] do exist. Their construction is much harder and involves some graduate level combinatorial mathematics, see Anderson (1997).
Further Reading
Anderson, I. 1997 "Combinatorial designs and tournaments", Clarenden Press Oxford.
Dinitz, J.H. "Designing Schedules for Leagues and Tournaments"
Haselgrove, J. and Leach, J. 1977 "A tournament design problem", Am. Math. Monthly, 84, 198-201
