Algorithm - Attempting to balance out team skill levels, while having a equal amount of players

Question

I have 3 teams, They have 2 players, 3 players and 7 players. There is 18 players sitting on the sidelines waiting to be assigned.

Each player has their own skill level, meaning a level 1 is not going to defeat a level 10.

I want to balance the teams out to 10 players each. And I want to try get all 3 teams as equal in skill as I can. But I don't want to remove the players already in a team.

But I'm not sure how I would accomplish this. I'm also not sure if there is a easy answer, or if this would be expensive to compute.

The skill level is a number which I already have. The teams all have a equal amount of players. Which means the skill level is the only varying number.

A example is. Team 1 has 3 players and a total skill level of 4. Team 2 has 6 players and a total skill level of 8. Team 3 has 8 players and a total skill level of 9.

I have 13 players who need to be assigned so the teams are 10 players each. And I want to try match up the total skill levels.

Answer 1

This reads to me like you are trying to partition a (multi)set of numbers (the "skill levels") into blocks of equal size ("teams") so that the averages ("total skill level") are as close to equal as possible.

To solve this, I would begin by computing the average skill level, which is the sum of the skill levels divided by the number of players, call this number s. If there are to be m teams total, each with k players, giving a total of m*k players, then the target skill level for each teams is k*s.

Since your teams are already partially filled, the problem you have based on your example

I have 3 teams, They have 2 players, 3 players and 7 players. There is 18 players sitting on the sidelines waiting to be assigned.

is the following:

• Team A, with current skill level a, needs 8 players such that p1 + ... + p8 + a = 10*s
• Team B, with current skill level b, needs 7 players such that q1 + ... + q7 + b = 10*s
• Team C, with current skill level c, needs 3 players such that r1 + r2 + r3 + c = 10*s

For a brute force solution, find the players for Team C first, then use the remaining players to solve for Teams A and B.

For a more clever solution, you need to realize that this is really a subset sum problem, and use one of the well-known algorithms for solving that. I recommend the dynamic programming solution as described in the linked article.

Answer 2

it is impossible to give a solid answer here, because what really matters is how accurate the ranking scheme is, and if it satisfies some logical properties.

Additivity: If the ranking is a perfect one, then it will probably be additive in some sense. My thinking comes from bridge, but any task where the players can be ranked and can form groups would apply. So it would be nice if a rank 10 and rank 1 player, when teamed up, would be a good match for a pair formed from rank 5 and 6 players. (Bridge rankings might be more accurately additive in a log sense, from what I have read.)

Synergy: Do some work together better than others in a group? Again, this is a ranking issue, because your ranking with one person might be better than with others. There is often a synergy aspect here. Avoiding bridge as the example, golf is what comes to mind. Put two people together on a golf course, if one person is the type who constantly is talking, while the other needs silence to concentrate, then logically they will play together poorly.

Answer 3

A pragmatic approach that will get you a good answer is to assign the highest ranked player to the lowest-ranked team until all players are assigned, where you compute a team's rank by summing its players' ranks.