Who Can Win a Single-Elimination Tournament?
Authors: Michael Kim, Warut Suksompong, Virginia Williams
AAAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We prove new sufficient conditions on the pairwise match outcome information and the favorite player, under which there is guaranteed to be a seeding where the player wins the tournament. Our results greatly generalize previous results. We also investigate the relationship between the set of players that can win an SE tournament under some seeding (so called SE winners) and other traditional tournament solutions. In addition, we generalize and strengthen prior work on probabilistic models for generating tournaments. All of our results are constructive. In particular, we demonstrate that certain conditions are sufficient for a player v to be an SE winner by giving algorithms, running in polynomial time, that outputs a seeding where v will win. |
| Researcher Affiliation | Academia | Michael P. Kim, Warut Suksompong, and Virginia Vassilevska Williams Computer Science Department Stanford University |
| Pseudocode | Yes | We will present an algorithm to compute a winning seeding for K. The algorithm will match the players for the first round of the tournament in such a way that the leftover tournament after the first round also satisfies the conditions of the theorem. The description of the algorithm is as follows. 1. Perform a maximal matching M1 from A to H. 2. Since |H| < |A|, we have A\M1 = . Perform a maximal matching M2 (which might be an empty matching) from A\M1 onto I J. 3. If A was not fully used in the two matchings, match an arbitrary unused player in A with K. Else, choose an arbitrary player a A M2 and rematch it to K. 4. Perform arbitrary matchings within A, H, and I J. 5. If there are leftover players, there must be exactly two of them; match them to each other. |
| Open Source Code | No | The paper is theoretical and focuses on mathematical proofs and algorithms. It does not mention or provide any links to open-source code for its methodology. |
| Open Datasets | No | The paper is theoretical and does not involve empirical training on datasets. It discusses 'generative models for tournaments' but these are conceptual models for analysis, not empirical datasets used for training machine learning models. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and describes algorithms and proofs; it does not involve any empirical experiments that would require hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not describe any specific software dependencies or versions required for implementation or execution of experiments. |
| Experiment Setup | No | The paper is theoretical and focuses on mathematical proofs and algorithm design. It does not describe any empirical experiment setup details such as hyperparameters or training configurations. |