选择公平的团队 - 以及证明它的数学方法

Question

选择公平的团队 - 以及证明它的数学方法

3

应用程序：类似挑选游乐场团队。

我必须将一个包含n个连续排名元素的集合分成两个由n/2个元素组成的团队。这些团队必须尽可能地“平均”。在上述描述的游乐场团队方面考虑“平均”。排名指示相对“技能”或价值级别。元素＃1的价值为1，“点”，元素＃2的价值为2，依此类推。没有其他限制。

因此，如果我有一个集合[1,2,3,4]，那么我需要两个由两个元素组成的团队。可能性是：

[1,2]和[3,4]

[1,3]和[2,4]

[1,4]和[2,3]

（顺序不重要。）

看起来第三个选项在这种情况下是最好的。但是如何最好地评估更大的集合？平均值/平均数是一种方法，但这会导致以下候选人配对的相同排名，而否则它们看起来不平衡：

[1,2,3,4,13,14,15,16]和[5,6,7,8,9,10,11,12]

我可以使用蛮力方法来评估我问题域中的所有候选解决方案。

是否有一些数学/统计方法可以用来验证两个团队的“平均”程度？

谢谢！

- spoxox

这个问题应该移动到 http://math.stackexchange.com/ 吗？ - jacknad

排名是绝对值还是相对值？例如，总会有(1,2,3,...)吗？还是可能会出现(1,20,21,34,35)等情况？一个例子是科比·布莱恩特和一群高中篮球运动员。 - steve8918

1

我认为你需要更加明确地规范化“均匀性”的含义；如果两个拥有相同平均排名（和相同排名总和）的团队被认为是“不均匀的”，那么这意味着什么？ - Chowlett

是的，“均匀性”很难捉摸。为了简单起见，我将以我提到的点作为表达方式。元素之间的变化可以被视为恒定的。 - spoxox

这背后的理论叫什么？谢谢Michael。 - Alain Michael Janith Schroter

7个回答

3

这些数字代表排名吗？那么，没有足够的信息来制定公平的团队，因此不存在获取公平团队的算法。甚至比赛可能会出现这种情况。

[1] & [2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]

大型团队处于劣势。例如，对于国际象棋团队比赛，如果1队和2队之间的水平差距很大，这种情况就会出现。

即使是你提到的“不公平”的匹配：

[1,2,3,4,13,14,15,16] & [5,6,7,8,9,10,11,12]

在像棒球这样的比赛中，可能会完全公平。毕竟，13-16岁的球员仍然需要击球！

因此，最公平的做法可能就是随机选择队伍。这也避免了任何形式的“操纵”系统(就像我和我的朋友们在高中体育课上做的那样：) )。

- BlueRaja - Danny Pflughoeft

公平，就像美丽一样，是在观察者的眼中。但如果随机团队选择器产生了A = [1..8]和B = [9..16]，我会同意B团队的领导者的看法。 - High Performance Mark

3

我认为没有足够的信息来确定答案。

对于某人成为＃1与＃2之间的差别，真正意义是什么？他们是否比较优秀50％，还是10％或1％？＃1与＃5相比有多少优势？真正需要准确的是分配值的算法，分布算法需要正确反映这一点。

例如，就像我说的，如果你把科比·布莱恩特和一群高中篮球孩子混在一起，相对价值会是多少呢？因为在篮球比赛中，科比·布莱恩特可以独自击败所有的高中孩子。那么他的排名是＃1，其他孩子是＃1000+吗？

此外，您必须假设价值确定考虑到团队的规模。团队只需要两个球员吗？还是需要10个？在后一种情况下，您的第二个例子似乎还不错，因为前4名球员将与6个非常糟糕的球员一起比赛，这可能会影响成功。

如果您所做的只是分配值，并且如果“公平性”的概念内置于价值系统中，则平均值似乎是分配球员的公平方式。

- steve8918

抱歉，我早些时候应该表述得更清楚。元素之间的变化可以被视为恒定不变。我想这样可以允许变化为0，因此所有团队都是平等的 - 这是一个无用的结果！鉴于变异的一致性（#1比#2好x％，比#3好2x％），是否有一些算法适用于这种特定级别的精确度？ - spoxox

1

你需要一种迭代排名方法，带有自动选择功能，以在每次迭代中产生均匀排名的团队。即使参与者的混合在一定程度上随时间变化，这也可以实现。我为我的5人制小组创建了一个工具，然后向所有人开放，如果你搜索“公平团队选择器”，就可以找到它。

- John Pollard

0

首先，第一个人选择1。然后他们轮流选择2。

假设：

要选择的元素数量为偶数
每个选择者对每个元素给出相同的价值
元素的价值非常相似但不同
价值越低越好

[最佳] 首先，第一个人选择1。然后他们轮流选择2：

16 items                             average
Team 1: 1, 4, 5, 8, 9, 12, 13, 16      8.5
Team 2: 2, 3, 6, 7, 10, 11, 14, 15     8.5

14 items                             average
Team 1: 1, 4, 5, 8, 9, 12, 13          7.42857
Team 2: 2, 3, 6, 7, 10, 11, 14         7.57143

选择第一个1，第二个2，然后每次选择1。

16 items                             average
Team 1: 1, 4, 6, 7, 10, 11, 14, 15     8.875
Team 2: 2, 3, 5, 8, 9, 12, 13, 16      8.125

14 items                             average
Team 1: 1, 4, 5, 8, 9, 12, 13          7.42857
Team 2: 2, 3, 6, 7, 10, 11, 14         7.57143

[最差]与每次选择1进行比较：

16 items                             average
Team 1: 1, 3, 5, 7, 9, 11, 13, 15      8
Team 2: 2, 4, 6, 8, 10, 12, 14, 16     9

16 items                             average
Team 1: 1, 3, 5, 7, 9, 11, 13          7
Team 2: 2, 4, 6, 8, 10, 12, 14         8

- Dodger

这种方法可能和其他方法一样好，但它把序数当作基数来处理，这显然是一个致命的错误。虽然在这些末日中，这种错误被广泛地实践。 - High Performance Mark

这种方法并不比其他方法更好。如果是这样，结果将是相等的。我答案中的数字代表值而不是顺序（因为顺序表示从左到右的选择顺序）。请随意使用我的假设更改值，并发布结果以向我们展示它与任何其他方法一样好。您也可以使用其他假设，但不能与我的答案进行比较，因为这没有意义。 - Dodger

0

如果每个“轮次”选择的顺序都是前一轮的反向顺序，那么团队不就是平等的吗？如果有10名才华为1-10的球员，我们正在创建5个团队（每个团队2名球员），第一轮中，第一个选择显然会选择最好的球员（才华水平为10）。然后下一个选择将是9，依此类推。第5个选择将得到才华水平为6的球员。在第二轮中，选择顺序被颠倒，因此刚刚获得才华水平6的团队将选择才华水平5（剩下的最高水平），以此类推，直到在第一轮中选择第一名的队长得到最后一名球员（才华水平为1）。因此，每个团队都有11个才华水平，其中一个团队有10和1，下一个团队有9和2，依此类推。这适用于任意数量的球员/团队。

- David B

0

从上面的模式。 A队：1、4、5、8、9、12、13、16 B队：2、3、6、7、10、11、14、15 使用模式沿着列表穿梭 A-B-B-A；A-B-B-A；等等。这个选择很容易编码。将所有有序的球员列表放入成对的位置。反转每一个奇数#对（假设第一个对是第0组）。然而，使用Thue-Morse算法进行团队组建有一个“更好”的方法。关于该算法的更详细描述，请参见：https://www.youtube.com/watch?v=prh72BLNjIk

- Bob Munds

酷，谢谢你介绍Thue-Morse给我。 - spoxox

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- High Performance Mark · Accepted Answer

你的第二个例子比第一个更长，但在我看来并不不公平。实际上，它符合您似乎认为是第一个例子的首选答案。

这就是你问题中与编程无关的核心。你拥有序数，但需要基数。要将前者转换为后者，您必须定义自己的映射，没有通用的现成方法。

例如，您可以依次比较2组中的每个元素，例如a1 vs b1, a2 vs b2...，如果a比b更好的情况数量与b比a更好的情况数量大致相同，则将两组视为足够均匀即可。

但对于您的应用程序，我认为您不需要比游乐场算法更复杂的东西，每个团队负责人选择最佳未被选择的球员并轮流选择即可。为什么需要更复杂的算法呢？