How Hard is Control in Multi-Peaked Elections: A Parameterized Study

We study the complexity of voting control problems in multi-peaked elections. In particular, we focus on the constructive/destructive control by adding/deleting votes under Condorcet, Maximin and Copelandα voting systems. We show that the NP of these problems (except for the destructive control by adding/deleting votes under Condorcet, which is polynomial-time solvable in the general case) hold even in κ-peaked elections with κ being a very small constant. Furthermore, from the parameterized complexity point of view, our reductions actually show that these problems are in κ-peaked elections with κ-3,4, with respect to the number of added/deleted votes.

• Publication year

  2015

• Venue

  Adaptive Agents and Multi-Agent Systems

• Publication date

  2015-05-04

• Fields of study

  Mathematics, Computer Science, Political Science

• Identifiers
  DOI 10.5555/2772879.2773407
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Manipulation with Bounded Single-Peaked Width: A Parameterized Study

  2015cited by this paper
• Controlling elections with bounded single-peaked width

  2014cited by this paper
• The control complexity of r-Approval: From the single-peaked case to the general case

  2014cited by this paper
• Parameterized complexity of control by voter selection in Maximin, Copeland, Borda, Bucklin, and Approval election systems

  2013cited by this paper
• The complexity of manipulative attacks in nearly single-peaked electorates

  2011cited by this paper
• Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates

  2010cited by this paper
• Parameterized complexity of control problems in Maximin election

  2010cited by this paper
• Parameterized computational complexity of control problems in voting systems

  2009cited by this paper
• The shield that never was: societies with single-peaked preferences are more open to manipulation and control

  2009cited by this paper
• How hard is it to control an election? Math

  1992cited by this paper

• Collecting, Classifying, Analyzing, and Using Real-World Ranking Data

  2023cites this paper
• Broadening the Complexity-theoretic Analysis of Manipulative Attacks in Group Identification

  2022cites this paper
• Collecting, Classifying, Analyzing, and Using Real-World Elections

  2022cites this paper
• Manipulative Attacks and Group Identification

  2022cites this paper
• On the complexity of bribery with distance restrictions

  2019cites this paper
• Complexity of strategic influences in elections and group identification with a main focus on incomplete information

  2019cites this paper
• Complexity of Controlling Nearly Single-Peaked Elections Revisited

  2018cites this paper
• On Recognising Nearly Single-Crossing Preferences

  2018cites this paper
• Optimal defense against election control by deleting voter groups

  2018cites this paper
• Parameterized Complexity of Voter Control in Multi-Peaked Elections

  2018cites this paper
• Facility location with double-peaked preferences

  2017cites this paper
• Structured Preferences

  2017cites this paper
• On the Complexity of Borda Control in Single-Peaked Elections

  2017cites this paper
• How hard is it to control a group?

  2016cites this paper
• Facility location with double-peaked preferences

  2015influential citation
• A deep exploration of the complexity border of strategic voting problems

  2015cites this paper
• Manipulation with Bounded Single-Peaked Width: A Parameterized Study

  2015cites this paper