Bribery in elections with randomly selected voters: hardness and algorithm

DOI10.1016/J.TCS.2025.115150MaRDI QIDQ7006266zbMATH OpenFDO

Authors Liangde Tao, Lin Chen, Lei Xu, Weidong (Larry) Shi, Md Mahabub Uz Zaman, Ahmed Sunny

Publication date 31 March 2025

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

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115150

zbMATH Keywords

approximation algorithmscomputational social choicepolynomial-time approximation scheme

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Integer programming (90C10) Social choice (91B14)

Cites work

• \(n\)-fold integer programming in cubic time
• Combinatorial \(n\)-fold integer programming and applications
• Complexity of manipulation with partial information in voting
• Determining possible and necessary winners given partial orders
• Elections with few voters: candidate control can be easy
• Faster Algorithms for Integer Programs with Block Structure
• Fixing balanced knockout and double elimination tournaments
• Handbook of computational social choice
• How hard is bribery in elections?
• scientific article; zbMATH DE number 7788439 (Why is no real title available?)
• Near-linear time algorithm for n-fold ILPs via color coding
• NP-hardness of two edge cover generalizations with applications to control and bribery for approval voting
• On the complexity of bribery and manipulation in tournaments with uncertain information
• On the evaluation of election outcomes under uncertainty
• Optimizing positional scoring rules for rank aggregation
• Smart Contract Execution - the (+-)-Biased Ballot Problem.
• Swap bribery
• Taking the final step to a full dichotomy of the possible winner problem in pure scoring rules
• The complexity of probabilistic lobbying
• Towards a dichotomy for the possible winner problem in elections based on scoring rules

This page was built for publication: Bribery in elections with randomly selected voters: hardness and algorithm

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