2026-08-11T06:20:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11688 2024-03-06T10:48:27Z ddc:004 open_access

Approximately Strategyproof Tournament Rules: On Large Manipulating Sets and Cover-Consistence Schvartzman, Ariel Weinberg, S. Matthew Zlatin, Eitan Zuo, Albert Tournament design Non-manipulability Cover-consistence Strategyproofness We consider the manipulability of tournament rules, in which n teams play a round robin tournament and a winner is (possibly randomly) selected based on the outcome of all binom{n}{2} matches. Prior work defines a tournament rule to be k-SNM-α if no set of ≤ k teams can fix the ≤ binom{k}{2} matches among them to increase their probability of winning by >α and asks: for each k, what is the minimum α(k) such that a Condorcet-consistent (i.e. always selects a Condorcet winner when one exists) k-SNM-α(k) tournament rule exists? A simple example witnesses that α(k) ≥ (k-1)/(2k-1) for all k, and [Jon Schneider et al., 2017] conjectures that this is tight (and prove it is tight for k=2). Our first result refutes this conjecture: there exists a sufficiently large k such that no Condorcet-consistent tournament rule is k-SNM-1/2. Our second result leverages similar machinery to design a new tournament rule which is k-SNM-2/3 for all k (and this is the first tournament rule which is k-SNM-(<1) for all k). Our final result extends prior work, which proves that single-elimination bracket with random seeding is 2-SNM-1/3 [Jon Schneider et al., 2017], in a different direction by seeking a stronger notion of fairness than Condorcet-consistence. We design a new tournament rule, which we call Randomized-King-of-the-Hill, which is 2-SNM-1/3 and cover-consistent (the winner is an uncovered team with probability 1). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ariel Schvartzman and S. Matthew Weinberg and Eitan Zlatin and Albert Zuo 2020 Is Part Of LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2020.3 urn:nbn:de:0030-drops-116881 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.3 eng https://creativecommons.org/licenses/by/3.0/legalcode