Search versus decision for election manipulation problems

DOI10.4230/LIPICS.STACS.2013.377MaRDI QIDQ2957899zbMATH OpenOpenAlexFDO

Authors Edith Hemaspaandra, Lane A. Hemaspaandra, Curtis Menton

Publication date 30 January 2017

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

zbMATH Keywords

application of structural complexity theorysearch vs. decision

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Social choice (91B14)

Abstract: Most theoretical definitions about the complexity of manipulating elections focus on the decision problem of recognizing which instances can be successfully manipulated, rather than the search problem of finding the successful manipulative actions. Since the latter is a far more natural goal for manipulators, that definitional focus may be misguided if these two complexities can differ. Our main result is that they probably do differ: If integer factoring is hard, then for election manipulation, election bribery, and some types of election control, there are election systems for which recognizing which instances can be successfully manipulated is in polynomial time but producing the successful manipulations cannot be done in polynomial time.

Recommendations

• Search versus Decision for Election Manipulation Problems
• How hard is bribery in elections?
• The computational difficulty of manipulating an election
• When are elections with few candidates hard to manipulate?
• Is computational complexity a barrier to manipulation?

Cited in

(16)

• The computational difficulty of manipulating an election
• Complexity of control in judgment aggregation for uniform premise-based quota rules
• Control complexity in Bucklin and fallback voting: a theoretical analysis
• Control complexity in Bucklin and fallback voting: an experimental analysis
• Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey
• Manipulation complexity of same-system runoff elections
• Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control
• The complexity of priced control in elections
• The Power of Self-Reducibility: Selectivity, Information, and Approximation
• The complexity of manipulative attacks in nearly single-peaked electorates
• Pseudo-deterministic proofs
• Search versus Decision for Election Manipulation Problems
• The complexity landscape of outcome determination in judgment aggregation
• Hardness and algorithms for electoral manipulation under media influence
• Complexity of control by partitioning veto elections and of control by adding candidates to plurality elections
• Complexity of manipulation and bribery in judgment aggregation for uniform premise-based quota rules

This page was built for publication: Search versus decision for election manipulation problems

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