text: Many electoral bribery, control, and manipulation problems (which we will refer to in general as "manipulative actions" problems) are NP-hard in the general case. It has recently been noted that many of these problems fall into polynomial time if the electorate is single-peaked (i.e., is polarized along some axis issue). However, real-world electorates are not truly single-peaked. There are usually some mavericks, and so real-world electorates tend to merely be nearly single-peaked. This paper studies the complexity of manipulative-action algorithms for elections over nearly single-peaked electorates, for various notions of nearness and various election systems. We provide instances where even one maverick jumps the manipulative-action complexity up to @math -hardness, but we also provide many instances where a reasonable number of mavericks can be tolerated without increasing the manipulative-action complexity.
  @cite_3: Much work has been devoted, during the past 20years, to using complexity to protect elections from manipulation and control. Many ''complexity shield'' results have been obtained-results showing that the attacker's task can be made NP-hard. 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.
  @cite_2: For many election systems, bribery (and related) attacks have been shown NP-hard using constructions on combinatorially rich structures such as partitions and covers. This paper shows that for voters who follow the most central political-science model of electorates-- single-peaked preferences--those hardness protections vanish. By using single-peaked preferences to simplify combinatorial covering challenges, we for the first time show that NP-hard bribery problems--including those for Kemeny and Llull elections--fall to polynomial time for single-peaked electorates. By using single-peaked preferences to simplify combinatorial partition challenges, we for the first time show that NP-hard partition-of-voters problems fall to polynomial time for single-peaked electorates. We show that for single-peaked electorates, the winner problems for Dodgson and Kemeny elections, though Θ2p-complete in the general case, fall to polynomial time. And we completely classify the complexity of weighted coalition manipulation for scoring protocols in single-peaked electorates.
summary: The four papers most related to the present one are the following. insightfully raised the idea that general complexity results may change in single-peaked societies. His manipulative-action example (STV) actually provides a case where single-peakedness fails to lower manipulation complexity, but in a different context he did find a lowering of complexity for single-peakedness. The papers , the first of which was in the TARK conference, then broadly explored the effect of single-peakedness on manipulative actions. These three papers are all in the model of (perfect) single-peakedness. , in the context of preference elicitation, raised and experimentally studied the issue of single-peaked societies. also discussed nearness to single-peakedness, and the papers @cite_3 @cite_2 both raise as open issues whether shield-evaporation (complexity) results for single-peakedness will withstand near-single-peakedness. The present paper seeks to bring the nearly single-peaked'' lens to the study of manipulative actions.