I'm struggling with an algorithm to divide a group of contestants into smaller groups to make up rounds. Take for example a group of $20$ people, which I want to divide into $3$ groups $(7,7,6).$ For each round in a contest, the groups are different, so that everybody has to combat everybody else in a rather fair distribution.

The problem is that with a (naive) random selection one person has to combat the same person more then another one. I.e. Two elements end up often in the same group.

I would like to make this more fair so that for a given number of contestants, group size (not all groups are the same size) and number of rounds, the algorithm finds a fair set of groups per round so that on average every contestant has the same odds of meeting the same contestant during the rounds.

Is there any literature on this topic I can consult? Or any known algorithms?

  • 1
    $\begingroup$ This sounds like an exercise in number theory or combinatorics rather than probability or randomness. You would only use probability if your constraints didn't fully determine what the solution was. $\endgroup$ – probabilityislogic Apr 26 '11 at 13:17
  • $\begingroup$ How many rounds are there? Do the three groups compete against each other, or do the people compete against each other within the groups? $\endgroup$ – GaBorgulya Apr 26 '11 at 13:38
  • $\begingroup$ The amount of rounds varies from 6 to let's say 20. It depends on the number of participants and the duration of the contest. Typically a round takes 15 minutes per group. If a contest takes 6 hours, we can have 4 groups and 6 rounds. Groups around 7 to 10 people are OK. People compete against each other. $\endgroup$ – Johan Apr 26 '11 at 13:44
  • $\begingroup$ How do you mean "people compete against each other"? Could you be more specific? Taking a round with a group of 7 people does this mean that there are $7\cdot 6 / 2 = 21$ competitions run? $\endgroup$ – GaBorgulya Apr 26 '11 at 13:47
  • $\begingroup$ As an example, take 20 competitors and assume we have a contest with 6 rounds. Each round consists of a different task that must be completed. The 20 competitors are divided into 3 groups: 7,7 and 6. The groups vary per round, so you do not compete against the same people all the time. This means there are 3*6 = 18 competitions run. The question is to come up with an algorithm to make this as fair as possible... $\endgroup$ – Johan Apr 26 '11 at 14:28

Perfectly balanced is clearly not achievable in all cases: suppose you do four rounds for four people in two groups, then everybody gets to play one opponent at least twice and another opponent at most once. So now we can discuss what, exactly, is an achievable goal.

Consider for each pair of people the number of rounds in which they are in the same group (i.e., the number of times they play each other). We would want this multiset $S$ of numbers to consist of numbers that are close to each other. We might, for example, try to have $\max S - \min S \leq 1$ (that is, if $A$ plays $B$ $n$ times, then $C$ plays $D$ at most $n + 1$ and at least $n - 1$ times). (Caveat - at this point it is not clear to me that this is always possible.) Or we might try to have the variance of the $S$ be minimal. Finally, we could try to minimize the variance subject to the min / max condition.

If the groups would be the same size, then you might be able to use block designs to achieve perfect balance (where $S$ is constant) for some sets of parameters. Otherwise, however, I think there is no theory that gives you an exact solution to this problem. It may well be that the most practical way to solve this is using a meta-heuristic such as Simulated Annealing or Tabu Search.

| cite | improve this answer | |
  • $\begingroup$ This answer pointed me in the right direction in the search for algorithms. Being a (classic) engineer, I'm more a pragmatist then a theoreticus... so I'm going for an approximation using random selection and a filter on the result set. $\endgroup$ – Johan Apr 28 '11 at 21:39

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.