Parameterized Analysis of Bribery in Challenge the Champ Tournaments
Authors: Juhi Chaudhary, Hendrik Molter, Meirav Zehavi
JAIR 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We start with establishing the (classical) computational complexity of CBCCT. In Section 3 we show the following. CBCCT is weakly NP-complete. This motivates developing parameterized algorithms [13, 16, 35] for the problem. ... On the algorithmic side, we show that the problem is fixed-parameter tractable 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 , School of Technology & Computer Science, Tata Institute of Fundamental Research, India HENDRIK MOLTER, Department of Computer Science, Ben-Gurion University of the Negev, Israel MEIRAV ZEHAVI, Department of Computer Science, Ben-Gurion University of the Negev, Israel |
| Pseudocode | No | The paper describes Mixed Integer Linear Program (MILP) formulations and their constraints and objective functions in mathematical notation, but it does not present them in structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not contain any explicit statement about releasing source code, nor does it provide any links to a code repository or mention code in supplementary materials. |
| Open Datasets | No | The paper focuses on theoretical computational complexity analysis of a problem and does not involve experiments on specific datasets. Therefore, it does not use or provide access to any open datasets for empirical evaluation. |
| Dataset Splits | No | The paper focuses on theoretical computational complexity analysis and does not involve experiments on datasets. Therefore, there is no mention of dataset splits. |
| Hardware Specification | No | The paper focuses on theoretical computational complexity and algorithmic results. It does not describe any empirical experiments that would require specific hardware specifications. |
| Software Dependencies | No | The paper focuses on theoretical computational complexity and algorithmic results, particularly involving Mixed Integer Linear Programs. While it mentions MILPs are solvable in FPT-time with respect to the number of integer variables, it does not specify any particular software or solver names with version numbers used for implementation or testing. |
| Experiment Setup | No | The paper focuses on theoretical computational complexity and algorithmic results. It does not describe any empirical experiments, and therefore, no experimental setup details, hyperparameters, or training configurations are provided. |