Manipulating Stochastically Generated Single-Elimination Tournaments for Nearly All Players

摘要

We study the power of a tournament organizer in manipulating the outcome of a balanced single-elimination tournament by fixing the initial seeding. This problem is known as agenda control for balanced voting trees. It is not known whether there is a polynomial time algorithm that computes a seeding for which a given player can win the tournament, even if the match outcomes for all pairwise player match-ups are known in advance. We approach the problem by giving a sufficient condition under which the organizer can always efficiently find a tournament seeding for which the given player will win the tournament. We then use this result to show that for most match outcomes generated by a natural random model attributed to Condorcet, the tournament organizer can very efficiently make a large constant fraction of the players win, by manipulating the initial seeding.