Finding Possible Winners in Spatial Voting with Incomplete Information
Authors: Hadas Shachnai, Rotem Shavitt, Andreas Wiese
IJCAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our results show that the possible winner problem in one dimension is solvable in polynomial time for all k-truncated voting rules with constant k. Moreover, for some scoring rules for which the possible winner problem is NP-complete, such as approval voting for any dimension or k-approval for d 2 dimensions, we give an FPT algorithm parameterized by the number of candidates. Finally, we classify tractable and intractable settings of the weighted possible winner problem in one dimension, and resolve the computational complexity of the weighted case for all two-valued positional scoring rules when d = 1. |
| Researcher Affiliation | Academia | 1Technion Israel Institute of Technology, Israel 2Technical University of Munich, Germany EMAIL, EMAIL, EMAIL |
| Pseudocode | No | Our algorithm decides if there is a solution to the shapes scheduling instance which satisfies Lemma 4. The algorithm exploits certain properties of the sets of possible shapes F(j)t. To this end, we define the notion of P-structured jobs... The heart of our algorithm is formalized as Lemma 6... To ensure that running time is polynomial in the input size, we embed this recursion into a dynamic program with a polynomial number of DP-cells. |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | No | The paper investigates a spatial voting model and its computational complexity, not empirical evaluation on datasets. Therefore, no datasets are used or made open. |
| Dataset Splits | No | No datasets are used for empirical evaluation, so there are no dataset splits mentioned. |
| Hardware Specification | No | The paper presents theoretical results on computational complexity and algorithms, and does not describe any experimental setup that would involve specific hardware. |
| Software Dependencies | No | The paper refers to theoretical approaches like 'integer linear program' and algorithms from literature (e.g., [Lenstra Jr, 1983]), but does not specify any software names with version numbers used for practical implementations or experiments. |
| Experiment Setup | No | The paper is theoretical, focusing on computational complexity and algorithm design, and therefore does not include details on experimental setup, hyperparameters, or training settings. |