DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2013.377

Search versus Decision for Election Manipulation Problems

Authors: Edith Hemaspaandra, Lane A. Hemaspaandra, and Curtis Menton

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

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.

Cite as

Edith Hemaspaandra, Lane A. Hemaspaandra, and Curtis Menton. Search versus Decision for Election Manipulation Problems. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 377-388, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{hemaspaandra_et_al:LIPIcs.STACS.2013.377,
  author =	{Hemaspaandra, Edith and Hemaspaandra, Lane A. and Menton, Curtis},
  title =	{{Search versus Decision for Election Manipulation Problems}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{377--388},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.377},
  URN =		{urn:nbn:de:0030-drops-39498},
  doi =		{10.4230/LIPIcs.STACS.2013.377},
  annote =	{Keywords: Search vs. decision, application of structural complexity theory}
}

Search Results

Documents authored by Menton, Curtis

Search versus Decision for Election Manipulation Problems

Abstract

Cite as

Thanks for your feedback!

Could not send message