Optimize fair teams when team size is can vary.

I am writing a script to pick teams as fairly as possible from a list of names and associated player values. The teams must have 4 or 5 members per team. I have a good method of optimizing teams when the list is divisible by 4 or 5 directly so that each team has the same number of players. My hang up is the list quanity is unpredictable and may end up being something like 17, where I would want to optimize each team's total value with the option of some teams having 4 members and others 5, i.e. 3 teams of 4 and 1 team of 5. I'm open to modifications to my current picking method, or if it's not possible, having a seperate optimizing loop for just this scenario that could be selected when needed. Thanks!

Current code is:

minstd = 5;
%teamsz = 4;
teamsz = 5;
I = height(playerval)/teamsz;
for i = 1:100000
    idx = kron(eye(I),ones(teamsz,1));
    idx = idx(randperm(end),randperm(end));
    teamtry = playerval.*idx;
    teamsums = sum(teamtry);
    stdev = std(teamsums);
    if stdev < minstd
        minstd = stdev;
        finalstd = stdev;
        finalteams = idx;
        finalteamscore = teamsums;
    end
end

[Image Analyst]

So let me see if I understand this. You have some number of players (numPlayers is how many?) and some number of teams (numTeams is how many) and "teamsz" players per team (around but not exactly numPlayers/numTeams). And you want to assign each player to a teams. And each player has a value or "talent score" (payerval) according to how good he or she it. And you'd like to assign players to teams such that after all players have been assigned to a team, the total talent scores for the teams are as close together as possible. For example you have 20 teams and 1000 players (approcimately 50 players per team) and you want the sum of talent scores for the teams to be around 5000 (or whatever) with as low a spread around that number as possible. Is that right?

[Levi Shelton]

That is correct. There are a few important caveats. First is that it's not a set list of players, so I can't really predict a target team value because there may be instances where the sum of talent scores is around 20 and other times 50. That is why it currently tries random groupings and minimizes the standard deviation of the sums, such that the actual team sum is not relevant. I know there's always going to be some varation, I just need the best possible with the given player values. Max total players would probably be 50. Second is that each team must have either 4 or 5 members, no more, no less. Later on I plan to incorporate some method of finding the best option no matter what, or forcing all 4's or all 5's even with higher deviation. My current sticking point is optimizing when there has to be a mixture of teams with 4 and 5 members.

[Matt J]

@Levi Shelton Rather than optimizing standard deviation of teamsums, you should consider instead optimizing the mean absolute deviation about the mean. This can be posed as a binary linear program and would probably be more reliable than random trial and error.

[Levi Shelton]

@Matt J Thanks for the advice, I'll look into this method. I would certainly prefer a discrete solution as opposed to hammering randperm and hoping for the best.

Answer 1

[Matt J]

Instead of using kron to set up your initial matrix idx, use blkdiag:

nPlayers=17;

minTeams=floor(nPlayers/5); %minimum number of teams
maxTeams=ceil(nPlayers/4); %minimum number of teams

nTeams=minTeams:maxTeams;

M=numel(nTeams);

for i=1:M
   
    N=nTeams(i);
    
    c=diophantine(ones(1,N),nPlayers,[4,5]);
    
    if ~isempty(c);
        memberships=unique(sort(c,2,'descend'),'rows'); break;
    end
    
end

memberships %number of people on each team

memberships = 1×4

5 4 4 4

args=arrayfun(@(z) ones(z,1), memberships,'uni',0);
idx=blkdiag(args{:})

idx = 17×4

1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0

[Matt J]

Thanks for the advice, I'll look into this method. I would certainly prefer a discrete solution as opposed to hammering randperm and hoping for the best.

After membership is computed as above, we can continue as below, using the FEX download minl1intlin,

https://www.mathworks.com/matlabcentral/fileexchange/52795-constrained-minimum-l1-norm-solutions-of-linear-equations

to compute the mean absolute deviation from mean solution:

M=sum(membership); Im=speye(M); em=ones(1,M); %number of players
N=numel(membership); In=speye(N); en=ones(1,N); %number of teams

V=kron(In,playerval(:)');
C=full(V-mean(V,1))/N; %difference-from-mean operator

Aeq_row=kron(en,Im); beq_row=em(:); %each player belongs to 1 team
Aeq_col=kron(In,em); beq_col=membership(:); %total players per team = membership

Aeq=[Aeq_row;Aeq_col]; %total equality constraints
beq=[beq_row;beq_col]; 

lb=zeros(M*N,1); ub=lb+1; intcon=1:M*N; %Force solution to be binary

X=minL1intlin(C,zeros(N,1),intcon, [],[],Aeq,beq,lb,ub);  %solve

X=reshape(round(X),M,N) %X(i,j) assigns i-th player to j-th team