ML Anthology

Incomplete Preferences in Single-Peaked Electorates

Martin Lackner
AAAI 2014 pp. 742-748
doi:10.1609/AAAI.V28I1.8822 /aaai/2014/lackner2014aaai-incomplete/

Abstract

Incomplete preferences are likely to arise in real-world preference aggregation and voting systems. This paper deals with determining whether an incomplete preference profile is single-peaked. This is essential information since many intractable voting problems become tractable for single-peaked profiles. We prove that for incomplete profiles the problem of determining single-peakedness is NP-complete. Despite this computational hardness result, we find four polynomial-time algorithms for reasonably restricted settings.

PDF AAAI Semantic Scholar

Cite

Text

Lackner. "Incomplete Preferences in Single-Peaked Electorates." AAAI Conference on Artificial Intelligence, 2014. doi:10.1609/AAAI.V28I1.8822

Markdown

[Lackner. "Incomplete Preferences in Single-Peaked Electorates." AAAI Conference on Artificial Intelligence, 2014.](https://mlanthology.org/aaai/2014/lackner2014aaai-incomplete/) doi:10.1609/AAAI.V28I1.8822

BibTeX

@inproceedings{lackner2014aaai-incomplete,
  title     = {{Incomplete Preferences in Single-Peaked Electorates}},
  author    = {Lackner, Martin},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2014},
  pages     = {742-748},
  doi       = {10.1609/AAAI.V28I1.8822},
  url       = {https://mlanthology.org/aaai/2014/lackner2014aaai-incomplete/}
}