2
$\begingroup$

let's say we have a set of players that we want to match into teams of aproximatly same strength, so that no team is much stronger than another team.

Each team consists of two players. One player is taking a defense position, another player is taking an offense position. The teams can decide for themself which of the players if playing at what position. We can assume that the teams try to win and will take the best possible combination of defense/offense player.

Each player has an offense rating (e.g. discrete number between 0 and 10) and a defense rating (same scale) that describes how strong the player is in the offense or defense position.

The strength of a team is determined by the defense strength of the player in the defense position and the offense strength of the player in the offense position. So we can assume:

TeamStrength = max(PlayerADefense + PlayerBOffense, PlayerAOffense + PlayerBDefense)

The question is, what is a good algorithm to find teams of similar strength using above metric.

My thinking is that I can easily evaluate a single result by calculating an average team strength and build the sum of difference (square).

Based on this it is obvious that I can just create random matches and then choose a "good" solution. However I'm curious if there is a way to find an optimal solution without brute forcing of all variants.

Any ideas?

Edit: There seems to be some confusion about the metric of optimal strength / average strength.

The goal is to have teams of similar strength, nothing more nothing less. Specifically I don't care if there are other combinations where the total strength of all teams is higher.

I can imagine various metrics to achieve this goal. One idea I presented was to use the following metric:

For each team t calculate its strength by calculating: 
    strength_t = max(PlayerADefense_t + PlayerBOffense_t, PlayerAOffense_t + PlayerBDefense_t)
Calculate the average team strength: avgStrength = sum(strength_t) / teamCount
For each team t calculate its deviation from the average squared and sum it:
    m = m + (avgStrength - strength_t) ^ 2
m should be minimal

I want to minimize the value $m$. I want to emphazize that I'm open to other metrics if they provide comparable results.

$\endgroup$
  • $\begingroup$ What exactly are you trying to find? A pair of teams with the closest possible strength? A division of all the players into teams so that the teams are "as close as possible" to having the same strength? (If so, by what metric?) A division of all the players into teams and a pairing of the teams so that each pair of teams is as close as possible to the same strength? Something else? $\endgroup$ – David Richerby Mar 12 '15 at 18:57
  • $\begingroup$ The second one, a division of all the players into teams so that they are as close as possible to having the same strength. $\endgroup$ – aKzenT Mar 12 '15 at 19:08
  • $\begingroup$ The optimum would be to have all teams with the same strength which would be the average strength of all teams. So while I'm open to alternative suggestions, one possible metric would be a "least square" approach, e.g. taking the squared difference between the optimum strength and actual team strength and summing this for all teams. $\endgroup$ – aKzenT Mar 12 '15 at 19:11
  • $\begingroup$ The application is matching real human players into teams and having an "interesting" match that is not dominated by overly strong teams and not having any obvious loosers. So what I'm looking for at the end is something that is better than just random sampling of possible teams. Optimally would be an efficient algorithm finding the best match of course. As to the exact metric I don't care as long as it provides reasonable good results. $\endgroup$ – aKzenT Mar 12 '15 at 19:15
  • $\begingroup$ It would help if you edited the question to specify a metric for what you mean by "approximately same strength" (i.e., a metric to use for evaluating how good a particular assignment of players to teams is). It seems that the comments have spawned some uncertainty (see megas's comment underneath my answer, where he points out a shortcoming of the metric that you seem to be suggesting in your 2nd comment), so anything you can do to help clarify what you are looking for might help improve the quality of answers. $\endgroup$ – D.W. Mar 13 '15 at 6:38
3
$\begingroup$

This can be expressed as a weighted maximum matching problem.

Suppose we want the average team strength to be $x$. If the actual team strength is $s$, we apply a penalty of $(x-s)^2$. In this way, for any proposed partitioning of the players into teams, we obtain a total penalty (the sum of the penalties for each of the teams). The goal is to find an assignment of teams that minimize the total penalty. I think this is what you are asking for.

So, here is how we express this as a maximum matching problem. If you have $n$ players, form a graph with $n$ vertices, one vertex per player. For each pair of players $v,w$, add an edge from $v$ to $w$ whose weight is $-(x-s_{v,w})^2$, where $s_{v,w}$ is the strength of the team obtained by putting $v$ and $w$ onto the same team. Now any division of the people into $n/2$ teams is a matching in this graph. By maximizing the total weight of the matching, we are minimizing the total penalty of the corresponding teams, so the maximum matching gives us a solution to your problem. Finally, there are polynomial-time algorithms for finding a maximum matching in a weighted graph, so you can just use one of them.

How do we find $x$? I initially interpreted your comments to imply that $x$ should be the optimal team strength, by which I assume you mean the average strength of the teams in the assignment that maximizes this average (without trying to make the team strengths as similar as possible). This too can be computed by solving a maximum matching problem, where now the weight on the edge from $v$ to $w$ is simply $s_{v,w}$. So, the total algorithm is: first find $x$, using an algorithm for maximum matching, then find the best partitioning of teams according to your original matching, by applying the maximum matching algorithm a second time.

However, after reading megas' comments, I now suspect that interpretation was incorrect. As megas correctly explains, a more reasonable interpretation would be to make $x$ be the average strength of the teams in the partitioning selected to make team strength as close as possible. That's a harder problem.

However, here's an approach that might work reasonably well in practice. Sweep $x$ over a range of candidate values, say, over 100 candidate values. (You can probably get some reasonable guess for a range $[\ell,u]$ that is likely to contain the optimal value for $x$; now try a bunch of different values of $x$ in that range, say the values $\ell, \ell+0.01(u-\ell), \ell+0.02(u-\ell), \dots,u$.) For each such hypothesized value of $x$, solve the maximum matching problem (with weights $-(x-s_{v,w})^2$ on the edges) to get an assignment of players to teams. In this way, we get 100 candidate assignments. Now for each we can calculate the average team strength and the total penalty, and see which assignment is best.

Why do I expect this will give close to an optimal answer? Well, there is some real optimum. Let $x_\text{opt}$ be the average team strength for this actual optimum. When we use a candidate value for $x$ that is sufficiently close to $x_\text{opt}$, we can expect to get an assignment that matches the optimum (or is close to it). So, if the step size for the candidate values of $x$ is small enough, this procedure seems like it should find the optimum. In practice, this is only a heuristic, and it might or might not find the actual optimum, but I suspect it will enable you to find an assignment that's pretty close to optimal, even if it's not exactly the optimum.

$\endgroup$
  • $\begingroup$ This is definitely a nice approach. But the OP's objective is to find teams of approximately equal strength, which at the optimal point will be close to their average; It feels that this choice of $x$ is not helping that objective. And it is the choice of $x$ that seems to be very challenging, at least under this approach. $\endgroup$ – megas Mar 13 '15 at 6:32
  • $\begingroup$ @megas, I understand.... but I'm just using the metric that the OP suggested. As the OP wrote, "one possible metric would be a "least square" approach, e.g. taking the squared difference between the optimum strength and actual team strength and summing this for all teams.". That's exactly the metric I use in this answer. If that's not the metric the OP wants maximized, or if I mis-understood his/her comment, then it's up to her/him to edit the question to specify a metric. $\endgroup$ – D.W. Mar 13 '15 at 6:35
  • $\begingroup$ It is definitely up to the OP! I understood optimum strength as the average strength of the optimal team set (where optimal set is the one that minimizes the objective as you stated it, but with $x$ being dependent on the selected teams and not fixed a-priori). In any case, the sole motivation of my comment was point out my interpretation of the question which (possibly?) renders the problem more challenging, and see/discuss whether there was a more suitable choice for $x$ under that interpretation. $\endgroup$ – megas Mar 13 '15 at 7:14
  • $\begingroup$ @megas - oh! Your interpretation makes much more sense, and now that you explain it, I bet it's more likely to be what the OP wanted. Thank you for the explanation. I've edited my answer to outline one heuristic that might be effective at optimizing for that metric. $\endgroup$ – D.W. Mar 13 '15 at 7:32

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.