Tight Bounds on 3-Team Manipulations in Randomized Death Match

Atanas Dinev, S. Matthew Weinberg

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


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 ∞.

Original languageEnglish (US)
Title of host publicationWeb and Internet Economics - 18th International Conference, WINE 2022, Proceedings
EditorsKristoffer Arnsfelt Hansen, Tracy Xiao Liu, Azarakhsh Malekian
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages19
ISBN (Print)9783031228315
StatePublished - 2022
Event18th International Conference on Web and Internet Economics, WINE 2022 - Troy, United States
Duration: Dec 12 2022Dec 15 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13778 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference18th International Conference on Web and Internet Economics, WINE 2022
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Tight Bounds on 3-Team Manipulations in Randomized Death Match'. Together they form a unique fingerprint.

Cite this