Weighted electoral control

DOI10.1613/JAIR.4621MaRDI QIDQ5246710zbMATH OpenOpenAlexFDO

Authors Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra

Publication date 22 April 2015

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

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

Mathematics Subject Classification ID

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

Abstract: Although manipulation and bribery have been extensively studied under weighted voting, there has been almost no work done on election control under weighted voting. This is unfortunate, since weighted voting appears in many important natural settings. In this paper, we study the complexity of controlling the outcome of weighted elections through adding and deleting voters. We obtain polynomial-time algorithms, NP-completeness results, and for many NP-complete cases, approximation algorithms. In particular, for scoring rules we completely characterize the complexity of weighted voter control. Our work shows that for quite a few important cases, either polynomial-time exact algorithms or polynomial-time approximation algorithms exist.

Recommendations

• How hard is bribery in elections?
• A note on the complexity of manipulating weighted Schulze voting
• Control and bribery in voting
• Structural control in weighted voting games
• Structural control in weighted voting games

Cited in

(19)

• Optimal defense against election control by deleting voter groups
• A parameterized perspective on protecting elections
• Structural control in weighted voting games
• A note on the complexity of manipulating weighted Schulze voting
• Control complexity in Borda elections: solving all open cases of offline control and some cases of online control
• Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting
• On the computational complexity of variants of combinatorial voter control in elections
• Cloning in elections: finding the possible winners
• Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control
• The complexity of priced control in elections
• Weighted manipulation for four-candidate Llull is easy
• Dichotomy for pure scoring rules under manipulative electoral actions
• Structural control in weighted voting games
• Campaign management under approval-driven voting rules
• Control and bribery in voting
• Election manipulation on social networks: seeding, edge removal, edge addition
• Computational complexity characterization of protecting elections from bribery
• Complexity of control by partitioning veto elections and of control by adding candidates to plurality elections
• Search versus search for collapsing electoral control types

This page was built for publication: Weighted electoral control

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