Search versus Decision for Election Manipulation Problems
ACM Transactions on Computation Theory · 2020-03-31 · 12 (1) · 1-42
DOI: 10.1145/3369937 ↗At a glance
Journal article in ACM Transactions on Computation Theory, published online on 2020-02-11. Written by Edith Hemaspaandra and 2 co-authors. Cited 11 times so far (Crossref); 63 references. Funded by: Alexander von Humboldt-Stiftung, National Science Foundation.
Abstract (original language)
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 P ≠ NP ∩ coNP (which itself is well known to hold if integer factoring is hard), then for election manipulation, election bribery, and some types of election control, there are election systems for which the problem of recognizing which instances can be successfully manipulated is polynomial-time solvable, yet the task of producing the successful manipulations cannot be done in polynomial time.
Funding
- Alexander von Humboldt-Stiftung
- National Science Foundation
Cite
APA
Hemaspaandra, E., Hemaspaandra, L. A., & Menton, C. (2020). Search versus Decision for Election Manipulation Problems. ACM Transactions on Computation Theory, 12(1), 1-42. https://doi.org/10.1145/3369937
Vancouver
Hemaspaandra E, Hemaspaandra LA, Menton C. Search versus Decision for Election Manipulation Problems. ACM Transactions on Computation Theory. 2020;12(1):1-42. doi:10.1145/3369937
BibTeX
@article{Hemaspaandra2020,
author = {Hemaspaandra, Edith and Hemaspaandra, Lane A. and Menton, Curtis},
title = {Search versus Decision for Election Manipulation Problems},
journal = {ACM Transactions on Computation Theory},
year = {2020},
volume = {12},
number = {1},
pages = {1--42},
doi = {10.1145/3369937}
}
EUVIMED