Elections with few voters: candidate control can be easy

DOI10.1613/JAIR.5515;zbMATH Open1426.91092arXiv1411.7812MaRDI QIDQ4600728FDOQ4600728

Authors: Jiehua Chen, Piotr Faliszewski, Rolf Niedermeier, Nimrod Talmon 

Publication date: 12 January 2018

Published in: Journal of Artificial Intelligence Research (Search for Journal in Brave)

Abstract: We study the computational complexity of candidate control in elections with few voters, that is, we consider the parameterized complexity of candidate control in elections with respect to the number of voters as a parameter. We consider both the standard scenario of adding and deleting candidates, where one asks whether a given candidate can become a winner (or, in the destructive case, can be precluded from winning) by adding or deleting few candidates, as well as a combinatorial scenario where adding/deleting a candidate automatically means adding or deleting a whole group of candidates. Considering several fundamental voting rules, our results show that the parameterized complexity of candidate control, with the number of voters as the parameter, is much more varied than in the setting with many voters.

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

Recommendations

• Parameterized complexity of control problems in Maximin election
• Parameterized Complexity of Candidate Control in Elections and Related Digraph Problems
• Parameterized computational complexity of control problems in voting systems
• Parameterized complexity of control by voter selection in Maximin, Copeland, Borda, Bucklin, and Approval election systems
• On the computational complexity of variants of combinatorial voter control in elections

zbMATH Keywords

computational complexityelectionsvoting rulescandidate control

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Voting theory (91B12)

Cited In (19)

• Parameterized complexity of control by voter selection in Maximin, Copeland, Borda, Bucklin, and Approval election systems
• Complexity of control by partitioning veto elections and of control by adding candidates to plurality elections
• \(k\)-majority digraphs and the hardness of voting with a constant number of voters
• Tennis manipulation: can we help Serena Williams win another tournament? Or can we control a knockout tournament with reasonable complexity?
• Computational complexity characterization of protecting elections from bribery
• Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers
• Resolute control: forbidding candidates from winning an election is hard
• Title not available (Why is that?)
• On the computational complexity of variants of combinatorial voter control in elections
• The complexity of priced control in elections
• Parameterized Complexity of Candidate Control in Elections and Related Digraph Problems
• Parameterized complexity of control problems in Maximin election
• A parameterized perspective on protecting elections
• Complexity of control by partitioning veto and maximin elections and of control by adding candidates to plurality elections
• Parameterized computational complexity of control problems in voting systems
• Combinatorial voter control in elections
• Combinatorial voter control in elections
• The Complexity of Controlling Condorcet, Fallback, and k-Veto Elections by Replacing Candidates or Voters
• The complexity of controlling candidate-sequential elections

This page was built for publication: Elections with few voters: candidate control can be easy

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