Rigging Tournament Brackets for Weaker Players
Isabelle Stanton and Virginia Vassilevska Williams
Consider the following problem in game manipulation. A tournament designer who has full knowledge of the match outcomes between any possible pair of players would like to create a bracket for a balanced single-elimination tournament so that their favorite player will win. Although this problem has been studied in the areas of voting and tournament manipulation, it is still unknown whether it can be tackled in polynomial time. We focus on identifying several general cases for which the tournament can always be fixed efficiently for the given player. We give constructive proofs that, under some natural assumptions, if a player is ranked among the top K players, then one can efficiently fix the tournament for the given player, even when K is a constant fraction of the number of players.