Incomplete Preferences in Single-Peaked Electorates
DOI:
https://doi.org/10.1609/aaai.v28i1.8822Keywords:
Algorithms, Computational Social Choice, Single-Peaked, PreferencesAbstract
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.
Downloads
Published
2014-06-21
How to Cite
Lackner, M. (2014). Incomplete Preferences in Single-Peaked Electorates. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1). https://doi.org/10.1609/aaai.v28i1.8822
Issue
Section
AAAI Technical Track: Game Theory and Economic Paradigms