Bribery in Balanced Knockout Tournaments

Balanced knockout tournaments comprise a common format for sporting competitions and pairwise decision-making. In this paper, we investigate the computational complexity of arranging the tournament's initial seeding and bribing players to guarantee one player's victory. We give a model of bribery in which the organizer can both arrange the seeding and bribe players to decrease their probability of beating other players at a cost, without exceeding a budget. We also show that it is NP-hard to determine a bribery and a seeding under which a given player wins the tournament with probability 1, even when the pre-bribery matrix is monotonic, and the post-bribery matrix is ϵ-monotonic and very close to the initial one. We also show that for almost all n player inputs generated by a well known deterministic model due to Condorcet, one can always bribe the "top" O(log n) players so that there is an efficiently constructible seeding for which any player wins.