On the computational complexity of variants of combinatorial voter control in elections

DOI10.1007/978-3-319-55911-7_25MaRDI QIDQ2988834zbMATH OpenOpenAlexFDO

Authors Leon Kellerhals, Viatcheslav Korenwein, Philipp Zschoche, Robert Bredereck, Jiehua Chen

Publication date 19 May 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.05108

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Voting theory (91B12)

Abstract: Voter control problems model situations in which an external agent tries toaffect the result of an election by adding or deleting the fewest number of voters. The goal of the agent is to make a specific candidate either win (emph{constructive} control) or lose (emph{destructive} control) the election. We study the constructive and destructive voter control problems whenadding and deleting voters have a emph{combinatorial flavor}: If we add (resp. delete) a voter~$v$, we also add (resp. delete) a bundle~$kappa(v)$ of voters that are associated with~$v$. While the bundle~$kappa(v)$ may have more than one voter, a voter may also be associated with more than one voter. We analyze the computational complexity of the four voter control problems for the Plurality rule. We obtain that, in general, making a candidate lose is computationally easier than making her win. In particular, if the bundling relation is symmetric (i.e. $forallwcolonwinkappa(v)Leftrightarrowvinkappa(w)$), and if each voter has at most two voters associated with him, then destructive control is polynomial-time solvable while the constructive variant remains $NP$-hard. Even if the bundles are disjoint (i.e. $forallwcolonwinkappa(v)Leftrightarrowkappa(v)=kappa(w)$), the constructive problem variants remain intractable. Finally, the minimization variant of constructive control by adding voters does not admit an efficient approximation algorithm, unless P=NP.

Recommendations

• Combinatorial voter control in elections
• Combinatorial voter control in elections
• Parameterized computational complexity of control problems in voting systems
• Elections with few voters: candidate control can be easy
• Complexity of control by partitioning veto and maximin elections and of control by adding candidates to plurality elections

Cites work

• An algorithmic proof of Tutte's f-factor theorem
• Anyone but him: the complexity of precluding an alternative
• Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey
• Combinatorial voter control in elections
• Control complexity in Bucklin and fallback voting: a theoretical analysis
• Elections with few voters: candidate control can be easy
• Fundamentals of parameterized complexity
• Graph structure and monadic second-order logic. A language-theoretic approach
• How hard is it to control an election?
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Large-scale election campaigns: combinatorial shift bribery
• Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
• Minimum vertex weighted deficiency of (g,f)-factors: A greedy algorithm
• Multimode control attacks on elections
• On the computational complexity of variants of combinatorial voter control in elections
• Parameterized complexity of candidate control in elections and related digraph problems
• Parameterized complexity of control problems in Maximin election
• Parameterized computational complexity of control problems in voting systems
• Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control
• Studies in Computational Aspects of Voting
• Weighted electoral control

Cited in

(15)

• Parameterized computational complexity of control problems in voting systems
• A parameterized perspective on protecting elections
• Exploiting social influence to control elections based on positional scoring rules
• Control complexity in Bucklin and fallback voting: a theoretical analysis
• Combinatorial voter control in elections
• Combinatorial voter control in elections
• On the computational complexity of variants of combinatorial voter control in elections
• The complexity of priced control in elections
• Online voter control in sequential elections
• Parameterized Computational Complexity of Dodgson and Young Elections
• scientific article; zbMATH DE number 6928629 (Why is no real title available?)
• Elections with few voters: candidate control can be easy
• The Last Voting Rule Is Home: Complexity of Control by Partition of Candidates or Voters in Maximin Elections
• On the complexity of winner determination and strategic control in conditional approval voting
• Binary linear programming solutions and non-approximability for control problems in voting systems

This page was built for publication: On the computational complexity of variants of combinatorial voter control in elections

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2988834)