Bin Packing Algorithm for Teammate finder app?

Question

Question(s)

• Can I use Bin Packing Algorithm for forming teams of 5 from a dynamic queue of players that is trying to find teammates?

Context I'm making a teammate finder app where:

• Player selects role and region
• Player clicks find match
• Player is put on matchmaking queue
• There are only 5 role slots for one lobby
• Player takes one role slot based on his role
• Player is placed in a suitable bin(lobby) where player's MMR(rank),region, role and KDA is considered.
• If player didnt fit in the existing lobbies, the program will make a new lobby
• A lobby group is created based on the players's MMR and region and placed on based on rank tier and region where rank_tier = Math.round(MMR/1000) and lobby_group_key=(rank_tier+region) ex. region=America MMR=3333 rank_tier=3 key=3America; region=EU MMR=3500 rank_tier=4 key=4EU
• A lobby is placed in the lobby group
• The player didn't fit will be placed in the new lobby
• Move to next player and try to place until there is no players in queue
• Once a lobby is filled, it is considered final and removed from the tentative list

Pseudocode

This is the pseudocode that I have in mind but I don't know if it is exactly a Bin Packing Algorithm. I'm really new to Algorithms

let tentative_lobbies = new Map()
let player_queue = new Map()

//player joins queue
function playerJoins(){
    tryPlacePlayer(player)
}

// try to place player in a lobby(bin)
function tryPlacePlayer(player){
    if lobby group doesn't exist
        //make a lobby group based on player MMR and region
        rank_tier = Math.round(player.MMR/1000)
        lobby_group_key = rank_tier+player.region
        lobby_key = ranktier+``+1
    else
        for each lobby that exist for player's rank and region
            if lobby's roleslot is not yet taken
                //place player into the lobby and recalculate the lobby's average kda

            if lobby's roleslots are all filled 
                //remove lobby from tentative_lobbies

        if player didn't fit in any of the lobbys in his rank tier
            //Make a new Lobby based on player's rank and region
            rank_tier = Math.round(player.MMR/1000)
            lobby_group_key = rank_tier+player.region
            lobby_key = ranktier+``+lobby_group.size + 1
            //calculate the average kda for the new lobby
            //place the lobby into tentative_lobbies
}

Answer 1

In the classic Bin Packing Problem, you have are trying to fit weighted elements into the minimum number of capacited bins. The problem you are adressing feels more like a matching problem to me.

You are describing a greedy algorithm, where you take iterative definitive decision with each new player. You could call it best insert strategy. It will definitely yield a feasible solution that uses a low number of lobbys and seems to be perfectly suitable for what you are trying to achieve.

However, if you seek to have the most balanced collection of lobbys in term of MMR, location, ... then this will not yield an optimal solution. For example, take p1 with MMR 0, p2 with MMR 5 and p3 with MMR 15 with compatible roles and say you accept a new player only if its distance to the mean MMR is <= 10.

With order (p2, p3, p1), they will be all accepted in the same lobby, but with order (p1, p2, p3) they wont, and this will create one more lobby.

I see 2 ideas here :

• Design the acceptance criterion to overcome this
• Design a routine to periodically try to merge lobbies