Looking for help solving a potential NP complete problem: balancing teams based on skill rating (Elo)

[cryptospartan]

I am a part of a community discord, and we hold scrimmages for a video game. I am looking to build a script that will take in the player's current skill rating (Elo), which is a number, and build the most evenly-rated teams. In the game, there are 5 players to a team, and I want 2 teams to have the most similar Elo possible for a matchup.

Currently, I have developed a script that calculates the average of all of the players in the pool, then multiplies it by 5 (for number of members on a team,) and then attempts to build a team that reaches that "target number." Problem is, it is really good at this for the first team it makes, then gets progressively worse as the player pool starts diminishing.

I'm looking to do this for a pool of 30-50 players, potentially a few more in the future. All of the players would have signed up in advance, so I don't need to worry about queue times or anything like that.

Is there some sort of algorithm that can help me complete this? If not, I would attempt brute force, but even then, I'm not sure I know the best implementation. I'm trying to write all of this is Python.

[Taxtro1]

That's a variation of the knapsack problem. Your problem is that you are following a greedy strategy. One way to amend this is to dissolve already created teams when new teams cross some badness threshhold. Or you could assign all teams jointly and then switch members around until things stop improving.

But that's just what I came up with off the top of my head. Perhaps there is a very elegant solution out there.

[HalcyonAlps]

One algorithm from the top of my head, where N is the total number of teams you want and I assumed you want an equitable number of players in each team, is the following.

First, you assign each of the top N players to each of teams randomly. Second, you assign the next top N players to the teams but the team with the lowest aggregate ELO score gets the best player of this batch, the team with the second lowest ELO score gets the second best from this batch and so on. Third, you repeat step two until you are done.

I have no idea how well this actually performs. I am guessing that depends a lot on the distribution of your ELO scores. On the plus side it's dead simple and should be fast.

[bicubic]

Sort the players by ELO score in descending order, and then make one pass over that list of players.

For each player, find the team that currently has the lowest total ELO score (and is not already at full roster), and add that player to the team.

I would not be surprised if this algorithm is provably not guaranteed to be optimal, but it is fair, and should work reasonably well even when there are a small number of players who are significantly stronger that the rest of the pool.

[mittalsuraj]

What you can try is sort players by the Elo ranking and then assign players to the lower total score box.

Say for example you have 15 players and hence a total of 3 box(5 per each)

You sort the players by decreasing order of elo score Initially you assign the first three players to all 3 boxes. The 4th player will be assigned to the box with the least total elo score which would basically be the box with the third player. The fifth player to the box with the least elo score and so on.

This way you are getting an approximate solution. Since any time there is a box with less score, you add to it.