Computational Aspects of Nearly Single-Peaked Electorates

Abstract

Manipulation, bribery, and control are well-studied ways of changing the outcome of an election. Many voting rules are, in the general case, computationally resistant to some of these manipulative actions. However when restricted to single-peaked electorates, these rules suddenly become easy to manipulate. Recently, Faliszewski, Hemaspaandra, and Hemaspaandra studied the computational complexity of strategic behavior in nearly single-peaked electorates. These are electorates that are not single-peaked but close to it according to some distance measure.





In this paper we introduce several new distance measures regarding single-peakedness. We prove that determining whether a given profile is nearly single-peaked is NP-complete in many cases. For one case we present a polynomial-time algorithm. In case the single-peaked axis is given, we show that determining the distance is always possible in polynomial time. Furthermore, we explore the relations between the new notions introduced in this paper and existing notions from the literature.