Abstract
We consider the manipulability of tournament rules for roundrobin tournaments of n competitors. Specifically, n competitors are competing for a prize, and a tournament rule r maps the result of all n(n1)/2 pairwise matches (called a tournament, T) to a distribution over winners. Rule r is Condorcetconsistent if whenever i wins all n1 of her matches, r selects i with probability 1.
We consider strategic manipulation of tournaments where player j might throw their match to player i in order to increase the likelihood that one of them wins the tournament. Regardless of the reason why j chooses to do this, the potential for manipulation exists as long as Pr[r(T) = i] increases by more than Pr[r(T) = j] decreases. Unfortunately, it is known that every Condorcetconsistent rule is manipulable. In this work, we address the question of how manipulable Condorcetconsistent rules must necessarily be  by trying to minimize the difference between the increase in Pr[r(T) = i] and decrease in Pr[r(T) = j] for any potential manipulating pair.
We show that every Condorcetconsistent rule is in fact 1/3manipulable, and that selecting a winner according to a random single elimination bracket is not alphamanipulable for any alpha > 1/3. We also show that many previously studied tournament formats are all 1/2manipulable, and the popular class of Copeland rules (any rule that selects a player with the most wins) are all in fact 1manipulable, the worst possible. Finally, we consider extensions to matchfixing among sets of more than two players.
BibTeX  Entry
@InProceedings{schneider_et_al:LIPIcs:2017:8160,
author = {Jon Schneider and Ariel Schvartzman and S. Matthew Weinberg},
title = {{CondorcetConsistent and Approximately Strategyproof Tournament Rules}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {35:135:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770293},
ISSN = {18688969},
year = {2017},
volume = {67},
editor = {Christos H. Papadimitriou},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8160},
URN = {urn:nbn:de:0030drops81605},
doi = {10.4230/LIPIcs.ITCS.2017.35},
annote = {Keywords: Tournament design, Nonmanipulability, Condorcetconsistent, Strategyproofness}
}
Keywords: 

Tournament design, Nonmanipulability, Condorcetconsistent, Strategyproofness 
Seminar: 

8th Innovations in Theoretical Computer Science Conference (ITCS 2017) 
Issue Date: 

2017 
Date of publication: 

24.11.2017 