Publication: On the Manipulability of Tournament Rules by Throwing Matches
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Access Restrictions
Abstract
A Tournament Rule takes as input a set of reasonable'' tournament rules (i.e. tournament rules so that if team $x$ defeats every other team, it is ranked first with probability $1$), when these two teams fix the match between them. Our work instead considers the possibility that two teams may both fix the match between them, and additionally throw matches to outside teams (that is, they can intentionally lose a match to a non-colluding team that they could have won). Our main result establishes that no two teams can gain more than $1/3$ in expected prize winnings in Nested Randomized King of the Hill (introduced in [DaleFRSW22], similar to QuickSort), by together fixing their match and throwing matches to external teams. This is optimal, as any reasonable'' tournament admits the possibility of two teams gaining