Algorithm to create fair / evenly matched teams based on player rankings

Question

I have a data set of players' skill ranking, age and sex and would like to create evenly matched teams.

• Teams will have the same number of players (currently 8 teams of 12 players).
• Teams should have the same or similar male to female ratio.
• Teams should have similar age curve/distribution.

I would like to try this in Haskell but the choice of coding language is the least important aspect of this problem.

Answer 1

This is a bin packing problem, or a multi-dimensional knapsack problem. Björn B. Brandenburg has made a bin packing heuristics library in Haskell that you may find useful.

You need something like...

data Player = P { skill :: Int, gender :: Bool, age :: Int }

Decide on a number of teams n (I'm guessing this is a function of the total number of players).

Find the desired total skill per team:

teamSkill n ps = sum (map skill ps) / n

Find the ideal gender ratio:

genderRatio ps = sum (map (\x -> if gender x then 1 else 0)) / length ps

Find the ideal age variance (you'll want the Math.Statistics package):

ageDist ps = pvar (map age ps)

And you must assign the three constraints some weights to come up with a scoring for a given team:

score skillW genderW ageW team = skillW * sk + genderW * g + ageW * a
  where (sk, (g, a)) = (teamSkill 1 &&& genderRatio &&& ageDist) team

The problem reduces to the minimization of the difference in scores between teams. A brute force approach will take time proportional to Θ(n^k−1). Given the size of your problem (8 teams of 12 players each), this translates to about 6 to 24 hours on a typical modern PC.

EDIT

An approach that may work well for you (since you don't need an exact solution in practise) is simulated annealing, or continual improvement by random permutation:

1. Pick teams at random.
2. Get a score for this configuration (see above).
3. Randomly swap players between two or more teams.
4. Get a score for the new configuration. If it's better than the previous one, keep it and recurse to step 3. Otherwise discard the new configuration and try step 3 again.
5. When the score has not improved for some fixed number of iterations (experiment to find the knee of this curve), stop. It's likely that the configuration you have at this point will be close enough to the ideal. Run this algorithm a few times to gain confidence that you have not hit on some local optimum that is considerably worse than ideal.

Answer 2

Given the number of players per team and the gender ration (which you can easily compute). The remaining problem is called n-partition problem, which is unfortunately NP-complete and thus very hard to solve exactly. You will have to use approximative or heuristic allgorithms (evolutionary algorithms), if your problem size is too big for a brute force solution. A very simple approximation would be sorting by age and assign in an alternating way.

Answer 3

1. Assign point values to the skill levels, gender, and age
2. Assign the sum of the points for each criteria to each player
3. Sort players by their calculated point value
4. Assign the next player to the first team
5. Assign players to the second team until it has >= total points than the first team or the team reaches the maximum players.
6. Perform 5 for each team, looping back to the first team, until all players are assigned

You can tweak the skill level, gender, and age point values to change the distribution of each.