Algorithm and data structure to match groups of users (1-5 each) into 2 balanced sets of 5 users

Question

I'm building a matchmaking queueing service for a 5v5 team-based game.

I have a large set of users that are grouped into unique lobbies comprised of 1-5 users each. Each user has an integer based rank from 1-16. These ranks will eventually be converted to a trueskill rating, but for now, we're sticking with integers since we're importing the rankings from an existing system that is already quite accurate.

So we have lobbies of up to 5 people, and we want to create balanced matches between 10 people (5v5), combining these various lobbies in a way that is balanced and equivalent to 2 sets of 5 people. Lobbies can't be split up and the rank differential between users in a lobby can't exceed 4.

I can design the data structure in any way. Currently, I have a hash object of lobbies and a hash object of users that refer to each other.

I'm not looking for code, or even necessarily pseudocode. I'm just looking for a place to start. I'm a little lost on how I can efficiently and properly combine lobbies of various sizes into 5v5 matches, while ensuring that those two teams are sufficiently balanced in ranks (+-1.5 ranks).

Answer 1

First thing is to know the partitions of the number 5 (the team size you want to assembly). There are algorithms to generate the partitions of a number but since the number is small and fixed you don't need to worry about it. The partitions of 5 are: {5}, {4,1}, {3,2}, {3,1,1}, {2,2,1), {2,1,1,1}, and {1,1,1,1,1}.

Make 5 lobby lists (L1,L2,L3,L4,L5). One for each lobby size. Each element will contain: 1) the lobby id 2) the time in queue 3) the sum of the ranks of the players that compose the lobby L1 is the list of all lobbies of size 1, L2 is the list of all lobbies of size 2 and so on.

Now you make a list T of all possible teams of 5 people that you can assembly from the 5 lists of lobbies. To build that list you loop through the lists L1,...L5 according to the partitions of 5.

team {
    int partition_type;
    int lobby_index[5]; //each lobby_index value will mean a different thing depending on the value of partition_type
}

team_index = 0

//partition case 0: {5}
for (i5=0; i5<n5; i5++) do
    //in the case of partition_type==0, only the first index is used and it is an index in the list of lobbies of size 5
    Team[team_index++] = new team(partition_type = 0, lobby_index[0] = i5)
end

//partition case 1: {4,1}
for (i4=0; i4<n4; i4++) do
    for (i1=0; i1<n1; i1++) do
        //in the case of partition_type==1, the first index is an index in the list of lobbies of size 4 and the second is an index in the list of size 1
        Team[team_index++] = new team(partition_type = 1, lobby_index[0] = i4, lobby_index[1] = i1)
    end
end

//partition case 2: {3,2}
for (i3=0; i3<n3; i3++) do
    for (i2=0; i2<n2; i2++) do
        Team[team_index++] = new team(partition_type = 2, lobby_index[0] = i3, lobby_index[1] = i2)
    end
end

//partition case 3: {3,1,1}
for (i3=0; i3<n3; i3++) do
    for (i1a=0; i1a<n1-1; i1a++) do // 0 <= i1a < i1b < n1
        for (i1b=i1a+1; i1b<n1; i1b++) do
            Team[team_index++] = new team(partition_type = 3, lobby_index[0] = i3, lobby_index[1] = i1a, lobby_index[2] = i1b)
        end
    end
end

//partition case 4: {2,2,1)
for (i2a=0; i2a<n2-1; i2a++) do  // 0 <= i2a < i2b < n2
    for (i2b=i2a+1; i2b<n2; i2b++) do
        for (i1=0; i1<n1; i1++) do
            Team[team_index++] = new team(partition_type = 4, lobby_index[0] = i2a, lobby_index[1] = i2b, lobby_index[2] = i1)
        end
    end
end

//partition case 5: {2,1,1,1}
for (i2=0; i2<n2; i2++) do
    for (i1a=0; i1a<n1-2; i1a++) do  // 0 <= i1a < i1b < i1c < n1
        for (i1b=i1a+1; i1b<n1-1; i1b++) do
            for (i1c=i1b+1; i1c<n1; i1c++) do
                Team[team_index++] = new team(partition_type = 5,     lobby_index[0] = i2, lobby_index[1] = i1a, lobby_index[2] = i1b, lobby_index[3] = i1c)
            end
        end
    end
end

//partition case 6: {1,1,1,1,1}
for (i1a=0; i1a<n1-4; i1a++) do  // 0 <= i1a < i1b < i1c < i1d < n1
    for (i1b=i1a+1; i1b<n1-3; i1b++) do
        for (i1c=i1b+1; i1c<n1-2; i1c++) do
            for (i1d=i1c+1; i1d<n1-1; i1d++) do
                for (i1e=i1d+1; i1e<n1; i1e++) do
                    Team[team_index++] = new team(partition_type = 6, lobby_index[0] = i1a, lobby_index[1] = i1b, lobby_index[2] = i1c, lobby_index[3] = i1d, lobby_index[4] = i1e))
            end
        end
    end
end

To calculate the rank of a Team[30] (just showing one case):

if Team[30].partition_type==2 then
    i3 = Team[30].lobby_index[0]
    i2 = Team[30].lobby_index[1]
    rank = ( (L3[i3].rank) + (L2[i2].rank) ) / 5
end

Have 2 copies of T (or at least make sure you can traverse it in 2 different ways). One ordered by the average rank of that team and the other copy ordered by the average time in queue.

Now traverse the list T ordered by queue times from higher to lower. The first element is the one that has the priority to find a game first because their members are waiting for longer in average. Check the rank average of this team. Now use the rank value you found to determine all the teams that are +/- 1.5 from its rank. This is easily done by using the teams list T copy ordered by ranking. Now you just need to check if any of the teams in the rank range does not include any lobby of the current team (since one lobby can't be in both teams).

If there is such a team them you just found a game (if there are more than one pick then one with highest queue time). Remove all lobbies involved from their lists and recalculate all teams again. If not them get the next team in the list ordered by queue time and test again. Once you traverse all the queue time list you wait until the list of queues change and do all again.

Answer 2

1. Calculate the total rank of all players in a single lobby.

2. Match with other lobby based on that. (+- 1.5 range pretty much)

Isn't it as simple as this?