Lackner, M. (2014). Incomplete Preferences in Single-Peaked Electorates. In C. E. Brodley & P. Stone (Eds.), Proceedings of the Twenty-Eighth AAAI Conference on Aritifical Intelligence (pp. 742–748). http://hdl.handle.net/20.500.12708/55786
Proceedings of the Twenty-Eighth AAAI Conference on Aritifical Intelligence
Twenty-Eighth AAAI Conference on Aritifical Intelligence (AAAI 2014)
27-Jul-2014 - 31-Jul-2014
Québec City, Québec, Canada, Non-EU
Number of Pages:
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.