Preferences Single-Peaked on a Circle
Authors: Dominik Peters, Martin Lackner
AAAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We introduce the domain of preferences that are singlepeaked on a circle, which is a generalization of the wellstudied single-peaked domain. ... We give a fast recognition algorithm of this domain, provide a characterisation by finitely many forbidden subprofiles, and show that many popular singleand multi-winner voting rules are polynomialtime computable on this domain. In contrast, Kemeny s rule remains hard to evaluate, and several impossibility results from social choice theory can be proved using only profiles that are single-peaked on a circle. The aim of this paper is to explore this new preference domain in detail. We will find that this domain is algorithmically useful (it often allows for efficient winner determination), but it performs less convincingly in terms of axiomatic properties (since voting paradoxes still occur and impossibility results can still be proven). |
| Researcher Affiliation | Academia | Department of Computer Science University of Oxford, UK |
| Pseudocode | No | The paper describes algorithms verbally and through mathematical formulations (e.g., CC-IP), but does not include structured pseudocode or algorithm blocks. |
| Open Source Code | No | No statement regarding open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not involve the use of datasets for training or experimentation. |
| Dataset Splits | No | The paper is theoretical and does not involve datasets or their partitioning into splits. |
| Hardware Specification | No | The paper is theoretical and does not describe experimental setups requiring specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithms and proofs rather than practical implementations that would require specific software dependencies with version numbers for replication. |
| Experiment Setup | No | The paper is theoretical and does not describe an empirical experimental setup with hyperparameters or training configurations. |