algorithm - 选择锦标赛的最佳球员(团队)子集

Question

问题：
让我们考虑以下场景：
让T={t_1, t_2, ..., t_h}成为一组不同的游戏。每场比赛都是一对一的（它们是单人游戏）。
设n为players的个数，每个游戏都有一个已知的性能度量这个指标可以直接转化为赢得一个给定游戏的概率。编辑：函数Q(i|q)给出了玩家i在与q集合中均匀分布的玩家的比赛中获胜的预期概率。
在比赛中，一组球员从players中抽取一场比赛（随机选择，均匀分布），并可以委托一名球员（以最佳表现衡量）代表该队比赛。
从所有可能的T成员队伍中选择获胜概率最高的队伍。
澄清：玩家和团队面对的是由同一组k玩家组成的团队。或许描述这个问题的更好方法是这样说：
1）所有可能的(k<n)成员团队都是从给定的n玩家集合中创建的（玩家可以在多个团队中复制，但没有两个团队拥有完全相同的玩家集合）。
2）这些队是成对的，每对比赛都会从k开始，
3）每个团队为给定的游戏选择其最佳玩家（根据问题描述中给出的已知性能度量）-这可能导致玩家与自己的相同副本进行游戏；请注意，“最佳玩家”是在不了解对方团队成员的情况下选择的，只有其自身成员的n值，
4）每队得分等于获胜概率的点数（从未进行过实际比赛，假设松懈得0分，获胜得1分，我们直接进入对给定对手的预期得分），
5）对每对队伍和比赛的组合重复步骤T，
6）得分最多的球队获胜（如果所述比赛和对方球队分别从Q(-|q)和所有可能的2-4成员球队的集合中随机抽取且分布均匀，则球队得分与同一队赢得一场比赛的概率成正比）
什么是“快速”找到获胜球队的方法？
暴力解决方案：
我们按照澄清书上写的做。
这种类型的解决方案在T大量的时候失败了——对于k一些可能的队大约等于n，这使得不可能很快地指向最好的队。
我在寻找什么样的解决方案（算法）？
显然，任何可以将该团队构建为一个迭代过程的东西都不需要检查所有可能的团队组成如果不存在精确解，那么近似解是可接受的（即从第九十五百分位创建团队）。
我考虑这个问题已经有一段时间了，但是我不能提供任何严格的证据证明我提出的任何方法都能满足我的条件我提出的一个可能的解决方案是，选择一个拥有最多比赛次数的球员，在比赛中，他自己的排名高于95%的球员，这将是球队的第一名球员。然后，我会通过所有可能的第二名球员，并添加一个增加游戏的数量，在其中的球队比例如95%的球员最好然后我会继续这个过程，直到找到n>>k播放器。
这个解决方案提出了一个明显的问题，那就是我们在任何时候都没有真正地将n^k玩家团队相互比较，我们甚至都没有试图找到真正最好的团队（老实说，这并不重要）。
我会感谢任何帮助-也可以是任何形式的链接到外部来源/发表的论文等涉及这类问题。我看到的大多数问题都涉及到团队的构建，假设团队的性能与其成员的平均性能相关，而不是给定任务的最高性能。

Answer 1

这个问题有两个主要的困难点——它们是相互依存的。
首先，这是一个概率版本的Set Cover Problem：你需要一个玩家集合，他们可以为你提供各种游戏的“好”报道，为一些启发性的“好”。
其次，你的球队赢得一场比赛的可能性不是一个平稳的函数。博弈策略矩阵是一个k x k矩阵，改变该矩阵中的一个条目（匹配结果）可以完全改变最优策略。
在没有关于Q函数的任何有用属性的情况下，我们没有理由期望某个特定的启发式（例如，选择一个获胜率普遍较高的玩家）是找到前5%解的有效方法。在许多情况下，一对“多面手”玩家将带领任何这样的启发式到一个局部最大值，将其输给在一个小领域中经过精心挑选的专家团队。
例如，假设你选择一个全明星的三人小组参加五项全能（不是五项全能得分，只是个人项目）。你选多面手：比如说，最近在国际五项比赛中获得四枚奖牌的选手。我将以个人项目中最新的奖牌获得者为例：1号法国重剑，最近的200米游泳冠军，最近的两项全能冠军，我将放弃跳台表演这实际上保证了我4个项目中有3个获胜（如果你把两项全能算在一起的话，5个项目中有4个获胜）。
如果你对Q函数有某种梯度性质，比如各种游戏中的能力之间的相关性，那么我们可以使用ML算法来确保在更短的时间内得到一个很好的解决方案在那之前，你会遇到棘手的问题。