2026-08-11T00:28:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3949 2024-03-06T10:34:41Z ddc:004 open_access

Search versus Decision for Election Manipulation Problems Hemaspaandra, Edith Hemaspaandra, Lane A. Menton, Curtis Search vs. decision application of structural complexity theory 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Edith Hemaspaandra and Lane A. Hemaspaandra and Curtis Menton 2013 Is Part Of LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2013.377 urn:nbn:de:0030-drops-39498 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.377 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode