算法能否使锦标赛作弊行为消失？

lixia01

我们制定了一项锦标赛规则，试图满足三个关键标准，使团队勾结或操纵比赛变得毫无意义。我们发现，制定一条满足所有三个标准的规则是不可能的，但团队的自私通常可以首先防止勾结。
比赛作弊在电影和书籍中经常出现，但在现实生活中很少发生。尽管如此，还是有一些影响深远的著名案例。因此，研究体育比赛组织者如何制定比赛规则以减少甚至消除作弊动机是有用的。事实上，计算机科学研究中常用的一些算法方法特别适合特定类型的体育勾结：即球队意识到故意输球可以帮助他们的球队（或球队）。
根据所使用的积分系统，循环赛（每支球队互相比赛一次）和基于种子的锦标赛允许球队故意输球以帮助另一支球队晋级，或者为了帮助彼此同时晋级。
“锦标赛”当然是一个常见的体育术语，但它也是图论中的一个术语，描述连接对象之间具有成对关系的模型，而这恰好直接适用于体育锦标赛的运作方式。
假设你组织了一场锦标赛，每支球队都互相比赛一次，不允许平局。这看起来像一张锦标赛图表，其中每对球队都用一条线连接起来，箭头指向这两支球队之间的比赛的失败者。为了设计一场完全公平的锦标赛，让串通或故意输球变得毫无意义，决定谁是赢家的规则应该符合以下三个期望属性：
击败所有其他球队的球队就是整个锦标赛的获胜者（如果存在的话）。
每支球队都有动力赢得每场比赛。
组建假球联盟不会给球队带来任何好处。
在“关于规模至少为三的勾结的近似防策略锦标赛规则”中，我们着手设计一个满足上述属性 1 和 2 的锦标赛规则，以及属性 3 的放宽版本。然后，在“面向具有部分可转移效用的锦标赛的公平和防策略锦标赛规则”中，我们试图创建一个锦标赛模型，通过假设和纳入每支球队的自私程度，接受并处理满足 1 和 3 的数学不可能性。我们表明，如果勾结的潜在收益大于球队的自私程度乘以其个人牺牲，则任何公平的锦标赛规则都无法防止操纵，并且我们根据少数球队的自私参数，通过计算求解公平（即满足上述属性 1 和 2）和防操纵的锦标赛规则。
设计规则
在我们设计规则并根据我们期望的特性测试它们之前，我们需要建立一种数学语言来选择获胜者并改变锦标赛的结果。我们试图制定一个锦标赛规则，即一种根据结果选择获胜者的方法，使串通过时。我们还假设我们已经观察到了循环赛式锦标赛中所有比赛的结果。
假设有一组球队（S）想要在锦标赛（T）中操纵比赛。我们假设S中的球队能够操纵的比赛只有两支球队都在S中的比赛。“S相邻”锦标赛是指所有涉及非S球队的比赛结果相同的锦标赛。
在此基础上，我们重新表述了前面提到的三个期望属性：
如果有一支队伍击败了所有其他队伍，则认为该队伍获胜的概率为 100%。
一支球队不可能因为故意输球而获益。
对于任意两个 S 相邻锦标赛，对于至少两个球队的任何子集，任何子集球队获胜的综合概率在T 1 和T 2中应该相同。
结果
很容易找到满足三个所需属性中的两个的规则。但是，您可以分别满足规则 3 或 1，但不能同时满足。例如，一条规则赋予每支球队每赢得一场比赛 1/(n(n - 1)/2) 的获胜机会，这可以满足属性 2 和 3，但奇怪的是，它会导致不败球队的获胜机会低于 100%，这违反了属性 1。或者，如果有不败球队，我们可以挑选一支不败球队作为获胜者，如果没有，我们可以随机选择一支获胜球队（当然，这也是一条奇怪的规则）。这将满足属性 1 和 2，但不满足属性 3；在成对的比赛中，球队可以合谋让其中一支球队成为不败球队，这将使这些球队的获胜机会从不比随机好多少提高到 100%。下面显示了一个这样的实例，其中选择不同类型的规则以不同的方式满足这些属性。
我们研究了理论和实践中流行的规则，以寻找满足我们要求的规则，但发现从数学上讲，设计满足属性 1 和 3 的规则是不可能的，即使允许随机规则。
做出调整
鉴于满足所有三个期望属性在数学上是不可能的，人们可以尝试找到满足属性 1 和 2（也许还有其他一些期望属性）的规则，同时尽量不违反属性 3。考虑以下选择获胜者的方式：观察所有比赛后，抽取一个随机单淘汰制括号（如下所示），并用观察到的结果填写括号，直到产生获胜者。先前的研究表明，对于大小为 2 的合谋集合，此规则满足属性 1 和 2，而仅尽量不违反属性 3。违反属性 3 的程度是通过违反属性 3 的操纵的最坏情况收益来衡量的。在上述规则中，通过操纵获胜的几率最多增加 33%。最近，提出了一条明确的规则，该规则满足属性 1 和 2，并且对于大小为 3 的集合次优地满足属性 3，这意味着规则的保证与已知最坏情况之间存在差距，已知最坏情况的操纵收益最多为 51.6%。
我们的研究提出了一条不同的规则，该规则略微（但仍然不是最佳的）减少了操纵带来的潜在收益。我们提出的理论规则将一小部分团队确定为“重要”，我们将其定义为可以组成联盟并导致联盟中的团队成为明显赢家的团队。
我们将每个可能的锦标赛结果分为五个类别之一，具体取决于某支球队赢得所有比赛的几率。如果锦标赛中有一支球队赢得所有比赛，我们将宣布该球队为获胜者。如果锦标赛中没有一支球队赢得所有比赛，我们将随机选择一个获胜者。对于“接近”赢得所有比赛的锦标赛，我们会确定那些可以通过操纵锦标赛获得可观收益的球队。我们证明这样的球队并不多，并且对于每个“接近”的锦标赛，我们为每支球队分配特定的概率，以便规模为三的球队从操纵中获得的收益最多为 50%（规模为二的球队仍然是最佳的 33%）。
人们对我们的模型普遍存在的一个担忧是，我们假设所有基本事实的结果都是确定性的，例如 A 总是击败 B，这可能与真实比赛不符。毕竟，弱者总是有机会的！如果我们允许随机结果，例如 A 80% 的时间击败 B，我们的结果是否成立？事实证明，由于先前的研究，这个问题的答案是“是”，因为最坏的情况是那些具有确定性结果的情况。相关研究表明，如果我们将所有游戏的获胜概率限制在 60-40% 的区间内，那么随着比赛变得更加激烈，我们可以预期操纵带来的收益会减少。
为了克服我们之前提出的不可能结果，我们引入了一个新模型来确定哪些操纵是有益的。在迄今为止概述的模型中，操纵联盟中的团队将其获胜的联合概率视为一个统一的整体。也就是说，联盟中的团队并不关心其他团队获胜的机会是上升还是下降，即使是他们自己的团队——这种假设不太可能发生，因为团队自然会关心自己的获胜机会，或者至少有点自私。为了模拟操纵联盟中的团队仍然有点自私的假设，我们在操纵计算中引入了权重来反映这一点。
我们观察到，如果每支球队对自己获胜机会的权重是操纵联盟中其他球队的两倍，那么对于最多有六支球队的锦标赛，存在满足属性 1 和 3 的规则。我们推测，在这个模型下，可能确实存在完全满足属性 1 和 3 的规则。我们还表明，对于几条流行的规则，需要很大的权重才能使规则满足属性 1 和 3。
结论
体育比赛中使用的许多流行规则都具有高度可操纵性，实际上可以反映计算机科学研究中常用的一些算法方法。然而，在高风险比赛中，勾结和操纵比赛仍然很少见，这表明模型的某些部分（例如考虑最坏情况而不是平均情况）未能反映现实。或者，正如我们的研究表明的那样，团队足够自私，以至于操纵带来的收益与他们个人的损失相比微不足道，这就是为什么勾结在高风险体育比赛中很少见的原因。
致谢
本文讨论的两篇研究论文分别与 Jan Soukup 和 David Mikšaník 以及 David Pennock 和 Eric Xue 合作完成。我还要感谢 Jon Schneider、Matt Weinberg、Eitan Zlatin 和 Albert Zuo，他们中的一些人现在在 Google 工作，是之前工作的合作者。