8
$\begingroup$

I am randomly assigning people to play on different golf teams each week. I have 7 teams, each with 4 players.

My starting list is ordered alphabetically by last name.

I’m using a random number generator based on atmospheric noise to assign people each week. However, I do get people together on the same team a few weeks in a row.

How can I reduce the number of times 2 or more people are randomly assigned to the same team? Should I randomize the starting list then randomize the teams?

$\endgroup$
6
  • $\begingroup$ Does it need to be random? You could keep track of the teams from week to week, and assign everyone to a new configuration weekly (until that becomes impossible; then restart). $\endgroup$
    – Sycorax
    Jan 7 at 16:11
  • 5
    $\begingroup$ You can guarantee that no 2 people are assigned to the same team on consecutive weeks by rejecting all random assignments that do so. $\endgroup$
    – Sycorax
    Jan 7 at 17:37
  • 2
    $\begingroup$ I think this post (not on Cross Validated) discusses a similar (if not the identical) problem. $\endgroup$ Jan 7 at 18:33
  • 1
    $\begingroup$ For this problem, I believe the best solution is rejection sampling. But if you want to see how deep this rabbit hole goes, consider that Spotify faced a similar problem in the form of user feedback about its shuffle algorithm that caused them to implement a new shuffler that incorporates dithering. This is an Ok coverage of the topic medium.com/immensity/…; I read a better one some years ago but I can't find it now. $\endgroup$
    – Sycorax
    Jan 7 at 19:09
  • 2
    $\begingroup$ As you might expect, this is the social golfer problem. There is a solution (or apparently 4466 solutions) where no pairs repeat in 9 rounds two-thirds of the way down Ed Pegg Jr's note. You can make this random-ish by allocating the $28$ places at random and ordering the rounds at random - and the only way of spotting that there is some control is the lack of repeats $\endgroup$
    – Henry
    Jan 8 at 1:40

1 Answer 1

9
$\begingroup$

Your problem seems to be twofold: people notice when they have a common partner two weeks (rounds) in a row. They also notice when they have a common partner frequently. As it turns out, limiting the former possibility also keeps the latter rate low. So, let's solve the first problem.

A quick and simple solution is rejection sampling. The way it works here is to conceive of your assignment for a round as being a random sample of all possible assignments (of which there are over $10^{16}$), a set $\Omega.$ After any number $r$ of rounds, suppose you have specified selection probabilities for every possible assignment, based somehow on the results of the previous rounds. To generate the team assignments for the next round, you repeatedly draw an assignment $\omega$ from $\Omega,$ compare its selection probability $\Pr(\omega)$ to a randomly generated probability $U,$ and accept that assignment when $U\le \omega.$

Perhaps the simplest example of this is to set the selection probabilities to zero for any assignment that would pair two teammates who had just played together in the previous round. The algorithm will either not terminate (because no random selection meeting your criteria is possible) or it will yield a satisfactory assignment. Here is an example of the first two rounds of such a schedule showing the first and second values of $\omega$ that were (randomly) selected:

, , Round = 1

      Team
        1  2  3  4  5  6  7
  [1,]  4 15  6  3  1  2 11
  [2,]  5 16 13  8  7 14 12
  [3,]  9 24 18 19 10 22 23
  [4,] 25 27 21 20 17 26 28

, , Round = 2

      Team
        1  2  3  4  5  6  7
  [1,]  3  2 16  6  9  1 10
  [2,]  5  8 17 11 19  4 20
  [3,]  7 12 18 15 26 21 23
  [4,] 14 13 25 22 27 28 24

You may check, by inspection, that no pair of people teamed in the first round were teamed again in the second round.

Another version of this would be to keep track of how often each pair of people has been teamed in the past and reduce the selection probabilities in inverse proportion to these frequencies. This is one way to minimize the rate of assignments to the same team, but by itself does not solve the first problem of having a common partner two weeks in a row.

Here is a summary of the results of the simplest procedure, run for 52 rounds.

Figure

There were $6$ pairs who never played together, $16$ who played together once, $38$ who played together twice, ..., and $1$ pair who played together in thirteen of the 52 rounds. And of course, by construction, nobody ever had a common teammate two rounds in a row.

On average, each person played with any specific other person less than six times (because there are $28-1=27$ other people available and $4-1=3$ others in one's team, for an average chance of teaming with someone equal to $3/27=1/9$ per round; and $52/9 \lt 6.$) The distribution of these pair counts is remarkably similar to a Poisson distribution of rate $52/9.$ This relationship makes the distribution of pair counts predictable before you ever generate a schedule.

Another nice feature of this approach is that it is "online" in the sense that you can apply it, without any modification, to extend an existing schedule.


This R code generated the example and the figure.

pick <- function(n, k) matrix(sample.int(n*k, n*k), n)
evaluate <- function(X, A) max(apply(X, 1, function(x) max(A[x, x]))) > 0
update <- function(X, A) {
  I <- t(matrix(apply(X, 1, combn, m=2), 2))
  A[I] <- A[I] + 1 # Increment pair counts
  A
}    
n <- 7                   # Number of teams
k <- 4                   # Players per team
N <- 52                  # Number of rounds to schedule
A <- matrix(0, k*n, k*n) # Tracks the pairings from the previous round
Schedule <- array(NA, c(k, n, N), dimnames=list(Position=1:k, Team=1:n, Round=1:N))
set.seed(17)
for (round in 1:N) {
  while(evaluate(X <- pick(n, k), A)) {} # Rejection sampling
  A <- update(X, matrix(0, k*n, k*n))    # Record the results for future selections
  Schedule[,,round] <- t(X)              # Save this assignment in the schedule
}
Schedule2 <- apply(Schedule, c(2,3), sort) # Make the schedule easier to read
(Schedule2[,,1:2])                         # Inspect it
#
# Plot a summary of this schedule.
#
check <- function(Schedule) {
  stopifnot(unique(apply(Schedule, 3, function(x) length(unique(c(x))))) == n*k)
  Pairs <- matrix(apply(Schedule, 3, function(S) apply(S, 2, combn, m=2)), 2)
  A <- table(Pairs[1, ], Pairs[2, ])
  table(A[lower.tri(A)] + t(A)[lower.tri(A)])
}
y <- c(check(Schedule))
i <- as.numeric(names(y))
plot(i, y, type="h", lwd=2, ylim=c(0, max(y)),
     main=paste("Common Teammate Frequencies in", N, "Rounds"))
$\endgroup$
4
  • $\begingroup$ I wonder whether a solution with $9k$ rounds is possible for some small $k<7$ where each person plays with any other exactly $k$ times. Or of it is not possible for $k<7$ whether the variance can be reduced a lot more than with this random assignment that only takes care of not playing twice in a row with the same person. $\endgroup$ Jan 7 at 22:52
  • $\begingroup$ @SextusEmpiricus It is possible with $k=1$ for each the $28$ players to play once with each of the other $27$ over $9$ rounds. $\endgroup$
    – Henry
    Jan 8 at 15:26
  • $\begingroup$ @Henry do you have a proof of that? $\endgroup$ Jan 8 at 16:49
  • 1
    $\begingroup$ @SextusEmpiricus See two-thirds of the way down Ed Pegg Jr's note for one such arrangement. $\endgroup$
    – Henry
    Jan 8 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.