Balancing Teams base on Skill

Suppose you had a set of players for a game and you had to build teams based on those players. Assume that you also had to try to make the teams as evenly matched as possible. The first thing to do is to establish a player skill rating. Let's say we could assign a skill rating of 1 to 5, where 1 is a really good player and 5 is the opposite side of the scale. Now, all we have to do is determine how many players we can have on each team. And we can sort the players by skill and put them on the teams. Seems simple enough. But wait! There's more.

What if we had 20 teams and only had two players with a skill rating of 1? If we were using a loop to assign players, then team 1 and 2 would get those players and the rest of the teams would get 2. Wouldn't everyone want to get team 1 because that team would always get the best players. This is something we have to solve.

Let's add another restriction. A few players can only be on certain teams. Let's assume this is because of scheduling or some other valid reason. They are put on teams even before the process even begins. These players can be any skill level.

Furthermore, let's say that there is a certain position in the game where players are scarce. For example, the quarterback in football or goal keeper in soccer. We want to make sure that every team has one of these key players if possible. Of course, if there are not enough of the scarce player, we may not be able to do anything about it. Let's assume that it is acceptable just to do our best.

How would we handle this from an algorithm stand point?

We will use a clustering strategy to assign players. We talked about this before. It simply means to take all the players and put them into clusters based on their skill level. Then they are assigned to teams based on cluster. This can be done by sorting by skill level.

We will keep a data structure, which we call cluster data, for each team which contains the number of players of each skill level that each team should have and what they actually have. We will first analyze the list of players and take each skill level cluster and divide it by the number of teams. We will round the resulting number up to the nearest integer. This means if we have 20 teams, and two 1 players, we divide 20 by 2 and round up which gives us 1. We then say that each team should have 1 player rated 1. While we know that we cannot achieve this, we can use this data to assign better players to those teams before we give players to the teams that do get those very skilled players.

We load all the players, and initialize our data structure based on players that were put on the team in advance.

Then we go about assigning the scarce skill players one team at a time. We process teams in random order so we don't favor anyone. While we do this, we update the cluster data appropriately.

We are now ready to assign the rest of the players. We take each cluster that still has available players and start with the highest skill level. Take a player, then find the team with the most need at that point. The team with the most need will be done by calculating a score based on what the team should have and what the team actually has. We assign a "need" value for each skill level, with most skilled getting a value of 20, followed by 16, 12, 8, 4. We take the list of should have for each skill level up to the skill level we are currently processing and subtract the 'has' from the 'should have' then multiply by the 'need' value. This will result in a negative number most of the time, especially early in the algorithm.

If a team has a 1 and should have a 1, then that need score is zero. If the second team has no 1 player but should have 1 player (because the should have value for all teams for all skill levels is the same), then that gives us -1 times 20, which is -20. Assuming that we are assigning level 2 players, and team 2 has none of those yet, team 2 score (-20) is less than team 1. Using this approach, we go through all the teams and find the team with the lowest need score. Then we put that player on the team, update the cluster data and move onto the next team. We repeat this process until all the players are exhausted or all teams are full.

I discussed a possible team balancing algorithm that can create teams balanced based on skill. I showed how that can use some level of complexity to accomplish a very flexible approach to getting teams that are evenly matched.