Incomplete Preferences in Single-Peaked Electorates
arXiv:1907.00752 · doi:10.1613/jair.1.11577
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 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.
arXiv commentThis work is based on a conference paper by Martin Lackner (AAAI 2014) and a follow-up conference paper by Zack Fitzsimmons (TARK 2015)
References in corpus (4)
- Towards a Dichotomy for the Possible Winner Problem in Elections Based on Scoring Rules
- Single-Peaked Consistency for Weak Orders Is Easy
- The one-dimensional Euclidean domain: Finitely many obstructions are not enough
- On the Number of Single-Peaked Narcissistic or Single-Crossing Narcissistic Preference Profiles