Much work has been devoted, during the past twenty years, to using complexity to protect elections from manipulation and control. Many results have been obtained showing NP-hardness shields, and recently there has been much focus on whether such worst-case hardness protections can be bypassed by frequently correct heuristics or by approximations. This paper takes a very different approach: We argue that when electorates follow the canonical political science model of societ al preferences the complexity shield never existed in the first place. In particular, we show that for electorates having single-peaked preferences, many existing NP-hardness results on manipulation and control evaporate.
As mentioned in the main text, Bartholdi and Trick @cite_27 , Doignon and Falmagne @cite_37 , and Escoffier, Lang, and "O zt "u rk @cite_1 have provided efficient algorithms for testing single-peakedness and producing a valid candidate linear ordering, for the case when votes are linear orders.
@cite_27 @cite_1 @cite_37
2042544885 2004142419
We study a special case of the Stable Roommates problem in which preferences are derived from a psychological model common in social choice literature. When preferences are 'single-peaked' and 'narcissistic', there exists a unique stable matching, and it can be constructed in O(n) time. We also show how to recognize quickly, when a set of preferences is single-peaked. Abstract Two conditions on a collection of simple orders - unimodality and straightness - are necessary but not jointly sufficient for unidimensional unfolding representations. From the analysis of these conditions, a polynomial time algorithm is derived for the testing of unidimensionality and for the construction of a representation when one exists.