Incomplete Preferences in Single-Peaked Electorates
Abstract
Incomplete preferences are likely to arise in real-world preference aggregation scenarios. This paper deals with determining whether an incomplete preference profile is single-peaked. This is valuable information since many intractable voting problems become tractable given singlepeaked preferences. We prove that the problem of recognizing single-peakedness is NP-complete for incomplete profiles consisting of partial orders. Despite this intractability result, we find several polynomial-time algorithms for reasonably restricted settings. In particular, we give polynomial-time recognition algorithms for weak orders, which can be viewed as preferences with indifference.
Cite
Text
Fitzsimmons and Lackner. "Incomplete Preferences in Single-Peaked Electorates." Journal of Artificial Intelligence Research, 2020. doi:10.1613/JAIR.1.11577Markdown
[Fitzsimmons and Lackner. "Incomplete Preferences in Single-Peaked Electorates." Journal of Artificial Intelligence Research, 2020.](https://mlanthology.org/jair/2020/fitzsimmons2020jair-incomplete/) doi:10.1613/JAIR.1.11577BibTeX
@article{fitzsimmons2020jair-incomplete,
title = {{Incomplete Preferences in Single-Peaked Electorates}},
author = {Fitzsimmons, Zack and Lackner, Martin},
journal = {Journal of Artificial Intelligence Research},
year = {2020},
pages = {797-833},
doi = {10.1613/JAIR.1.11577},
volume = {67},
url = {https://mlanthology.org/jair/2020/fitzsimmons2020jair-incomplete/}
}