Team matchmaking algorithm based on ELO

Question

I'm looking for a very simple way to put up 2 teams out of unspecified(but known) amount of players. So its not actually a standard matchmaking since it only creates one match out of the whole pool of registered players for the specific match. I do have pretty much only single variable and it is the ELO score for each player, which means it's the only available option to base calculations on.

What I thought of is just simply go through every possible combination of a players(6 in each team) and the lowest difference between the average ELO of teams is the final rosters that get created. I've tested this option and it gives me more than 17mil calculations for 18 registered players(the amount of players shouldnt be more than 24 usually) so its doable but its definitely the MOST unoptimized way to do that.

So I decided to ask a question in here, maybe you can help me with that in some way. Any ideas what simple algos I can use or the ways of optimizing something in a straight up comparisons of all possible combinations.

If you want to provide any code examples I can read any code language(almost), so it doesnt really matter.

Update:

• Input: a list[] of player that contain player_id and elo,
• Output: two lists: team1[] and team2[] containing player objects.
• Objective: The average Elo of both teams should be as close as possible.

Answer 1

We can write this as a mathematical optimization problem:

Say we have players i=1..24, and teams j=1,2. Introduce decision variables:

 x(i,j) = 1 if player i is assigned to team j
          0 otherwise

Then we can write:

 Min |avg(2)-avg(1)|
 subject to
     sum(j, x(i,j)) <= 1    for all i  (a player can be assigned only once)
     sum(i, x(i,j)) = 6     for all j  (a team needs 6 players)
     avg(j) = sum(i, rating(i)*x(i,j)) / 6   (calculate the average)
     avg(j) >= 0         

We can linearize the absolute value in the objective:

 Min z
 subject to
     sum(j, x(i,j)) <= 1    for all i
     sum(i, x(i,j)) = 6     for all j
     avg(j) = sum(i, rating(i)*x(i,j)) / 6
     -z <= avg(2)-avg(1) <= z
     z >= 0, avg(j) >= 0

This is now a linear Mixed Integer Programming problem. MIP solvers are readily available.

Using some random data I get:

----     43 PARAMETER r  ELO rating

player1  1275,    player2  1531,    player3  1585,    player4   668,    player5  1107,    player6  1011
player7  1242,    player8  1774,    player9  1096,    player10 1400,    player11 1036,    player12 1538
player13 1135,    player14 1206,    player15 2153,    player16 1112,    player17  880,    player18  850
player19 1528,    player20 1875,    player21  939,    player22 1684,    player23 1807,    player24 1110


----     43 VARIABLE x.L  assignment

               team1       team2

player1        1.000
player2                    1.000
player4        1.000
player5                    1.000
player6                    1.000
player7        1.000
player8        1.000
player9        1.000
player10                   1.000
player11                   1.000
player17       1.000
player18                   1.000


----     43 VARIABLE avg.L  average rating of team

team1 1155.833,    team2 1155.833


----     43 PARAMETER report  solution report

               team1       team2

player1     1275.000
player2                 1531.000
player4      668.000
player5                 1107.000
player6                 1011.000
player7     1242.000
player8     1774.000
player9     1096.000
player10                1400.000
player11                1036.000
player17     880.000
player18                 850.000
sum         6935.000    6935.000
avg         1155.833    1155.833

Surprisingly, for this data set we can find a perfect match.