平衡二部图中随机匹配问题:体育抽签机制的(不)公平性

Random matching in balanced bipartite graphs: The (un)fairness of draw mechanisms used in sports

摘要 Abstract

某些淘汰赛的分组抽签需要在平衡二部图中寻找完美匹配。当存在抽签约束时,体育比赛中常用的两种场 proven 方法被证明是非均匀分布的(可行匹配并非等概率出现),这可能威胁到公平性。我们针对合理大小的平衡二部图子集(最多16个节点),比较了这两种机制及其各自两种形式的偏差。在合理的限制条件下,发现一种机制在四分之一决赛抽签中优于其他所有机制。验证结果显示,欧洲冠军联赛16强抽签在2003/04至2023/24赛季期间采用了四种可用设计中的最佳方案。然而,这些随机化程序仍有很大的改进空间,特别是它们往往以相同的方向和大致相同的幅度扭曲概率。

The draw of some knockout tournaments requires finding a perfect matching in a balanced bipartite graph. The problem becomes challenging with draw constraints: the two field-proven procedures used in sports are known to be non-uniformly distributed (the feasible matchings are not equally likely), which may threaten fairness. We compare the biases of both mechanisms, each of them having two forms, for reasonable subsets of balanced bipartite graphs up to 16 nodes. A mechanism is found to dominate all others in the draw of quarterfinals under reasonable restrictions. The UEFA Champions League Round of 16 draw is verified to apply the best design among the four available options between the 2003/04 and 2023/24 seasons. However, considerable scope remains to improve the performance of these randomisation procedures, especially because they tend to distort the probabilities in the same direction and roughly with the same magnitude.

平衡二部图中随机匹配问题:体育抽签机制的(不)公平性 - arXiv