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 page (https://www.devenezia.com/downloads/round-robin/rounds.php?v=b1)
In 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 (https://www.devenezia.com/downloads/round-robin/index.html) 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=6i +2: i>=1] or a member of the series 6,12,18,24,30,36,... [n=6i : 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 (http://www.emba.uvm.edu/~dinitz/preprints/design_tourney_talk.pdf) 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=6i +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
Hi Fred,
Thanks for your message. The book is not going to help with schedules where the number of courts are restricted, I referred to it as it gives enough detail to construct the full BTD when the number of players is 6i+4. If you do want these schedules then I have made the constructions for you, just follow the link above for "Ian's Excel File". At least the 10 player, 5 court BTD may be of some use.
I have not followed up the references on the combinatorics of CBTDs or TAs, but clearly if you are having problems then you need to refer back to the original Mendelsohn and Rodney paper. When I have needed schedules like this I find that an exchange algorithm works fine and can produce superior schedules to the ones I have seen. In particular I think it is essential that the distribution of the byes is considered. For example, look at the plan for CBTD(10,3) that you refer to above; players 1, 2, & 3 have no byes in the first 6 rounds, while players 4 & 5 get 4 byes each. This is so uneven that I think you might get complaints from the players if you used the schedule for a league. It is possible to do much better:
(E J) (C H) (B G)
(F I) (A D) (E H)
(B D) (F G) (C J)
(E I) (G H) (A B)
(C D) (A I) (F J)
------------------
(C E) (B J) (H I)
(A G) (D H) (E F)
(B C) (A J) (G I)
(A H) (B E) (D F)
(G J) (C F) (D I)
------------------
(B I) (D E) (C G)
(H J) (B F) (A E)
(D G) (I J) (A C)
(A F) (E G) (B H)
(F H) (C I) (D J)
Above the 10 players play exactly 3 times on each court and exactly 3 times in each block of 5 rounds. There is also a minimal number of back-to-back games within the blocks of 5 rounds, I believe.
Some of the schedules you are looking for can be found directly by slicing up BTDs, for example just take the BTD for 12 players and form two rounds from each of the 11 rounds. So games played on courts 4,5 & 6 in round 1 are played instead on courts 1,2 & 3 in round 2.
Let me know (on or off-line) if there are specific schedules that you are interested in finding.
Ian.