Computational Aspects of Nearly Single-Peaked Electorates
Authors: Gábor Erdélyi, Martin Lackner, Andreas Pfandler
JAIR 2017 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We prove that determining whether a given profile is nearly single-peaked is NP-complete in many cases. For one case we present a polynomial-time algorithm. In case the single-peaked axis is given, we show that determining the distance is always possible in polynomial time. Furthermore, we explore the relations between the new notions introduced in this paper and existing notions from the literature. We analyze the computational complexity of computing the distance of arbitrary preference profiles to single-peakedness. In most cases we show NP-completeness. For the k-candidate deletion distance, we present a polynomial-time algorithm. |
| Researcher Affiliation | Academia | Gabor Erdelyi EMAIL School of Economic Disciplines University of Siegen Siegen, Germany. Martin Lackner EMAIL Department of Computer Science University of Oxford Oxford, United Kingdom. Andreas Pfandler EMAIL Institute of Information Systems TU Wien Vienna, Austria. |
| Pseudocode | Yes | Algorithm 1: Polynomial-time algorithm for k-candidate deletion single-peaked consistency Theorem 6.16 |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code for the methodology described, nor does it provide links to a code repository. |
| Open Datasets | No | The paper focuses on theoretical computational complexity aspects of nearly single-peaked electorates and preference profiles. It does not describe or use any specific datasets for empirical evaluation or provide any access information for such. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments using datasets, therefore, there is no information about dataset splits. |
| Hardware Specification | No | The paper presents theoretical results and algorithms. It does not describe any experimental setup or specify hardware used for running experiments. |
| Software Dependencies | No | The paper is theoretical and focuses on computational complexity and algorithms. It does not specify any software dependencies with version numbers used for experimental implementation. |
| Experiment Setup | No | The paper is purely theoretical, presenting proofs and algorithms. It does not describe any empirical experimental setup, hyperparameters, or training configurations. |