The Complexity of Election Problems with Group-Separable Preferences
Authors: Piotr Faliszewski, Alexander Karpov, Svetlana Obraztsova
IJCAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We analyze the complexity of several NP-hard election-related problems under the assumptions that the voters have group-separable preferences. We show that under this assumption our problems typically remain NP-hard, but we provide more efficient algorithms if additionally the clone decomposition tree is of moderate height.Our algorithm is based on dynamic programming over the clone decomposition tree of the input election. We obtain all our NP-hardness proofs using the same trick. |
| Researcher Affiliation | Academia | 1AGH University, Krakow, Poland 2National Research University Higher School of Economics, Moscow, Russia 3Institute of Control Sciences of Russian Academy of Sciences, Moscow, Russia 4Nanyang Technological University, Singapore |
| Pseudocode | No | The information is insufficient. The paper describes algorithms verbally but does not include any structured pseudocode or clearly labeled algorithm blocks. |
| Open Source Code | No | The information is insufficient. The paper does not provide any concrete access information (specific repository link, explicit code release statement, or code in supplementary materials) for source code related to the methodology. |
| Open Datasets | No | The paper is theoretical and does not involve empirical evaluation on datasets, therefore no information about public dataset availability is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical evaluation on datasets, therefore no information about dataset splits for training, validation, or testing is provided. |
| Hardware Specification | No | The paper is theoretical and does not involve empirical experiments, therefore no hardware specifications are mentioned. |
| Software Dependencies | No | The information is insufficient. The paper is theoretical and does not describe an implementation, thus no specific software dependencies with version numbers are provided. |
| Experiment Setup | No | The paper is theoretical and does not involve empirical experiments, therefore no specific experimental setup details like hyperparameters or training configurations are provided. |