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

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).

• Wouldn't just summing up the total rank in the lobby and then selecting other lobbies from the list withing the range of +-1.5 work? Or I am totally off? Jun 26, 2015 at 23:25
• From your question I am concluding that "Lobbies can't be split up and the rank differential between users in a lobby can't exceed 4" is already ensured from something else, not part of the algorithm you are looking for right? Jun 27, 2015 at 18:15

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.

• Can you expand a bit on "To build that list you loop through the lists L1,...L5 according to the partitions of 5." Also, I'm curious how I could do this dynamically as long as it doesn't add significant complexity. Jun 28, 2015 at 18:16
• I've implemented it and it appears to work quite well, although I'll have to do some more testing to be sure. Could I show you my implementation privately? Thanks! Jun 29, 2015 at 1:08
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?

• What about lobbies with only 1 person or two people? I need to turn them all into groups of 5v5. Jun 27, 2015 at 0:46
• I though you can't merge lobbies, but if you can, Jun 28, 2015 at 4:44
• "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."
– user40980
Jun 28, 2015 at 18:11