research-article

Public Access

Search versus Decision for Election Manipulation Problems

Authors:

Edith Hemaspaandra,

Lane A. Hemaspaandra,

Curtis MentonAuthors Info & Claims

ACM Transactions on Computation Theory (TOCT), Volume 12, Issue 1

Article No.: 3, Pages 1 - 42

https://doi.org/10.1145/3369937

Published: 11 February 2020 Publication History

All formats PDF

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 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.

References

[1]

Dorit Aharonov and Oded Regev. 2005. Lattice problems in NP ∩ coNP. J. ACM 52, 5 (2005), 749--765.

Digital Library

[2]

John J. Bartholdi, III and James B. Orlin. 1991. Single transferable vote resists strategic voting. Soc. Choice Welfare 8, 4 (1991), 341--354.

[3]

John J. Bartholdi, III, Craig A. Tovey, and Michael A. Trick. 1989. The computational difficulty of manipulating an election. Soc. Choice Welfare 6, 3 (1989), 227--241.

[4]

John J. Bartholdi, III, Craig A. Tovey, and Michael A. Trick. 1989. Voting schemes for which it can be difficult to tell who won the election. Soc. Choice Welfare 6, 2 (1989), 157--165.

[5]

John J. Bartholdi, III, Craig A. Tovey, and Michael A. Trick. 1992. How hard is it to control an election? Math. Comput. Model. 16, 8--9 (1992), 27--40.

Digital Library

[6]

Dorothea Baumeister, Gabor Erdélyi, Edith Hemaspaandra, Lane A. Hemaspaandra, and Jörg Rothe. 2010. Computational aspects of approval voting. In Handbook on Approval Voting, Jean-François Laslier and M. Remzi Sanver (Eds.). Springer, 199--251.

[7]

Dorothea Baumeister and Jörg Rothe. 2016. Preference aggregation by voting. In Economics and Computation: An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division, Jörg Rothe (Ed.). Springer, 197--325.

[8]

Mihir Bellare and Shafi Goldwasser. 1994. The complexity of decision versus search. SIAM J. Comput. 23, 1 (1994), 97--119.

Digital Library

[9]

Leonard Berman and Juris Hartmanis. 1977. On isomorphisms and density of NP and other complete sets. SIAM J. Comput. 6, 2 (1977), 305--322.

Digital Library

[10]

Manuel Blum and Russell Impagliazzo. 1987. Generic oracles and oracle classes. In Proceedings of the 28th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, 118--126.

Digital Library

[11]

Allan Borodin and Alan J. Demers. 1976. Some Comments on Functional Self-Reducibility and the NP Hierarchy. Technical Report TR 76-284. Department of Computer Science, Cornell University, Ithaca, NY.

[12]

Samuel R. Buss. 1987. The Boolean formula value problem is in ALOGTIME. In Proceedings of the 19th ACM Symposium on Theory of Computing. ACM Press, 123--131.

Digital Library

[13]

Anne Condon. 1992. The complexity of stochastic games. Inf. Comput. 96, 2 (1992), 203--224.

Digital Library

[14]

Vincent Conitzer, Tuomas Sandholm, and Jérôme Lang. 2007. When are elections with few candidates hard to manipulate? J. ACM 54, 3 (2007), Article 14.

Digital Library

[15]

Cynthia Dwork, Ravi Kumar, Moni Naor, and D. Sivakumar. 2001. Rank aggregation methods for the web. In Proceedings of the 10th International World Wide Web Conference. ACM Press, 613--622.

[16]

Eithan Ephrati and Jeffrey S. Rosenschein. 1997. A heuristic technique for multi-agent planning. Ann. Math. Artif. Intell. 20, 1--4 (1997), 13--67.

Digital Library

[17]

Gábor Erdélyi, Michael R. Fellows, Jörg Rothe, and Lena Schend. 2015. Control complexity in Bucklin and fallback voting: A theoretical analysis. J. Comput. Syst. Sci. 81, 4 (2015), 632--660.

[18]

Gábor Erdélyi, Markus Nowak, and Jörg Rothe. 2009. Sincere-strategy preference-based approval voting fully resists constructive control and broadly resists destructive control. Math. Logic Quart. 55, 4 (2009), 425--443.

[19]

Piotr Faliszewski, Edith Hemaspaandra, and Lane A. Hemaspaandra. 2009. How hard is bribery in elections? J. Artif. Intell. Res. 35 (2009), 485--532.

Digital Library

[20]

Piotr Faliszewski, Edith Hemaspaandra, and Lane A. Hemaspaandra. 2010. Using complexity to protect elections. Commun. ACM 53, 11 (2010), 74--82.

Digital Library

[21]

Piotr Faliszewski, Edith Hemaspaandra, and Lane A. Hemaspaandra. 2011. Multimode control attacks on elections. J. Artif. Intell. Res. 40 (2011), 305--351.

[22]

Piotr Faliszewski, Edith Hemaspaandra, and Lane A. Hemaspaandra. 2014. The complexity of manipulative attacks in nearly single-peaked electorates. Artif. Intell. 207 (2014), 69--99.

[23]

Piotr Faliszewski, Edith Hemaspaandra, and Lane A. Hemaspaandra. 2015. Weighted electoral control. J. Artif. Intell. Res. 52 (2015), 507--542.

[24]

Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra, and Jörg Rothe. 2009. Llull and Copeland voting computationally resist bribery and constructive control. J. Artif. Intell. Res. 35 (2009), 275--341.

Digital Library

[25]

Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra, and Jörg Rothe. 2009. A richer understanding of the complexity of election systems. In Fundamental Problems in Computing: Essays in Honor of Professor Daniel J. Rosenkrantz, Sekharipuram S. Ravi and Sandeep K. Shukla (Eds.). Springer, 375--406.

[26]

Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra, and Jörg Rothe. 2011. The shield that never was: Societies with single-peaked preferences are more open to manipulation and control. Inf. Comput. 209, 2 (2011), 89--107.

Digital Library

[27]

Piotr Faliszewski and Jörg Rothe. 2016. Control and bribery in voting. In Handbook of Computational Social Choice, Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia (Eds.). Cambridge University Press, 146--168.

[28]

Stephen A. Fenner, Lance Fortnow, Ashish V. Naik, and John D. Rogers. 2003. Inverting onto functions. Inf. Comput. 186, 1 (2003), 90--103.

Digital Library

[29]

Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 8 Company.

Digital Library

[30]

Sumit Ghosh, Manisha Mundhe, Karina Hernandez, and Sandip Sen. 1999. Voting for Movies: The anatomy of recommender systems. In Proceedings of the 3rd Annual Conference on Autonomous Agents. ACM Press, 434--435.

Digital Library

[31]

Oded Goldreich and Shafi Goldwasser. 2000. On the limits of nonapproximability of lattice problems. J. Comput. Syst. Sci. 60, 3 (2000), 540--563.

Digital Library

[32]

Juris Hartmanis and Lane A. Hemachandra. 1988. Complexity classes without machines: On complete languages for UP. Theor. Comput. Sci. 58, 1--3 (1988), 129--142.

Digital Library

[33]

Juris Hartmanis and Lane A. Hemachandra. 1990. Robust machines accept easy sets. Theor. Comput. Sci. 74, 2 (1990), 217--226.

Digital Library

[34]

Lane A. Hemachandra. 1987. Counting in Structural Complexity Theory. Ph.D. Dissertation. Cornell University, Ithaca, NY.

[35]

Edith Hemaspaandra, Lane A. Hemaspaandra, and Curtis Menton. 2013. Search versus decision for election manipulation problems. In Proceedings of the 30th Annual Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics, Vol. 20. 377--388.

[36]

Edith Hemaspaandra, Lane A. Hemaspaandra, and Jörg Rothe. 2007. Anyone but him: The complexity of precluding an alternative. Artif. Intell. 171, 5--6 (2007), 255--285.

Digital Library

[37]

Edith Hemaspaandra, Ashish V. Naik, Mitsunori Ogihara, and Alan L. Selman. 1996. P-selective sets and reducing search to decision vs. self-reducibility. J. Comput. Syst. Sci. 53, 2 (1996), 194--209.

Digital Library

[38]

Lane A. Hemaspaandra. 2017. CSC 286/486. Retrieved from http://www.cs.rochester.edu/u/lane/course-notes-csc486-2017.pdf.

[39]

Lane A. Hemaspaandra. 2018. Computational social choice and computational complexity: BFFs? In Proceedings of the 32nd AAAI Conference on Artificial Intelligence. AAAI Press, 7971--7977.

[40]

Lane A. Hemaspaandra, Rahman Lavaee, and Curtis Menton. 2016. Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control. Ann. Math. Artif. Intell. 77, 3--4 (2016), 191--223.

Digital Library

[41]

Lane A. Hemaspaandra and David E. Narváez. 2017. The opacity of backbones. In Proceedings of the 31st AAAI Conference on Artificial Intelligence. AAAI Press, 3900--3906.

[42]

Lane A. Hemaspaandra and David E. Narváez. 2019. Existence versus exploitation: The opacity of backbones and backdoors under a weak assumption. In Proceedings of the 45th International Conference on Current Trends in Theory and Practice of Computer Science. Lecture Notes in Computer Science, Vol. 11376, Springer-Verlag, 247--259.

[43]

Lane A. Hemaspaandra, Jörg Rothe, and Gerd Wechsung. 1997. Easy sets and hard certificate schemes. Acta Inf. 34, 11 (1997), 859--879.

[44]

Lane A. Hemaspaandra and Leen Torenvliet. 2003. Theory of Semi-Feasible Algorithms. Springer-Verlag.

[45]

Lane A. Hemaspaandra and Marius Zimand. 1996. Strong self-reducibility precludes strong immunity. Math. Syst. Theory 29, 5 (1996), 535--548.

[46]

John E. Hopcroft and Jeffrey D. Ullman. 1979. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley.

Digital Library

[47]

Pavel Hubáček, Moni Naor, and Eylon Yogev. 2017. The journey from NP to TFNP hardness. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference. Leibniz International Proceedings in Informatics, Vol. 67, 60:1--60:21.

[48]

Russell Impagliazzo and Moni Naor. 1988. Decision trees and downward closures. In Proceedings of the 3rd Structure in Complexity Theory Conference. IEEE Computer Society Press, 29--38.

[49]

Marcin Jurdzinski. 1998. Deciding the winner in parity games is in UP ∩ co-UP. Inform. Process. Lett. 68, 3 (1998), 119--124.

Digital Library

[50]

Richard M. Karp, Eli Upfal, and Avi Wigderson. 1988. The complexity of parallel search. J. Comput. Syst. Sci. 36, 1 (1988), 225--253.

Digital Library

[51]

Shiva Kintali. 2010. NP intersect coNP. Retrieved from kintali.wordpress.com/2010/06/06/np-intersect-conp.

[52]

Richard E. Ladner, Nancy A. Lynch, and Alan L. Selman. 1975. A comparison of polynomial time reducibilities. Theor. Comput. Sci. 1, 2 (1975), 103--124.

[53]

Cynthia Maushagen and Jörg Rothe. 2018. Complexity of control by partitioning veto elections and of control by adding candidates to plurality elections. Ann. Math. Artif. Intell. 82, 4 (2018), 219--244.

Digital Library

[54]

Nimrod Megiddo and Christos H. Papadimitriou. 1991. On total functions, existence theorems and computational complexity. Theor. Comput. Sci. 81, 2 (1991), 317--324.

Digital Library

[55]

Curtis Menton. 2013. Normalized range voting broadly resists control. Theory Comput. Syst. 53, 4 (2013), 507--531.

Digital Library

[56]

Curtis Menton and Preetjot Singh. 2013. Control complexity of Schulze voting. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence. AAAI Press, 286--292.

[57]

Albert R. Meyer and Mike Paterson. 1979. With What Frequency Are Apparently Intractable Problems Difficult? Technical Report MIT/LCS/TM-126. Laboratory for Computer Science, MIT, Cambridge, MA.

[58]

Marc Neveling and Jörg Rothe. 2017. Solving seven open problems of offline and online control in Borda elections. In Proceedings of the 31st AAAI Conference on Artificial Intelligence. AAAI Press, 3029--3035.

[59]

David C. Parkes and Lirong Xia. 2012. A complexity-of-strategic-behavior comparison between Schulze’s rule and ranked pairs. In Proceedings of the 26th AAAI Conference on Artificial Intelligence. AAAI Press, 1429--1435.

[60]

Jörg Rothe. 1999. Complexity of Certificates, Heuristics, and Counting Types, with Applications to Cryptography and Circuit Theory. Habilitation thesis, Friedrich-Schiller-Universität Jena, Institut für Informatik, Jena, Germany.

[61]

Claus-Peter Schnorr. 1976. Optimal algorithms for self-reducible problems. In Proceedings of the 3rd International Colloquium on Automata, Languages, and Programming. Edinburgh University Press, 322--337.

[62]

Peter W. Shor. 1997. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26, 5 (1997), 1484--1509.

Digital Library

[63]

Gábor Tardos. 1989. Query complexity, or why is it difficult to separate NP^A∩ coNP^A from P^A by random oracles A. Combinatorica 9 (1989), 385--392.

[64]

Leslie G. Valiant. 1976. The relative complexity of checking and evaluating. Inform. Process. Lett. 5, 1 (1976), 20--23.

[65]

John Watrous. 2011. An introduction to quantum information and quantum circuits. SIGACT News 42, 2 (2011), 52--67.

Digital Library

Cited By

Chavrimootoo MAgmon NAn BRicci AYeoh W(2023)Separations and Collapses in Computational Social ChoiceProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3599160(3026-3028)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3599160
Carleton BChavrimootoo MHemaspaandra LNarváez DTaliancich CWelles HAgmon NAn BRicci AYeoh W(2023)Search versus Search for Collapsing Electoral Control TypesProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3599042(2682-2684)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3599042
Carleton BChavrimootoo MHemaspaandra LNarváez DTaliancich CWelles HAgmon NAn BRicci AYeoh W(2023)Separating and Collapsing Electoral Control TypesProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598833(1743-1751)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598833
Show More Cited By

Index Terms

Search versus Decision for Election Manipulation Problems
1. Computing methodologies
  1. Artificial intelligence
    1. Distributed artificial intelligence
      1. Multi-agent systems
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
    2. Problems, reductions and completeness
  2. Theory and algorithms for application domains

Recommendations

High-Multiplicity Election Problems
AAMAS '18: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems

The computational study of elections generally assumes that the preferences of the electorate come in as a list of votes. Depending on the context, it may be much more natural to represent the list succinctly, as the distinct votes of the electorate and ...
THE COMPLEXITY OF DECISION VERSUS SEARCH
High-multiplicity election problems

The computational study of elections generally assumes that the preferences of the electorate come in as a list of votes. Depending on the context, it may be much more natural to represent the list succinctly, as the distinct votes of the electorate and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Computation Theory

ACM Transactions on Computation Theory Volume 12, Issue 1

March 2020

199 pages

ISSN:1942-3454

EISSN:1942-3462

DOI:10.1145/3376904

Editor:
Ryan O'Donnell
Carnegie Mellon University, USA

Issue’s Table of Contents

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 February 2020

Accepted: 01 September 2019

Revised: 01 July 2019

Received: 01 November 2018

Published in TOCT Volume 12, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Alexander von Humboldt-Stiftung
National Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
719
Total Downloads

Downloads (Last 12 months)382
Downloads (Last 6 weeks)73

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chavrimootoo MAgmon NAn BRicci AYeoh W(2023)Separations and Collapses in Computational Social ChoiceProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3599160(3026-3028)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3599160
Carleton BChavrimootoo MHemaspaandra LNarváez DTaliancich CWelles HAgmon NAn BRicci AYeoh W(2023)Search versus Search for Collapsing Electoral Control TypesProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3599042(2682-2684)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3599042
Carleton BChavrimootoo MHemaspaandra LNarváez DTaliancich CWelles HAgmon NAn BRicci AYeoh W(2023)Separating and Collapsing Electoral Control TypesProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598833(1743-1751)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598833
Ma KXu QZeng JLi GCao XHuang Q(2022)A Tale of HodgeRank and Spectral Method: Target Attack Against Rank Aggregation Is the Fixed Point of Adversarial GameIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2022.3190939(1-18)Online publication date: 2022
https://doi.org/10.1109/TPAMI.2022.3190939
Hemaspaandra LNarváez D(2021)The opacity of backbonesInformation and Computation10.1016/j.ic.2021.104772281:COnline publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1016/j.ic.2021.104772
Neveling MRothe J(2021)Control complexity in Borda electionsArtificial Intelligence10.1016/j.artint.2021.103508298:COnline publication date: 1-Sep-2021
https://dl.acm.org/doi/10.1016/j.artint.2021.103508
Hemaspaandra LNarváez D(2021)Existence versus exploitation: the opacity of backdoors and backbonesProgress in Artificial Intelligence10.1007/s13748-021-00234-610:3(297-308)Online publication date: 1-Sep-2021
https://dl.acm.org/doi/10.1007/s13748-021-00234-6
Erdélyi GNeveling MReger CRothe JYang YZorn R(2021)Towards completing the puzzle: complexity of control by replacing, adding, and deleting candidates or votersAutonomous Agents and Multi-Agent Systems10.1007/s10458-021-09523-935:2Online publication date: 29-Jul-2021
https://doi.org/10.1007/s10458-021-09523-9
Fitzsimmons ZHemaspaandra EHemaspaandra L(2020)Control in the presence of manipulators: cooperative and competitive casesAutonomous Agents and Multi-Agent Systems10.1007/s10458-020-09475-634:2Online publication date: 28-Aug-2020
https://doi.org/10.1007/s10458-020-09475-6

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents