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

Here is a solution in MiniZinc:

% Selecting Chess Players

include "globals.mzn";

int: noOfTeams = 2;
int: noOfPlayers = 24;
int: playersPerTeam = 6;

set of int: Players = 1..noOfPlayers;
set of int: Teams = 1..noOfTeams;

array[Players] of int: elo = 
  [1275, 1531, 1585,  668, 1107, 1011,
   1242, 1774, 1096, 1400, 1036, 1538,
   1135, 1206, 2153, 1112,  880,  850,
   1528, 1875,  939, 1684, 1807, 1110];

array[Players] of var 0..noOfTeams: team;
array[Teams] of var int: eloSums;

%  same number of players per team
constraint forall(t in Teams) (
     playersPerTeam == sum([team[p] == t | p in Players])
  );

%  sum up the ELO numbers per team
constraint forall(t in Teams) (
     eloSums[t] == sum([if team[p] == t then elo[p] else 0 endif | p in Players])
  );

%  enforce sorted sums to break symmetries
%  and avoid minimum/maximum predicates          
constraint forall(t1 in Teams, t2 in Teams where t1 < t2) (
    eloSums[t1] <= eloSums[t2]
);

solve minimize eloSums[noOfTeams] - eloSums[1];

output ["\n             "] ++ ["team" ++ show(t) ++ "  " | t in Teams] ++
       ["\n"] ++
       [ if fix(team[p]) != 0 then
             if t == 1 then 
                "\nplayer" ++ show_int(-2,p) ++ " " 
             else 
                "" 
             endif ++
             if fix(team[p]) == t then
                show_int(8, elo[p])
             else
                "       "
             endif
         else 
           "" 
         endif 
         | p in Players, t in Teams ] ++
         ["\nsum     "] ++
         [show_int(8, eloSums[t]) | t in Teams ] ++
         ["\navg        "] ++
         [show_float(8,2,eloSums[t]/playersPerTeam) | t in Teams ];

The main decision variable is the array team. It assigns every player to one of the teams (0 = no team). To find a close ELO average, I sum up the ELO sums and enforce that minimum and maximum of all team sums are close together.

Answer 2

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.

Answer 3

Given that your approach is an approximation anyways, putting too much effort to produce a perfect answer is a losing cause. Instead pick a reasonable difference and go from there.

I would suggest that you sort the list of players by ELO, then pair them up. Those people will be on opposing teams if they are included. If there are an odd number of people, leave out the person who is farthest from any other. Sort the pairs by difference and pair them up as well in the same way. That gives you fairly evenly matched groups of 4, and the teams will be the best and worst against the middle 2. These groups of 4 should generally be relatively close to even. Score it as the better group minus the worse one. (Either half can wind up better depending on actual scores.)

Now search for 3 groups of 4 such that A is as close as possible to the sum of B and C. The better group from A will go with the worse groups from B and C.

With 24 people this will be a virtually instantaneous calculation, and will give reasonable results.

The repeated difference approach that I started with is a well-known heuristic for the subset sum problem.

---

Given how fast this heuristic is, I think that it is worth broadening the search for a good team as follows.

1. Sort your players. Put each player into a pair with the person above and below. With n players this will be n-1 pairs. Give each pair a score of either the ELO difference, or of how much more likely the better is to beat the worse. (Which I would choose depends on the way that the two play.)
2. Sort your pairs. Pair each pair with the closest pair above and below who does not intersect it. With n-1 pairs this will usually result in n-2 groups of 4.
3. Create a sorted list of groups of 4. Call it list4. Note that this list has size n + O(1).
4. Construct a list of all groups of 8 that can be made from 2 groups of 4 that do not intersect. Sort it. Call it list8. The formula for how big this list is is complicated, but is n^2/2 + O(n) and took time O(n^2 log(n)) to sort.
5. For each element of list4 find the nearest elements in list8 that are above/below it and have no players in common with it. For O(n) elements this is O(log(n)) expected work.

The result is that you get rid of the even/odd logic. Yes, you added back in some extra effort, but the biggest effort was the O(n^2 log(n)) to sort list8. This is sufficiently fast that you'll still produce very quick answers even if you had a hundred people thrown at it.

The result will be two evenly matched teams such that when they pair off by strength, the weaker team at least has a reasonable chance of posting a convincing upset.