论文标题
用种子修复淘汰赛
Fixing Knockout Tournaments With Seeds
论文作者
论文摘要
淘汰赛构成了组织体育比赛的流行格式。虽然先前的结果表明，通常可以通过固定括号来操纵淘汰赛，但这些结果忽略了玩家种子的普遍方面，这可能会大大限制所选的支架。我们表明，某些确保玩家可以在没有种子的情况下赢得淘汰赛的结构条件不再足够。另一方面，我们证明，当随机生成成对匹配结果时，所有玩家仍然可能在与没有种子的种子相同的概率阈值下都是淘汰赛冠军。此外，我们研究了在存在种子时确定是否可能进行操作的复杂性。
Knockout tournaments constitute a popular format for organizing sports competitions. While prior results have shown that it is often possible to manipulate a knockout tournament by fixing the bracket, these results ignore the prevalent aspect of player seeds, which can significantly constrain the chosen bracket. We show that certain structural conditions that guarantee that a player can win a knockout tournament without seeds are no longer sufficient in light of seed constraints. On the other hand, we prove that when the pairwise match outcomes are generated randomly, all players are still likely to be knockout winners under the same probability threshold with seeds as without seeds. In addition, we investigate the complexity of deciding whether a manipulation is possible when seeds are present.
