Tight Bounds on 3-Team Manipulations in Randomized Death Match

Consider a round-robin tournament on n teams, where a winner must be (possibly randomly) selected as a function of the results from the (n2) pairwise matches. A tournament rule is said to be k-SNM- α if no set of k teams can ever manipulate the (k2) pairwise matches between them to improve the joint probability that one of these k teams wins by more than α. Prior work identifies multiple simple tournament rules that are 2-SNM-1/3 (Randomized Single Elimination Bracket [17], Randomized King of the Hill [18], Randomized Death Match [6]), which is optimal for k= 2 among all Condorcet-consistent rules (that is, rules that select an undefeated team with probability 1). Our main result establishes that Randomized Death Match is 3-SNM-(31/60), which is tight (for Randomized Death Match). This is the first tight analysis of any Condorcet-consistent tournament rule and at least three manipulating teams. Our proof approach is novel in this domain: we explicitly find the most-manipulable tournament, and directly show that no other tournament can be more manipulable. In addition to our main result, we establish that Randomized Death Match disincentivizes Sybil attacks (where a team enters multiple copies of themselves into the tournament, and arbitrarily manipulates the outcomes of matches between their copies). Specifically, for any tournament, and any team u that is not a Condorcet winner, the probability that u or one of its Sybils wins in Randomized Death Match approaches 0 as the number of Sybils approaches ∞.