Construction of fair teams
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. 12
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. 12