Computational complexity characterization of protecting elections from bribery

DOI10.1016/J.TCS.2021.08.036MaRDI QIDQ5919119zbMATH OpenOpenAlexWikidataFDO

Authors Lin Chen, Ahmed Sunny, Shouhuai Xu, Yang Lu, Weidong (Larry) Shi, Nolan Shah, Zhi Min Gao, Lei Xu

Publication date 21 October 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

\( \Sigma_2^p\)-hardnesscomplexityNP-hardnessvoting

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• How hard is bribery in elections?
• Control and bribery in voting
• The complexity of online bribery in sequential elections
• How hard is bribery with distance restrictions?
• Multivariate complexity analysis of swap bribery

Cites work

• A study on the computational complexity of the bilevel knapsack problem
• Approximation algorithms for a bi-level knapsack problem
• Complete sets and the polynomial-time hierarchy
• Control and bribery in voting
• Copeland Voting Fully Resists Constructive Control
• Dichotomy for voting systems
• Elections with few voters: candidate control can be easy
• Frugal bribery in voting
• How hard is bribery in elections?
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Improved approximation algorithms for a bilevel knapsack problem
• Large-scale election campaigns: combinatorial shift bribery
• Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• NP-hardness of two edge cover generalizations with applications to control and bribery for approval voting
• Optimal defense against election control by deleting voter groups
• Prices matter for the parameterized complexity of shift bribery
• Swap bribery
• The complexity of computing the covering radius of a code
• Two-group knapsack game
• Weighted electoral control

Cited in

(10)

• Multivariate complexity analysis of Swap Bribery
• The computational difficulty of manipulating an election
• A parameterized perspective on protecting elections
• The complexity of online bribery in sequential elections
• Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
• scientific article; zbMATH DE number 1024093 (Why is no real title available?)
• scientific article; zbMATH DE number 7450032 (Why is no real title available?)
• A Parameterized Perspective on Attacking and Defending Elections
• Computational complexity characterization of protecting elections from bribery
• Hardness and algorithms for electoral manipulation under media influence

This page was built for publication: Computational complexity characterization of protecting elections from bribery

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