Parameterized Analysis of Bribery in Challenge the Champ Tournaments
Authors: Juhi Chaudhary, Hendrik Molter, Meirav Zehavi
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show that the problem is weakly NP-hard and W[1]-hard when parameterized by the number of players. On the algorithmic side, we show that the problem is fixed-parameter tractable (FPT) when parameterized either by the number of different bribe values or the number of different probability values. To this end, we establish several results that are of independent interest. In particular, we show that the product knapsack problem is W[1]-hard when parameterized by the number of items in the knapsack, and that constructive bribery for cup tournaments is W[1]-hard when parameterized by the number of players. Furthermore, we present a novel way of designing mixed integer linear programs, ensuring optimal solutions where all variables are integers. |
| Researcher Affiliation | Academia | Juhi Chaudhary 1 , Hendrik Molter 2 , Meirav Zehavi 2 1School of Technology and Computer Science, TIFR, Mumbai, India 2Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva, Israel juhi.chaudhary@tifr.res.in, molterh@post.bgu.ac.il, meiravze@bgu.ac.il |
| Pseudocode | No | The paper describes mathematical formulations (MILPs) and provides proofs, but it does not include any specific pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not contain any statement about making its source code available or provide a link to a code repository for the methodology described. |
| Open Datasets | No | This is a theoretical paper on computational complexity and algorithm design; it does not use or refer to any datasets for training, validation, or testing. |
| Dataset Splits | No | This is a theoretical paper and does not describe experimental validation on data splits. |
| Hardware Specification | No | This is a theoretical paper that does not describe any computational experiments, thus no hardware specifications are mentioned. |
| Software Dependencies | No | The paper discusses mixed integer linear programs (MILPs) and references theoretical results on their solvability, but it does not specify any particular software, solvers, or their version numbers used for implementation or experimentation. |
| Experiment Setup | No | This is a theoretical paper focusing on computational complexity and algorithm design; therefore, it does not describe an experimental setup, hyperparameters, or training configurations. |