Problem Detail: 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.
Asked By : aKzenT
Answered By : D.W.
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/40361 Ask a Question Download Related Notes/Documents
