Incomplete Preferences in Single-Peaked Electorates

07/01/2019
by   Zack Fitzsimmons, et al.
0

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 single-peaked 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset