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

Lets say you have six players (for a simple example). We can use the same algorithm which pairs opponents in single-elimination tournaments and adapt that to generate "even" teams based on any criteria you choose.

First rank your players best-to-worst. Don't take this too literally. You want a list of players sorted by the criteria you wish to separate them.

Why?

Let's look at single elimination tournaments for a second. The idea of using an algorithm to generate optimal single-elimination matches is to avoid the problem of the "top players" meeting too soon in the tournament. If top players meet too soon, one of the top players will be eliminated early on, making the tournament less interesting. We can use this "optimal" pairing to generate teams in which the "top" players are spread out evenly across the teams. Then spread out the the second top players, etc, etc.

So list you players by the criteria you want them separated: men first, then women... sorted by age second. We get (for example):

Player 1: Male - 18
Player 2: Male - 26
Player 3: Male - 45
Player 4: Female - 18
Player 5: Female - 26
Player 6: Female - 45

Then we'll apply the single-elimination algorithm which uses their "rank" (which is just their player number) to create "good match ups".

The single-elimination tournament generator basically works like this: take their rank (player number) and reverse the bits (binary). This new number you come up with become their "slot" in the tournament.

Player 1 in binary (001), reversed becomes 100 (4 decimal) = slot 4
Player 2 in binary (010), reversed becomes 010 (2 decimal) = slot 2
Player 3 in binary (011), reversed becomes 110 (6 decimal) = slot 6
Player 4 in binary (100), reversed becomes 001 (1 decimal) = slot 1
Player 5 in binary (101), reversed becomes 101 (5 decimal) = slot 5
Player 6 in binary (110), reversed becomes 011 (3 decimal) = slot 3

In a single-elimination tournament, slot 1 plays slot 2, 3-vs-4, 5-vs-6. We're going to uses these "pair ups" to generate optimal teams.

Looking at the player number above, ordered by their "slot number", here is the list we came up with:

Slot 1: Female - 18
Slot 2: Male - 26
Slot 3: Female - 45

Slot 4: Male - 18
Slot 5: Female - 26
Slot 6: Male - 45

When you split the slots up into teams (two or more) you get the players in slot 1-3 vs players in slot 4-6. That is the best/optimal grouping you can get.

This technique scales very well with many more players, multiple criteria (just group them together correctly), and multiple teams.

Answer 3

Well,

My answer is not about scoring strategies of teams/players because all the posted are good, but I would try a brute force or a random search approach. I don't think it's worth create a genetic algorithm.

Regards.

Answer 4

Almost trivial approach for two teams:

1. Sort all player by your skill/rank assessment.
2. Assign team A the best player.
3. Assign team B the next two best players
4. Assign team A the next two best players
5. goto 3
6. End when you're out of players.

Not very flexible, and only works on one column ranking, so it won't try to get similar gender or age profiles. But it does make fair well matched teams if the input distribution is reasonably smooth. Plus it doesn't always end with team A have the spare player when there are an odd number.

Answer 5

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.

Answer 6

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 7

Idea:

1. Sort players by skill
2. Assign best players in order (i.e.: team A: 1st player, team B: 2nd player, ...)
3. Assign worst players in order
4. Loop on 2
5. Evaluate possible corrections and perform them (i.e.: if team A has a total skill of 19 with a player with skill 5 and team B has a total skill of 21 with a player with skill 4, interchange them)
6. Evaluate possible corrections on gender distribution and perform them
7. Evaluate possible corrections on age distribution and perform them