[Back]


Publications in Scientific Journals:

M. Lackner, Z. Fitzsimmons:
"Incomplete Preferences in Single-Peaked Electorates";
Artificial Intelligence, 67 (2020), 797 - 833.



English 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.


"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1613/jair.1.11577


Created from the Publication Database of the Vienna University of Technology.