Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Adaptive Manipulation for Coalitions in Knockout Tournaments
Authors: Juhi Chaudhary, Hendrik Molter, Meirav Zehavi
AAAI 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We investigate the computational problem of determining whether, for a given tournament, a coalition has a manipulation strategy that increases the winning probability of a designated player above a given threshold. ... We show that the above problem is hard for every complexity class in the polynomial hierarchy. On the algorithmic side, we show that the problem is solvable in polynomial time when the coalition size is a constant. Furthermore, we show that the problem is fixed-parameter tractable... We present the hardness results in Section 4 and the algorithmic results in Section 5. |
| Researcher Affiliation | Academia | 1School of Technology and Computer Science, Tata Institute of Fundamental Research, Mumbai, India. 2Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva, Israel. |
| Pseudocode | No | We start by describing a dynamic programming algorithm. To this end, we need to introduce some concepts first. ... Let S 2{e1,e2,...,en} be the set of all possible configurations. We create a dynamic program M : {0, 1, 2, . . . , r} S [0, 1] that maps a level Li of TC together with a valid configuration S for Li to the probability that e wins assuming the players in S are seeded directly into their positions in Li and assuming the coalition players maximize the winning probability of e . We define M as follows. We have M[0, {e }] = 1, and for all S {e1, e2, . . . , en} with S = {e }, we have M[0, S] = 0. Let S {e1, e2, . . . , en} be valid for Li for i > 0, then we have Equation (1) in Fig. 2. The paper describes the dynamic programming approach and provides a mathematical equation (Equation 1 in Figure 2) for its recurrence relation, but does not present a structured pseudocode or algorithm block. |
| Open Source Code | No | The paper does not provide any explicit statement about open-sourcing code or links to a code repository. |
| Open Datasets | No | On the one hand, it is rarely conceivable that the outcomes of all possible matches will be deterministic i.e., that we can always be completely certain, in advance, who beats whom. To overcome this, we employ the standard probabilistic model for knockout tournaments, which is also used by Mattei et al. (Mattei et al. 2015). Here, for every two players, we know some estimate of the probability of one beating the other. Such estimations can often be derived from available statistics regarding past matches; see, e.g., (ESPN; Predict; Team; 538). The paper references general sources for probability estimations but does not use specific datasets for experimental evaluation, nor does it provide access information for any open datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve experimental evaluation using datasets, thus no dataset split information is provided. |
| Hardware Specification | No | The paper is theoretical, focusing on complexity results and algorithms, and does not report on any experiments that would require specific hardware. |
| Software Dependencies | No | The paper primarily presents theoretical results and algorithms. It does not specify any particular software dependencies with version numbers used for implementation or experimental evaluation. |
| Experiment Setup | No | The paper is theoretical, focusing on mathematical and algorithmic analysis, and therefore does not include details on experimental setup, hyperparameters, or training configurations. |