Abstract
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 kSNMα 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 Condorcetconsistent (i.e. always selects a Condorcet winner when one exists) kSNMα(k) tournament rule exists?
A simple example witnesses that α(k) ≥ (k1)/(2k1) 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 Condorcetconsistent tournament rule is kSNM1/2. Our second result leverages similar machinery to design a new tournament rule which is kSNM2/3 for all k (and this is the first tournament rule which is kSNM(<1) for all k).
Our final result extends prior work, which proves that singleelimination bracket with random seeding is 2SNM1/3 [Jon Schneider et al., 2017], in a different direction by seeking a stronger notion of fairness than Condorcetconsistence. We design a new tournament rule, which we call RandomizedKingoftheHill, which is 2SNM1/3 and coverconsistent (the winner is an uncovered team with probability 1).
BibTeX  Entry
@InProceedings{schvartzman_et_al:LIPIcs:2020:11688,
author = {Ariel Schvartzman and S. Matthew Weinberg and Eitan Zlatin and Albert Zuo},
title = {{Approximately Strategyproof Tournament Rules: On Large Manipulating Sets and CoverConsistence}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {3:13:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771344},
ISSN = {18688969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11688},
URN = {urn:nbn:de:0030drops116881},
doi = {10.4230/LIPIcs.ITCS.2020.3},
annote = {Keywords: Tournament design, Nonmanipulability, Coverconsistence, Strategyproofness}
}
Keywords: 

Tournament design, Nonmanipulability, Coverconsistence, Strategyproofness 
Seminar: 

11th Innovations in Theoretical Computer Science Conference (ITCS 2020) 
Issue Date: 

2020 
Date of publication: 

10.01.2020 