Problem:
Lets consider the following scenario:
Let T={t_1, t_2, ..., t_h} be a set of different games. Each game is played on one-on-one basis (they are single-player games).
Let n be a number of players, each with a known performance measure for each game. This measure can be directly translated into a probability of winning a given game. Edit: function Q(i|q) gives the expected probability of player i winning in the game q against players drawn with uniform distribution from the the set of players.
During a tournament a team of players draws one of the games from T (it's chosen at random with uniform distribution) and can delegate one player (with the best performance measure) to play on that teams behalf.
From all possible k member teams (k<n) choose the one that has the highest probability of winning the tournament.
Clarification: players and teams face off against teams formed from the same set of n players. Perhaps a better way to describe the problem would be to say that:
1) all possible k member teams are created from the given set of n players (players might be duplicated across many teams, but no two teams may have exactly the same set of players),
2) these teams are paired and for each pair a game from T is drawn,
3) each team picks it's best player for the given game (according to the known performance measure given in the problem description) - this can lead to players playing against identical copies of themselves; note that the "best player" is picked without any knowledge about the members of the opposing team only the Q(-|q) values of its own members,
4) each team scores number of points equal to the probability of winning the game (no actual games are ever played, we go straight to expected points gained from playing a given game against given opposing team assuming loosing gives 0 and winning 1 point),
5) steps 2-4 are repeated for all combinations of pairs of teams and games,
6) team with the most points wins (teams score is proportional to the probability of winning a single game against a single team, if the said game and opposing team were drawn at random with uniform distribution from respectively T and the set of all possible k member teams)
What is a "fast" way of finding that winning team?
Brute force solution:
We do exactly what is written in the clarification.
This type of solution fails miserably when n reaches large numbers - for n>>k a number of possible teams is approximately equal to n^k, which makes it impossible to quickly point to the best team.
What kind of solution (algorithm) am I looking for?
Obviously anything that can build that team as an iterative process that doesn't involve checking all possible team compositions. If an exact solution does not exist, then an approximate solution is acceptable (ie creating the team from 95th percentile).
I thought about this problem for a while now, but I'm not able to provide any rigorous proofs that any of the methods I came up with would satisfy my conditions. One possible solution I came up with would involve choosing a player that has the highest number of games in which it's own ranking is higher then that of eg. 95% of the players - that would be the 1st player of the team. Then I would go through all possible 2nd players and add the one that increases the number of games at which the team is better than eg 95% of players the most. Then I would continue the process until k-th player is found.
This solution poses an obvious problem that at no point are we actually comparing m-th player teams against one another, nor are we even trying to find the truly best team (which, to be honest, isn't that important).
I would appreciate any help - also in form of any links to external sources/published papers etc involving this kind of problems. Most problems I looked at that involve building teams assume that teams performance is tied to average performance of its members, as opposed to the highest performance given some task.
This problem has two broad points of difficulty -- and they're interdependent.
First, this is something of a probabilistic version of the Set Cover Problem: you need a collection of players who can give you "good" coverage of the various games, for some heuristic of "good".
Second, your team's likelihood of winning a particular game is not a smooth function. The game strategy matrix is a k x k matrix, and changing one entry (the outcome of a match-up) in that matrix can entirely alter the optimum strategy.
In the absence of any useful properties about the Q function, we have no reason to expect that a particular heuristic (e.g. pick a player with a generally high winning percentage) is a valid way to find a top-5% solution. In many cases, a couple of "generalist" players will lead any such heuristic to a local maximum that loses to a carefully-chosen team of experts in a small field.
For instance, imagine that you're picking an all-star team of three to compete in the events of the Pentathlon (not a scored Pentathlon, just the individual events). You pick the generalists: say, the most recent four medalists in international Pentathlon competition. I'll take the most recent medalists in the individual sports: the #1 French epee, the most recent 200m swim champion, the most recent biathlon winner, and I'll ceded the show jumping. That virtually guarantees me 3 wins of the 4 events (or 4 of 5, if you're counting the biathlon as double).
If you have some sort of gradient properties for the Q function, such as correlations among abilities in the various games, then we might be able to employ ML algorithms to ensure an excellent solution in much less time. Until then, you're stuck with a nasty complexity to the problem at hand.