Manipulation with Bounded Single-Peaked Width: A Parameterized Study

We study the manipulation problem in elections with bounded singlepeaked width from the parameterized complexity point of view. In particular, we focus on the Borda, Copeland α and Maximin voting correspondences. For Borda, we prove that the unweighted manipulation problem with two manipulators is fixed-parameter tractable with respect to single-peaked width. For Maximin and Copeland α for every 0 ≤ α ≤ 1, we prove that the unweighted manipulation problem is fixed-parameter tractable with respect to the combined parameter (k, t), where k denotes the single-peaked width and t denotes the number of manipulators. In addition, we study the weighted manipulation problem for Maximin and Copeland α for every 0 ≤ α ≤ 1 in single-peaked elections and achieve several polynomial-time solvability results.