3

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?

  • No constraint on the number of teams or the team sizes? How do you weight the deviation of the total teams strength from the average value against the deviation from the number of achieved preferences? – Doc Brown Apr 30 at 18:52
  • @DocBrown Sorry I guess I left out, there would only be two teams, but I am not ruling our more teams in the future. – Neil N Apr 30 at 18:54
  • Are teams equal size? Or is balanced strength the priority? – Chris Cudmore Apr 30 at 18:55
  • @ChrisCudmore I would say team size is the top priority, with a small variance in strength between the two allowed. – Neil N Apr 30 at 18:57
  • 3
    You may also be interested in the Stable marriage problem. – Theraot May 5 at 7:17
10

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.

| improve this answer | |
  • Thank you for the algorithm links, those were the type of starting points I was hoping to find. – Neil N Apr 30 at 19:47
4

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.

| improve this answer | |
  • This is pretty close to what I started putting into code last night. But instead of the 3 factors you have listed, I am only focusing on two, the strength difference and happiness rating. I am going to keep team size fixed at 50/50 for now and hopefully get good enough results. – Neil N May 1 at 14:44
2

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.

| improve this answer | |
  • It gets ugly fast though, as Alex, Bob and Chris are all my friends and on my team , but Chris hates Bob, and Bob hates Alex, but Chris and Alex are tight. I'd pick one of the friends or enemies list and work on that alone, because the cross product gets nasty. – Chris Cudmore Apr 30 at 20:20
  • 1
    @ChrisCudmore I think in the real-world data, the users will have strong "rivalries" that will take precedent. I am going to start with the preferred enemy lists, ranking them by who got the most 1st place votes, and try to work down from there. The fact that for 90% of other users, there is no preference, I think we'll avoid most love/hate triangles. – Neil N Apr 30 at 20:49
0

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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.