Strategy/algorithm to divide fair teams based on Elo and team request

I am part of a team hosting regular events where each player has an elo which depends on how well he or she has played in previous events. These events have 40 players and the players get split into teams of 5. The events always fill up so there are always equally many players in every team.

We used to allow a team request for every player, put them together and then just randomized everyone else which could lead to unfair teams.

So, given the ELO of every player as well as a team request from some players (a team request is only valid if the two people request each other), what would be a good strategy to assign fair teams? (Perfectly fair teams would be when the average ELO of every team is the same.)

The team requests should be fulfilled as often as is possible, and if some players will not get their team requests then this should be from random. (For example, if everyone would send a in a team request not all could be upheld because there are teams of 5s).

For example, here are some players:

Player1: 1200Elo Team Req: Player 3
Player2: 1300Elo Team Req: -
Player3: 1000Elo Team Req: Player 1
Player4: 900ELO Team Req: Player7
Player5: 1500Elo Team Req: -
Player6: 1400Elo Team Req: -
Player7: 1000Elo Team Req: Player 4
Player8: 800Elo Team Req: -
...
Player40: 1400Elo Team Req: -

To sort them simply by ELO you could

• order the participants by elo
• Start with the highest and put them in team 1, next in team 2 until all the teams have 1 member
• Take the next highest, but assign them to team 8, 7, 6... when you get to 1 reverse again
• When you get to the last row start with team 8 again rather than 1.

But this doesn't take into account any team requests. How could I go by adding that?

I made a genetic algorithm to try solving your problem.

Parameters that you can toy with:

• n_generations=400 in main() (low = faster algorithm, high = better teams)
• The weights return pref_score * 1 + elo_score * 1 in score_function() to decide what is more important, satisfy the player preferences or have balanced teams
• pool_size=100 in make_assignments() (low = faster algorithm, high = better teams)
• podium=10 in make_assignments() (must be between 0 and pool_size // 2)

from random import shuffle, sample, choices
from statistics import mean, pvariance
from math import exp

n = 40
n_teams = 8
players_per_team = 5
assert(n == n_teams * players_per_team)

def random_teams_with_preferences(preferences):
    players = list(range(n))
    shuffle(players)
    shuffle(preferences)
    teams = [players[players_per_team*team_number:players_per_team*(team_number+1)] for team_number in range(n_teams)]
    for u,v in preferences:
        u_team = next(i for i,t in enumerate(teams) if u in t)
        v_team = next(i for i,t in enumerate(teams) if v in t)
        if u_team != v_team:
            w = next(w for w in teams[u_team] if w!=u)
            teams[u_team] = (set(teams[u_team]) | {v}) - {w}
            teams[v_team] = (set(teams[v_team]) | {w}) - {v}
    return teams

def init_pool(pool_size, preferences=[]):
    return [random_teams_with_preferences(preferences) for _ in range(pool_size)]

def score_function(teams, players_elo, preferences):
    satisfied_preferences = 0
    for u,v in preferences:
        team = next(team for team in teams if u in team or v in team)
        if u in team and v in team:
            satisfied_preferences += 1
    pref_score = 100 * (satisfied_preferences / len(preferences) if preferences else 1)
    combined_elos = [mean(players_elo
 for p in team) for team in teams]
    elo_score = (500000 - pvariance(combined_elos)) / 5000
    return pref_score * 1 + elo_score * 1

def make_child(teams):
    t1, t2 = sample(range(len(teams)), k=2)
    p1, p2 = choices(range(players_per_team), k=2)
    new_teams = [
 for team in teams]
    new_teams[t1][p1], new_teams[t2][p2] = new_teams[t2][p2], new_teams[t1][p1]
    return new_teams

def make_assignments(players_elo, preferences, n_generations=10):
    podium=10
    pool = init_pool(pool_size=100, preferences=preferences)
    score = lambda x: score_function(x, players_elo, preferences)
    scored_pool = sorted(((score(teams), teams) for teams in pool), reverse=True)
    for _ in range(n_generations):
        children1 = [make_child(teams) for _,teams in scored_pool[:-podium]]
        children2 = [make_child(teams) for _,teams in scored_pool[:-podium]]
        new_pool = [
            choices((p, c1, c2), weights=(exp(s),exp(score(c1)),exp(score(c2))))[0]
            for (s,p),c1,c2 in zip(scored_pool, children1, children2)
        ] + [t for _,t in scored_pool[:podium]]
        scored_pool = sorted(((score(teams), teams) for teams in pool), reverse=True)
    return scored_pool

def random_preferences(k):
    players = list(range(n))
    result = []
    for _ in range(k):
        u,v = sample(players, 2)
        result.append((u,v))
        players = [x for x in players if x not in (u,v)]
    return result

def main():
    players_elo = [1627, 2343, 1683, 980, 1285, 826, 1307, 1682, 1488, 1504, 1627, 1948, 1390, 1204, 975, 1370, 1044, 1497, 1526, 1427, 1515, 1414, 1141, 764, 1844, 1451, 1864, 1379, 2072, 1210, 1683, 1006, 1030, 872, 985, 1016, 1512, 1203, 1442, 1015]
    assert(len(players_elo) == n)
    preferences = random_preferences(7)
    print('PLAYERS:', players_elo, sep='\n', end='\n\n')
    print('PREFERENCES:', preferences, sep='\n', end='\n\n')
    scored_pool = make_assignments(players_elo, preferences, n_generations=400)
    score, teams = scored_pool[0]
    print('TEAMS:')
    for team in teams:
        print(team, end=' ')
        elos = [players_elo
 for p in team]
        print(elos, mean(elos))
    print()

if __name__=='__main__':
    main()

Results:

PLAYERS:
[1627, 2343, 1683, 980, 1285, 826, 1307, 1682, 1488, 1504, 1627, 1948, 1390, 1204, 975, 1370, 1044, 1497, 1526, 1427, 1515, 1414, 1141, 764, 1844, 1451, 1864, 1379, 2072, 1210, 1683, 1006, 1030, 872, 985, 1016, 1512, 1203, 1442, 1015]
PREFERENCES:
[(15, 26), (36, 20), (35, 16), (23, 39), (10, 22), (11, 3), (18, 6)]
TEAMS:
[14, 28, 38, 33, 12] [975, 2072, 1442, 872, 1390] 1350.2
[11, 31, 3, 34, 17] [1948, 1006, 980, 985, 1497] 1283.2
{32, 5, 8, 15, 26} [1030, 826, 1488, 1370, 1864] 1315.6
[25, 2, 30, 21, 37] [1451, 1683, 1683, 1414, 1203] 1486.8
{1, 39, 10, 22, 23} [2343, 1015, 1627, 1141, 764] 1378
{6, 13, 18, 19, 29} [1307, 1204, 1526, 1427, 1210] 1334.8
{0, 35, 7, 9, 16} [1627, 1016, 1682, 1504, 1044] 1374.6
{4, 36, 20, 24, 27} [1285, 1512, 1515, 1844, 1379] 1507