Controlling sub-tournaments: easy or hard problem? Theoretical vs. practical analysis

摘要

Is it possible for the organizers of a sports tournament to influence the identity of the final winner by manipulating the initial seeding of the tournament? Is it possible to ensure a specific good (i.e. king) player will win at least a certain number of rounds in the tournament? This paper investigates these questions both by means of a theoretical method and a practical approach. The theoretical method focuses on the attempt to identify sufficient conditions to ensure a king player will win at least a pre-defined number of rounds in the tournament. It seems that the tournament must adhere to very strict conditions to ensure the outcome, suggesting that this is a hard problem. The practical approach, on the other hand, uses the Monte Carlo method to demonstrate that these problems are solvable in realistic computational time. A comparison of the results lead to the realization that players with equivalent representation might relax the actual complexity of the problem, and enable manipulation of tournaments that can be controlled in reality.