When Rigging a Tournament, Let Greediness Blind You
Lists
Only you see this
Abstract
A knockout tournament is a standard format of competition, ubiquitous in sports, elections and decision making. Such a competition consists of several rounds. In each round, all players that have not yet been eliminated are paired up into matches. Losers are eliminated, and winners are raised to the next round, until only one winner exists. Given that we can correctly predict the outcome of each potential match (modelled by a tournament D), a seeding of the tournament deterministically determines its winner. Having a favorite player v in mind, the Tournament Fixing Problem (TFP) asks whether there exists a seeding that makes v the winner. Aziz et al. [AAAI’14] showed that TFP is NP-hard. They initiated the study of the parameterized complexity of TFP with respect to the feedback arc set number k of D, and gave an XP-algorithm (which is highly inefficient). Recently, Ramanujan and Szeider [AAAI’17] showed that TFP admits an FPT algorithm, running in time 2^{ O(k^2 log k)} n ^{O(1)}. At the heart of this algorithm is a translation of TFP into an algebraic system of equations, solved in a black box fashion (by an ILP solver). We present a fresh, purely combinatorial greedy solution. We rely on new insights into TFP itself, which also results in the better running time bound of 2^{ O(k log k)} n^{ O(1)} . While our analysis is intricate, the algorithm itself is surprisingly simple.
BibTeX
@inproceedings{gupta2018when,
author = {Sushmita Gupta and Sanjukta Roy and Saket Saurabh and Meirav Zehavi},
title = {{When Rigging a Tournament, Let Greediness Blind You}},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2018},
doi = {10.24963/ijcai.2018/38},
}| Fixing a Balanced Knockout Tournament | AAAI · 2014 |
| Fixing Knockout Tournaments With Seeds | arXiv · 2022 |
| Winning a Tournament by Any Means Necessary | IJCAI · 2018 |
| Adaptive Manipulation for Coalitions in Knockout Tournaments | arXiv · 2024 |
| Parameterized Analysis of Bribery in Challenge the Champ Tournaments | arXiv · 2024 |
| Tournament Robustness via Redundancy | arXiv · 2025 |