Balancing players into two teams

Question

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?

Answer 1

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.