1
$\begingroup$

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?

  • 0
    $S$huffling the list of $p$artici$p$ants before randomly assigning them should do it.2011-04-26

1 Answers 1

2

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.

  • 0
    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.2011-04-28