Abstract
Schulze and ranked-pairs elections have received much attention recently, and the former has quickly become a quite widely used election system. For many cases these systems have been proven resistant to bribery, control, or manipulation, with ranked pairs being particularly praised for being NP-hard for all three of those. Nonetheless, the present paper shows that with respect to the number of candidates, Schulze and ranked-pairs elections are fixed-parameter tractable to bribe, control, and manipulate: we obtain uniform, polynomial-time algorithms whose running times’ degrees do not depend on the number of candidates. We also provide such algorithms for some weighted variants of these problems.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Bartholdi III, J., Tovey, C., Trick, M.: The computational difficulty of manipulating an election. Soc. Choice Welf. 6(3), 227–241 (1989)
Bartholdi III, J., Tovey, C., Trick, M.: How hard is it to control an election? Math. Comput. Model. 16(8/9), 27–40 (1992)
Betzler, N.: A multivariate complexity analysis of voting problems. Ph.D. thesis, Friedrich-Schiller-Universität Jena, Jena, Germany (2010)
Betzler, N., Bredereck, R., Chen, J., Niedermeier, R.: Studies in computational aspects of voting—A parameterized complexity perspective. In: The Multivariate Algorithmic Revolution and Beyond, 318–363. Springer-Verlag Lecture Notes in Computer Science #7370 (2012)
Betzler, N., Uhlmann, J.: Parameterized complexity of candidate control in elections and related digraph problems. Theor. Comput. Sci. 410(52), 43–53 (2009)
Brill, M., Fischer, F.: The price of neutrality for the ranked pairs method. In: Proceedings of the 26th AAAI Conference on Artificial Intelligence, pp. 1299–1305. AAAI Press (2012)
Conitzer, V., Sandholm, T., Lang, J.: When are elections with few candidates hard to manipulate? J. ACM 54(3) (2007). Article 14
Dorn, B., Schlotter, I.: Multivariate complexity analysis of swap bribery. Algorithmica 64(1), 126–151 (2012)
Downey, R., Fellows, M.: Parameterized Complexity. Springer-Verlag (1999)
Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L.: How hard is bribery in elections? J. Artif. Intell. Res. 35, 485–532 (2009)
Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L.: Multimode control attacks on elections. J. Artif. Intell. Res. 40, 305–351 (2011)
Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L.: Weighted electoral control. In: Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems, 367–374. International Foundation for Autonomous Agents and Multiagent Systems (2013)
Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L.: The complexity of manipulative attacks in nearly single-peaked electorates. Artif. Intell. 207, 69–99 (2014)
Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L., Rothe, J.: Llull and Copeland voting computationally resist bribery and constructive control. J. Artif. Intell. Res. 35, 275–341 (2009)
Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer-Verlag (2006)
Gaspers, S., Kalinowski, T., Narodytska, N., Walsh, T.: Coalitional manipulation for Schulze’s rule. In: Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems, 431–438. International Foundation for Autonomous Agents and Multiagent Systems (2013)
Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. SIGACT News 38(1), 31–45 (2007)
Hemaspaandra, E., Hemaspaandra, L., Menton, C.: Search versus decision for election manipulation problems. In: Proceedings of the 30th Annual Symposium on Theoretical Aspects of Computer Science, 377–388. Leibniz International Proceedings in Informatics (LIPIcs) (2013)
Hemaspaandra, E., Hemaspaandra, L., Rothe, J.: Anyone but him: The complexity of precluding an alternative. Artif. Intell. 171(5–6), 255–285 (2007)
Hemaspaandra, L., Lavaee, R., Menton, C.: Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control. Tech. Rep. arXiv: http://arxiv.org/abs/1301.6118 [cs.GT], Computing Res. Rep., http://arxiv.org/corr/ Revised June 2014 (2012)
Hemaspaandra, L., Lavaee, R., Menton, C.: Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control. In: Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems, 1345–1346. International Foundation for Autonomous Agents and Multiagent Systems (2013)
Cai, L., Chen, J., Downey, R., Fellows, M.: Advice classes of parameterized tractability. Annals of Pure and Applied Logic 84(1), 119–138 (1997)
Lenstra Jr., H.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538–548 (1983)
Lin, A.: Solving hard problems in election systems. Ph.D. thesis, Rochester Institute of Technology, Rochester, NY (2012)
Liu, H., Zhu, D.: Parameterized complexity of control problems in maximin election. Inf. Process. Lett. 110(10), 383–388 (2010)
McGarvey, D.: A theorem on the construction of voting paradoxes. Econometrica 21(4), 608–610 (1953)
Menton, C., Singh, P.: Manipulation and control complexity of Schulze voting. Tech. Rep. arXiv: http://arxiv.org/abs/1206.2111v1 (version 1) [cs.GT], Computing Research Repository, http://arxiv.org/corr/ (2012)
Menton, C., Singh, P.: Control complexity of Schulze voting. In: Proceedings of the 23rd International Joint Conference on Artificial Intelligence, 286–292. AAAI Press (2013)
Menton, C., Singh, P.: Manipulation and control complexity of Schulze voting. Tech. Rep. arXiv: http://arxiv.org/abs/1206.2111 (version 4) [cs.GT], Computing Research Repository, http://arxiv.org/corr/ (2013)
Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, London (2006)
Parkes, D., Xia, L.: A complexity-of-strategic-behavior comparison between Schulze’s rule and ranked pairs. In: Proceedings of the 26th AAAI Conference on Artificial Intelligence, 1429–1435. AAAI Press (2012)
Rothe, J., Schend, L.: Challenges to complexity shields that are supposed to protect elections against manipulation and control: A survey. Ann. Math. Artif. Intell. 68(1–3), 161–193 (2013)
Russell, N.: Complexity of control of Borda count elections. Master’s thesis, Rochester Institute of Technology (2007)
Schulze, M.: A new monotonic, clone-independent, reversal symmetric, and Condorcet-consistent single-winner election method. Soc. Choice Welf. 36, 267–303 (2011)
Tideman, T.: Collective Decisions and Voting: The Potential for Public Choice. Ashgate Publishing (2006)
Wikipedia: Schulze method en.wikipedia.org/wiki/Schulze_method (2013)
Xia, L.: Computing the margin of victory for various voting rules. In: Proceedings of the 13th ACM Conference on Electronic Commerce, 982–999 (2012)
Xia, L., Zuckerman, M., Procaccia, A., Conitzer, V., Rosenschein, J.: Complexity of unweighted manipulation under some common voting rules. In: Proceedings of the 21st International Joint Conference on Artificial Intelligence, 348–353 (2009)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Hemaspaandra, L.A., Lavaee, R. & Menton, C. Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control. Ann Math Artif Intell 77, 191–223 (2016). https://doi.org/10.1007/s10472-015-9479-1
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10472-015-9479-1