by Richard A. DeVenezia (02JUN2005), back to round robin
In the guestbook I found:
I would like to host a 12 player "King Of The Beach" Volleyball Tourney. A round robin inside a round robin.
Rules: Each player is partnered once with each of the other 11 players and compete against another partnered pair.
Important: Minimize the number of times any one player competes against any other player.Any suggestions?
- Mark from Huntington Beach, CA
Mark:
I bull headed my way into the problem, the results are below. I also asked a friend to review my bullheaded results:
Hi Richard,
I think I can help. What you are looking for is called a whist tournament.
Definition from the CRC Handbook of Combinatorial Designs.
A whist tournament, Wh(4n), for 4 n players is a schedule of games each consisting of two players opposing two others such that the games are arranged in 4n-1 rounds with the following properties: each round consists of n games; each person plays in exactly one game in each round; each person partners every other person exactly once; and each person opposes every other person exactly twice.
Wh(4n) is known to exist for all values of n>=1. There are easy cyclic constructions for most schedules that are likely to be used in practice. For example:
Game Game Game 12, 1 5, 6 2,11 3, 9 4, 8 7,10 12, 2 6, 7 3, 1 4,10 5, 9 8,11 12, 3 7, 8 4, 2 5,11 6,10 9, 1 12, 4 8, 9 5, 3 6, 1 7,11 10, 2 12, 5 9,10 6, 4 7, 2 8, 1 11, 3 12, 6 10,11 7, 5 8, 3 9, 2 1, 4 12, 7 11, 1 8, 6 9, 4 10, 3 2, 5 12, 8 1, 2 9, 7 10, 5 11, 4 3, 6 12, 9 2, 3 10, 8 11, 6 1, 5 4, 7 12,10 3, 4 11, 9 1, 7 2, 6 5, 8 12,11 4, 5 1,10 2, 8 3, 7 6, 9 Note that the cyclic method is based on the 12 elements (inf,0,1,2,3,4,5,6,7,8,9,10) and mod(11). The first row is a starter block. Generate the subsequent rounds by adding 1 to each element and taking mod (11), with the provision that the infinite element remains the same, i.e infinity+1=infinity. This construction with an infinite element is useful in many other areas of design theory. [ Ed. I replaced inf with 12 and increased each of 0 to 10 by 1 to be 1 to 11; E(r,1)=N, Item(r,c) = (E(r-1,c) mod 11) + 1 ]
Note that you can also have designs for 4n+1 players and 4n+1 rounds where each player sits out during exactly one round of play.
Hope that helps. I could give you the starter blocks for all the cyclic designs in the CRC book. It has Wh(4n) for n upto 12, and Wh(4n+1) for n upto 11.
The approach for this scheduling problem is to start with a 12 player round robin schedule. View each set of two columns as games between two man teams.
1: [ 1, 2] vs [ 3,12] [ 4,11] vs [ 5,10] [ 6, 9] vs [ 7, 8] 2: [ 1, 3] vs [ 4, 2] [ 5,12] vs [ 6,11] [ 7,10] vs [ 8, 9] 3: [ 1, 4] vs [ 5, 3] [ 6, 2] vs [ 7,12] [ 8,11] vs [ 9,10] 4: [ 1, 5] vs [ 6, 4] [ 7, 3] vs [ 8, 2] [ 9,12] vs [10,11] 5: [ 1, 6] vs [ 7, 5] [ 8, 4] vs [ 9, 3] [10, 2] vs [11,12] 6: [ 1, 7] vs [ 8, 6] [ 9, 5] vs [10, 4] [11, 3] vs [12, 2] 7: [ 1, 8] vs [ 9, 7] [10, 6] vs [11, 5] [12, 4] vs [ 2, 3] 8: [ 1, 9] vs [10, 8] [11, 7] vs [12, 6] [ 2, 5] vs [ 3, 4] 9: [ 1,10] vs [11, 9] [12, 8] vs [ 2, 7] [ 3, 6] vs [ 4, 5] 10: [ 1,11] vs [12,10] [ 2, 9] vs [ 3, 8] [ 4, 7] vs [ 5, 6] 11: [ 1,12] vs [ 2,11] [ 3,10] vs [ 4, 9] [ 5, 8] vs [ 6, 7]
This arrangement is from the cyclic algorithm.
Since it is based on a round robin, the arrangement ensures everyone is teamed once with everyone else.
However, the requirement to "minimize the number of times any one player competes against any other player" remains. Consider the matrix that shows how many times each player competes against another player:
1 2 3 4 5 6 7 8 9 10 11 12 -- -- -- -- -- -- -- -- -- -- -- -- 1: . 2 2 2 2 2 2 2 2 2 2 2 2: . . 6 2 . . 2 2 . . 2 6 3: . . . 6 2 . . 2 2 . . 2 4: . . . . 6 2 . . 2 2 . . 5: . . . . . 6 2 . . 2 2 . 6: . . . . . . 6 2 . . 2 2 7: . . . . . . . 6 2 . . 2 8: . . . . . . . . 6 2 . . 9: . . . . . . . . . 6 2 . 10: . . . . . . . . . . 6 2 11: . . . . . . . . . . . 6
The zeros have been replaced with a period (.) to reduce the clutter.
Let's figure out what the heck this matrix means
Examine row 2 column 12. The number 6 indicates that on 6 occassions player 2 competes against a team having player 12 on it. Now look at row 2 column 5. The zero means player 2 never competes against a team having player 5 on it!
Finally, examine the frequency count of the competition pairings. This can be used to consider how balanced or 'fair' the plan is.
1 2 3 4 5 6 7 8 9 10 11 12
-- -- -- -- -- -- -- -- -- -- -- --
0 33 0 0 0 11 0 0 0 0 0 0
On 33 occassions a player competes against some other player twice.
On 11 occassions a player competes against some other player six times!
On no occassion does a player compete against another only once.
Looks like the initial construction is a stinker and yields a plan that all players would recognize as un-balanced.
There is hope. The pairs in each row of the round robin can be randomly arranged without losing the round-robiness and a 'score' for the rearranged schedule can be computed. The score would tell:
Here are the frequencies from some select plans where everyone competes against everyone else. Notice how the F1 number increases.
f1 2 3 4 5 6 7 8 9 10 11 12
-- -- -- -- -- -- -- -- -- -- -- --
26 23 10 5 2 0 0 0 0 0 0 0
29 20 9 4 4 0 0 0 0 0 0 0
30 18 9 7 1 1 0 0 0 0 0 0
33 16 8 6 1 1 0 1 0 0 0 0
The numbers were taken from a simulation that randomly arranged the pairs within row. Two million randomized schedules were examined. When F1 increased, a plan was considered 'better' than any previous plan. Now look at the last row, 33 single pairings, 16 cases where two players meet twice, and 8 cases where some players meet thrice, etc.. upto 1 case where two players meet 8 times!
It's sort of like squeezing a water balloon. As you tighten up in one place, the numbers have to flop out in another.
8 times might be appropriate if you have two high energy players with a personal grudge, and you want everyone to be able to experience that intensity as they 'play along' with the two super-egos. If not, use an earlier selected plan.
Richard A. DeVeneziaThese are the plans for the four frequencies listed above. A computer program selected them as the 'first encountered highest 1 count' while examining 2 million randomized plans.
Team A Team B Team C Team D Team E Team F
-------------- -------------- --------------
3 12 1 2 4 11 6 9 5 10 7 8
1 3 8 9 4 2 7 10 5 12 6 11
7 12 5 3 9 10 8 11 6 2 1 4
7 3 1 5 10 11 6 4 8 2 9 12
10 2 11 12 1 6 7 5 8 4 9 3
12 2 8 6 10 4 1 7 11 3 9 5
2 3 11 5 10 6 1 8 12 4 9 7
11 7 10 8 1 9 2 5 12 6 3 4
3 6 1 10 2 7 11 9 12 8 4 5
1 11 3 8 12 10 2 9 4 7 5 6
2 11 1 12 4 9 6 7 3 10 5 8
Competition matrix
1 2 3 4 5 6 7 8 9 10 11 12
-- -- -- -- -- -- -- -- -- -- -- --
1: . 3 4 1 2 3 2 2 1 2 1 1
2: . . 1 1 1 1 1 1 3 2 3 5
3: . . . 1 4 1 1 3 2 1 2 2
4: . . . . 1 5 4 1 3 2 1 2
5: . . . . . 2 4 2 1 1 2 2
6: . . . . . . 2 1 1 2 2 2
7: . . . . . . . 1 2 3 1 1
8: . . . . . . . . 3 4 2 2
9: . . . . . . . . . 1 3 2
10: . . . . . . . . . . 3 1
11: . . . . . . . . . . . 2
12: . . . . . . . . . . . .
Frequency counts
1 2 3 4 5 6 7 8 9 10 11 12
-- -- -- -- -- -- -- -- -- -- -- --
26 23 10 5 2 0 0 0 0 0 0 0
Team A Team B Team C Team D Team E Team F
-------------- -------------- --------------
4 11 6 9 3 12 7 8 1 2 5 10
5 12 4 2 8 9 7 10 1 3 6 11
1 4 7 12 9 10 6 2 5 3 8 11
6 4 1 5 8 2 10 11 7 3 9 12
8 4 9 3 10 2 7 5 1 6 11 12
10 4 11 3 9 5 1 7 8 6 12 2
2 3 11 5 9 7 12 4 10 6 1 8
11 7 12 6 2 5 3 4 10 8 1 9
2 7 1 10 12 8 4 5 3 6 11 9
4 7 12 10 1 11 3 8 5 6 2 9
3 10 1 12 5 8 4 9 2 11 6 7
Competition matrix
1 2 3 4 5 6 7 8 9 10 11 12
-- -- -- -- -- -- -- -- -- -- -- --
1: . 1 2 1 2 3 2 2 1 4 2 2
2: . . 1 1 5 3 2 1 1 4 2 1
3: . . . 2 2 1 1 3 2 1 5 2
4: . . . . 4 1 2 2 3 1 1 4
5: . . . . . 1 1 2 2 1 1 1
6: . . . . . . 1 1 3 1 5 2
7: . . . . . . . 1 3 3 1 5
8: . . . . . . . . 3 3 2 2
9: . . . . . . . . . 2 1 1
10: . . . . . . . . . . 1 1
11: . . . . . . . . . . . 1
12: . . . . . . . . . . . .
Frequency counts
1 2 3 4 5 6 7 8 9 10 11 12
-- -- -- -- -- -- -- -- -- -- -- --
29 20 9 4 4 0 0 0 0 0 0 0
Team A Team B Team C Team D Team E Team F
-------------- -------------- --------------
1 2 5 10 7 8 4 11 3 12 6 9
7 10 1 3 4 2 8 9 6 11 5 12
1 4 6 2 8 11 7 12 5 3 9 10
7 3 8 2 9 12 1 5 10 11 6 4
7 5 11 12 8 4 1 6 10 2 9 3
11 3 9 5 1 7 12 2 10 4 8 6
10 6 11 5 1 8 9 7 2 3 12 4
12 6 2 5 11 7 1 9 3 4 10 8
4 5 12 8 11 9 3 6 2 7 1 10
5 6 4 7 12 10 3 8 2 9 1 11
3 10 1 12 4 9 5 8 6 7 2 11
Competition matrix
1 2 3 4 5 6 7 8 9 10 11 12
-- -- -- -- -- -- -- -- -- -- -- --
1: . 4 1 1 1 1 4 1 3 3 1 2
2: . . 2 2 1 2 3 1 2 2 1 2
3: . . . 1 1 1 1 2 4 5 1 3
4: . . . . 2 4 1 6 1 2 1 1
5: . . . . . 3 1 1 3 2 3 4
6: . . . . . . 1 1 1 2 4 2
7: . . . . . . . 3 1 1 4 2
8: . . . . . . . . 2 2 1 2
9: . . . . . . . . . 1 3 1
10: . . . . . . . . . . 1 1
11: . . . . . . . . . . . 2
12: . . . . . . . . . . . .
Frequency counts
1 2 3 4 5 6 7 8 9 10 11 12
-- -- -- -- -- -- -- -- -- -- -- --
30 18 9 7 1 1 0 0 0 0 0 0
Team A Team B Team C Team D Team E Team F
-------------- -------------- --------------
3 12 7 8 4 11 1 2 5 10 6 9
7 10 1 3 6 11 5 12 8 9 4 2
6 2 5 3 9 10 8 11 7 12 1 4
6 4 7 3 8 2 9 12 1 5 10 11
9 3 1 6 10 2 11 12 7 5 8 4
9 5 8 6 12 2 10 4 1 7 11 3
11 5 10 6 2 3 12 4 9 7 1 8
3 4 11 7 12 6 2 5 1 9 10 8
4 5 3 6 12 8 11 9 2 7 1 10
2 9 4 7 1 11 5 6 3 8 12 10
3 10 4 9 1 12 2 11 5 8 6 7
Competition matrix
1 2 3 4 5 6 7 8 9 10 11 12
-- -- -- -- -- -- -- -- -- -- -- --
1: . 2 2 1 1 1 4 1 2 3 4 1
2: . . 1 4 1 1 1 1 2 2 2 5
3: . . . 4 1 3 4 1 1 2 1 2
4: . . . . 1 1 4 1 2 1 1 2
5: . . . . . 8 1 2 1 2 3 1
6: . . . . . . 1 1 2 1 2 1
7: . . . . . . . 3 1 1 1 1
8: . . . . . . . . 6 2 1 3
9: . . . . . . . . . 3 1 1
10: . . . . . . . . . . 3 2
11: . . . . . . . . . . . 3
12: . . . . . . . . . . . .
Frequency counts
1 2 3 4 5 6 7 8 9 10 11 12
-- -- -- -- -- -- -- -- -- -- -- --
33 16 8 6 1 1 0 1 0 0 0 0