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.
The paper that inspired our work is Walsh's Uncertainty in Preference Elicitation and Aggregation'' @cite_39 . Among other things, in that paper he raises the issue of manipulation in single-peaked societies. Our paper follows his model of assuming society's linear ordering of the candidates is given and that manipulative voters must be single-peaked with respect to that ordering. However, our theme and his differ. His manipulation results present cases where single-peakedness leaves an @math -completeness shield intact. In particular, for both the constructive and the destructive cases, he shows that the coalition weighted manipulation problem for the single transferable vote election rule for three or more candidates remains @math -hard in the single-peaked case. Although our Theorem follows this path of seeing where shields remain intact for single-peaked preferences, the central focus of our paper is that single-peaked preferences often remove complexity shields on manipulation and control. Walsh's paper for a different issue---looking at incomplete profiles and asking whether some all the completions make a candidate a winner---proves both @math results and @math -completeness results. We're greatly indebted to his paper for raising and exploring the issue of manipulation for single-peaked electorates.
@cite_39
108432896
Uncertainty arises in preference aggregation in several ways. There may, for example, be uncertainty in the votes or the voting rule. Such uncertainty can introduce computational complexity in determining which candidate or candidates can or must win the election. In this paper, we survey recent work in this area and give some new results. We argue, for example, that the set of possible winners can be computationally harder to compute than the necessary winner. As a second example, we show that, even if the unknown votes are assumed to be single-peaked, it remains computationally hard to compute the possible and necessary winners, or to manipulate the election.