# Balancing players into two teams

I'm trying to find an algorithm which would arrange ranked players into 2 teams automatically before the game starts in a balanced way.

The game has 2 teams, each team can have up to 5 players, and each player has a skill rating, the higher the rating the greater the skill of the player in the game. Player rating ranges from 900 to 2100.

Example:

• player1 - rating: 1400
• player2 - rating: 1450
• player3 - rating: 1500
• player4 - rating: 1550
• player5 - rating: 1600
• player6 - rating: 1650
• player7 - rating: 1700
• player8 - rating: 1750
• player9 - rating: 1800
• player10 - rating: 1850

How to arrange these players into 2 teams so that the team average rating between teams is as balanced as possible ie. the difference between 2 teams average rating is the smallest?

• Is the number of players always the sum of the team sizes? (The example may be too simple. Imagine two selectors: after an initial choice of one player, they alternatingly select two, or a last one to complete the team. Can you find an example where this greedy procedure does not work?) Commented Aug 16 at 8:38

With 10 players, just try all possible arrangements.

With more players, this is a variant of the partition problem. You can adapt the standard dynamic programming algorithm for the partition problem, to solve this problem as well.

Specifically, we'll let $$A[t,k,j]$$ be true if there is a subset of $$k$$ of the first $$j$$ players whose total rating is $$t$$, or false otherwise. Notice that you can fill in the entries of the array $$A$$ using the following recurrence relation:

$$A[t,k,j] := A[t,k,j-1] \lor A[t-r_j,k-1,j-1],$$

where $$r_j$$ denotes the rank of the $$j$$th player.

Then, once you have filled in all of the entries of $$A[\cdot,\cdot,\cdot]$$, it is easy to find the optimal solution by iterating over all $$t,k$$ such that $$A[t,k,n]$$ is true (where $$n$$ denotes the total number of players), computing $$|t/k - (T-t)/(n-k)|$$ (where $$T=\sum_i r_i$$ denotes the sum of all players' ratings), and remembering the one where this difference is minimized.

The total running time will be $$O(Tn^2)$$, where $$n$$ is the number of players and $$T$$ is the sum of their ratings. For realistic problem sizes, this should be efficient.

It is a separate question whether, in practice, the average rating is the best predictor of a team's success.

• For some reason i thought there are more combinations, but for arranging 10 players in 2 teams there are only $\binom{10}{5}=252$ so trying all possible arrangements will work fine. Thanks for your answer, including for more players that looks interesting. Commented Aug 17 at 16:07