An algorithm for self picking teams

Question

Say I have 100 users, each with varying strength, and each with a top 5 set of "preferred teammates" and a top 5 set of "preferred enemies". I want to sort the users into two teams.

User
{
   int Id;
   int strength;
   List<int> PreferredTeammatesIds;  // arbitrary limit of 5
   List<int> PreferredEnemiesIds;  // arbitrary limit of 5
}

I am trying to come up with an algorithm where the total strength of each team is near equal, and as many of each user's preferences are achieved.

First, I assume a perfect everyone-gets-what-they-want is highly unlikely, especially with 100 users. But is there a way to calculate the optimal alignment, or would I just have to do some sort of random mutations or genetic algorithm and keep the best lineup found in N number of generated solutions?

Answer 1

The problem of partitioning a set of integer numbers into two sets with (almost) equal sums is a well-known and well-researched problem. It is called Partition problem (or as Wikipedia states - the optimization version of this problem). Solving it exactly is NP-hard, but the Wikipedia article contains some pointers to heuristics which will find you a "good solution" in an efficient manner.

The additional constraint of having both teams' sizes equal reduces the size of the search space, but I would not expect this to make the problem much simpler. Here is an older post on math.SE which shows how to introduce the constraint in a way any any partition algorithm can be applied to the "partition with equal set size" problem as well.

The constraints about the user's preferences probably don't make things easier, either. But to take this into account, need to define precisely how these contraints are used / weighted against the "equal strength / team sizes" conditions.

So yes, I would expect a randomized algorithm like Simulated Annealing being the right tool for this, or at least a good start.

Answer 2

Since this is basically an optimization problem, I would start with defining a suitable objective function that can be used to check which one of a number of solutions is best. To avoid transitivity issues, it's best to have a function which computes a numeric fitness value from a given solution.

In your problem, you have three factors that contribute to fitness:

• team size difference
• team strength difference
• "happiness" (how well each player's team preferences are met)

There are many different ways these can be combined into a single number. For example you could just sum up player strengths for each team, or you could penalize solutions in which one team has more of the weak players than the other one. Similarly for happiness: if individual player's happiness is computed by the number of matched preferences (possibly weighing negative preferences stronger than positive preferences) you could optimize for highest total happiness, highest "minimum happiness", lowest number of unhappy players etc.

To avoid getting completely implausible solutions, it's probably best to have some kind of nonlinearity such that if one aspect of a solution is particularly bad, the contribution of this aspect to the overall fitness is stronger.

One fitness aspect (team size) may be taken out of the objective function and baked into the algorithm, for example by only ever considering solutions with equal team sizes. Alternatively, you could give team size difference a higher weight than strength difference and happiness.

For this specific problem, there is most likely no specialized optimization algorithm, so you should choose a generic one, such as simulated annealing or some genetic algorithm. Off the top of my head, I don't see how you could define a combination/crossover operation for a genetic algorithm, so you would probably be limited to simple mutations and removal of weakest solutions from the population. This requires experimentation.

Answer 3

Well, there are 100891344545564193334812497256 ways to choose two teams of 50. Varying the size or number of teams won't move those numbers to a reasonable level, so you're going to have to approximate.

I wouldn't do it completely randomly, though. I would start by sorting then assigning by strength, then sort by (enemies on my team - friends on my team) and swap the two highest on each team. Figure out heuristics to break cycles, and keep going until you're happy or run out of time.

Answer 4

I remember how we used to do this in gym class in school when we needed teams. Two kids of equal strength were pulled out of the crowd and each could, by turn, pick a team member. To make it more fair, the one who got to pick second would get two consecutive picks, after which it would be alternating again until all players were taken. This is because the first picker will choose the top player who is likely a lot more capable than the next (for the sake of the argument, let's call him Jon) and this will provide an advantage that needs to be compensated.

This is easily automated by choosing the best ranking players in alternation. It ignores the favorite enemies part but if equal strength is the goal, that does not seem to matter.