Robust Draws in Balanced Knockout Tournaments
Authors: Krishnendu Chatterjee, Rasmus Ibsen-Jensen, Josef Tkadlec
IJCAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | First, we present several illuminating examples to establish: (a) there exist deterministic tournaments (where the pairwise winning probabilities are 0 or 1) where one optimal draw is much more robust than the other; and (b) in general, there exist tournaments with slightly suboptimal draws that are more robust than all the optimal draws. The above examples motivate the study of the computational problem of robust draws that guarantee a specified winning probability. Second, we present a polynomial-time algorithm for approximating the robustness of a draw for sufficiently small errors in pairwise winning probabilities, and obtain that the stated computational problem is NP-complete. We also show that two natural cases of deterministic tournaments where the optimal draw could be computed in polynomial time also admit polynomial-time algorithms to compute robust optimal draws. |
| Researcher Affiliation | Academia | IST Austria {krish.chat,ribsen,jtkadlec}@ist.ac.at |
| Pseudocode | No | The paper describes algorithms and mathematical proofs, but it does not include any explicitly labeled pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any statement or link indicating that open-source code for the described methodology is available. |
| Open Datasets | No | The paper is theoretical and does not involve the use of datasets for training or other empirical evaluations. The examples are theoretical constructs. |
| Dataset Splits | No | The paper is theoretical and does not involve the use of datasets with training/validation/test splits. |
| Hardware Specification | No | The paper does not specify any hardware used for computations or experiments. |
| Software Dependencies | No | The paper does not mention any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup involving hyperparameters or training configurations. |