Fixing Tournaments for Kings, Chokers, and More
Authors: Michael P. Kim, Virginia Vassilevska Williams
IJCAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the tournament fixing problem (TFP), which asks whether a tournament organizer can rig a single-elimination (SE) tournament such that their favorite player wins, simply by adjusting the initial seeding. Prior results give two perspectives of TFP: on the one hand, deciding whether an arbitrary player can win any SE tournament is known to be NP-complete; on the other hand, there are a number of known conditions, under which a player is guaranteed to win some SE tournament. We extend and connect both these lines of work. We show that for a number of structured variants of the problem, where our player is seemingly strong, deciding whether the player can win any tournament is still NP-complete. Dual to this hardness result, we characterize a new set of sufficient conditions for a player to win a tournament. Further, we give an improved exact algorithm for deciding whether a player can win a tournament. |
| Researcher Affiliation | Academia | Michael P. Kim and Virginia V. Williams Computer Science Department Stanford University {michael.kim,virgi}@cs.stanford.edu |
| Pseudocode | Yes | Algorithm 1 COVERB(A, B, E) |
| Open Source Code | No | The paper does not contain any statements or links indicating that source code for the described methodology is publicly available. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments on datasets that require public availability for training purposes. |
| Dataset Splits | No | The paper is theoretical and does not describe empirical experiments with training, validation, or test dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not conduct empirical experiments, thus no hardware specifications for running experiments are provided. |
| Software Dependencies | No | The paper is theoretical and does not conduct empirical experiments that would require specific software dependencies with version numbers for reproducibility. |
| Experiment Setup | No | The paper is theoretical and does not conduct empirical experiments; thus, there are no experimental setup details like hyperparameters or training settings. |