A single-elimination (SE) tournament is a popular way to select a winner in both sports competitions and in elections. A natural and well-studied question is the tournament fixing problem (TFP): given the set of all pairwise match outcomes, can a tournament organizer rig an SE tournament by adjusting the initial seeding so that their favorite player wins? We prove new sufficient conditions on the pairwise match out-come information and the favorite player, under which there is guaranteed to be a seeding where the player wins the tournament. Our results greatly generalize previous results. We also investigate the relationship between the set of players that can win an SE tournament under some seeding (so called SE winners) and other traditional tournament solutions. In addition, we generalize and strengthen prior work on probabilistic models for generating tournaments. For instance, we show that every player in an n player tournament generated by the Condorcet Random Model will be an SE winner even when the noise is as small as possible, p = Θ(ln n/n); prior work only had such results for p ≥ Ω({the square root of}(ln n/n)). We also establish new results for significantly more general generative models.
展开▼
机译：单一消除（SE）锦标赛是在体育比赛和选举中选择胜利者的热门方式。一个自然和良好的问题是锦标赛修复问题（TFP）：鉴于所有成对匹配结果的集合，可以通过调整最初的播种来调整锦标赛的锦标赛组织者钻机，以便他们最喜欢的球员获胜？我们在成对匹配的信息和最喜欢的球员上证明了新的充分条件，保证了玩家赢得锦标赛的播种。我们的结果极大地概括了以前的结果。我们还调查了可以在一些播种机（所谓的获奖者）和其他传统锦标赛解决方案下赢得SE锦标赛的球员之间的关系。此外，我们概括并加强了对发电锦标赛的概率模型的先前工作。例如，我们表明，即使噪声尽可能小，N播放器随机模型生成的N播放机锦标赛中的每个玩家都将是SE赢家，P =θ（Ln N / N）;在P≥ω的情况下，仅具有此类结果（{}的平方根（ln n / n））。我们还为更普遍的一般性模型建立了新的结果。
展开▼
