Abstract
In the context of voting, manipulation and control refer to attempts to influence the outcome of elections by either setting some of the votes strategically (i.e., by reporting untruthful preferences) or by altering the structure of elections via adding, deleting, or partitioning either candidates or voters. Since by the celebrated Gibbard–Satterthwaite theorem (and other results expanding its scope) all reasonable voting systems are manipulable in principle and since many voting systems are in principle susceptible to many control types modeling natural control scenarios, much work has been done to use computational complexity as a shield to protect elections against manipulation and control. However, most of this work has merely yielded NP-hardness results, showing that certain voting systems resist certain types of manipulation or control only in the worst case. Various approaches, including studies of the typical case (where votes are given according to some natural distribution), pose serious challenges to such worst-case complexity results and might allow successful manipulation or control attempts, despite the NP-hardness of the corresponding problems. We survey and discuss some recent results on these challenges to complexity results for manipulation and control, including typical-case analyses and experiments, fixed-parameter tractability, domain restrictions (single-peakedness), and approximability.
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
Baldwin, J.: The technique of the Nanson preferential majority system of election. Proc. R. Soc. Vic. 39, 42–52 (1926)
Ballester, M., Haeringer, G.: A characterization of the single-peaked domain. Soc. Choice Welf. 36(2), 305–322 (2011)
Bartholdi III, J., Orlin, J.: Single transferable vote resists strategic voting. Soc. Choice Welf. 8(4), 341–354 (1991)
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.: Voting schemes for which it can be difficult to tell who won the election. Soc. Choice Welf. 6(2), 157–165 (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)
Baumeister, D., Erdélyi, G., Hemaspaandra, E., Hemaspaandra, L., Rothe, J.: Computational aspects of approval voting. In: Laslier, J., Sanver, R. (eds.) Handbook on Approval Voting, chap. 10, pp. 199–251. Springer (2010)
Berg, S.: Paradox of voting under an urn model: the effect of homogeneity. Public Choice 47(2), 377–387 (1985)
Betzler, N.: On problem kernels for possible winner determination under the k-approval protocol. In: Proceedings of the 35th International Symposium on Mathematical Foundations of Computer Science, pp. 114–125. Lecture Notes in Computer Science #6281. Springer-Verlag (2010)
Betzler, N., Bredereck, R., Chen, J., Niedermeier, R.: Studies in computational aspects of voting—a parameterized complexity perspective. In: Bodlaender et al. H. (ed.) Fellows Festschrift, pp. 318–363. Lecture Notes in Computer Science #7370. Springer-Verlag (2012)
Betzler, N., Guo, J., Niedermeier, R.: Parameterized computational complexity of Dodgson and Young elections. In: Proceedings of the 11th Scandinavian Workshop on Algorithm Theory, pp. 402–413. Lecture Notes in Computer Science #5124. Springer-Verlag (2008)
Betzler, N., Hemmann, S., Niedermeier, R.: A multivariate complexity analysis of determining possible winners given incomplete votes. In: Proceedings of the 21st International Joint Conference on Artificial Intelligence, pp. 53–58. IJCAI (2009)
Betzler, N., Niedermeier, R., Woeginger, G.: Unweighted coalitional manipulation under the Borda rule is NP-hard. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence, pp. 55–60. IJCAI (2011)
Betzler, N., Uhlmann, J.: Parameterized complexity of candidate control in elections and related digraph problems. In: Proceedings of the 2nd Annual International Conference on Combinatorial Optimization and Applications, pp. 43–53. Lecture Notes in Computer Science #5165. Springer-Verlag (2008)
Black, D.: On the rationale of group decision-making. J. Polit. Econ. 56(1), 23–34 (1948)
Brams, S., Fishburn, P.: Approval voting. Am. Polit. Sci. Rev. 72(3), 831–847 (1978)
Brams, S., Sanver, R.: Voting systems that combine approval and preference. In: Brams, S., Gehrlein, W., Roberts, F. (eds.) The Mathematics of Preference, Choice, and Order: Essays in Honor of Peter C. Fishburn, pp. 215–237. Springer (2009)
Brandt, F., Brill, M., Hemaspaandra, E., Hemaspaandra, L.: Bypassing combinatorial protections: polynomial-time algorithms for single-peaked electorates. In: Proceedings of the 24th AAAI Conference on Artificial Intelligence, pp. 715–722. AAAI Press (2010)
Brelsford, E., Faliszewski, P., Hemaspaandra, E., Schnoor, H., Schnoor, I.: Approximability of manipulating elections. In: Proceedings of the 23rd AAAI Conference on Artificial Intelligence, pp. 44–49 (2008)
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)
Coleman, T., Teague, V.: On the complexity of manipulating elections. In: Proceedings of Computing: the 13th Australasian Theory Symposium, vol. 65, pp. 25–33 (2007)
Condorcet, J.: Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix (1785). Facsimile reprint of original published in Paris, 1972, by the Imprimerie Royale. English translation appears in I. McLean and A. Urken, Classics of Social Choice, pp. 91–112. University of Michigan Press (1995)
Conitzer, V.: Eliciting single-peaked preferences using comparison queries. J. Artif. Intell. Res. 35, 161–191 (2009)
Conitzer, V.: Making decisions based on the preferences of multiple agents. Commun. ACM 53(3), 84–94 (2010)
Conitzer, V., Rognlie, M., Xia, L.: Preference functions that score rankings and maximum likelihood estimation. In: Proceedings of the 21st International Joint Conference on Artificial Intelligence, pp. 109–115. IJCAI (2009)
Conitzer, V., Sandholm, T.: Universal voting protocol tweaks to make manipulation hard. In: Proceedings of the 18th International Joint Conference on Artificial Intelligence, pp. 781–788. Morgan Kaufmann (2003)
Conitzer, V., Sandholm, T.: Nonexistence of voting rules that are usually hard to manipulate. In: Proceedings of the 21st National Conference on Artificial Intelligence, pp. 627–634. AAAI Press (2006)
Conitzer, V., Sandholm, T., Lang, J.: When are elections with few candidates hard to manipulate? J. ACM 54(3), 14 (2007)
Copeland, A.: A “reasonable” social welfare function. Mimeographed Notes from a Seminar on Applications of Mathematics to the Social Sciences. University of Michigan (1951)
Davies, J., Katsirelos, G., Narodytska, N., Walsh, T.: Complexity of and algorithms for Borda manipulation. In: Proceedings of the 25th AAAI Conference on Artificial Intelligence, pp. 657–662. AAAI Press (2011)
Dobra, J.: An approach to empirical studies of voting paradoxes: an update and extension. Public Choice 41(2), 241–250 (1983)
Dobzinski, S., Procaccia, A.: Frequent manipulability of elections: the case of two voters. In: Proceedings of the 4th International Workshop on Internet and Network Economics, pp. 653–664 (2008)
Dorn, B., Schlotter, I.: Multivariate complexity analysis of swap bribery. In: Proceedings of the 5th International Symposium on Parameterized and Exact Computation, pp. 107–122. Lecture Notes in Computer Science #6478. Springer-Verlag (2010)
Downey, R., Fellows, M.: Parameterized Complexity. Springer-Verlag (1999)
Duggan, J., Schwartz, T.: Strategic manipulability without resoluteness or shared beliefs: Gibbard–Satterthwaite generalized. Soc. Choice Welf. 17(1), 85–93 (2000)
Dyer, J., Miles Jr., R.: An actual application of collective choice theory to the selection of trajectories for the mariner Jupiter/Saturn 1977 project. Oper. Res. 24(2), 220–244 (1976)
Elkind, E., Faliszewski, P., Slinko, A.: Swap bribery. In: Proceedings of the 2nd International Symposium on Algorithmic Game Theory, pp. 299–310. Lecture Notes in Computer Science #5814. Springer-Verlag (2009)
Elkind, E., Lipmaa, H.: Hybrid voting protocols and hardness of manipulation. In: Proceedings of the 16th International Symposium on Algorithms and Computation, pp. 206–215. Lecture Notes in Computer Science #3827. Springer-Verlag (2005)
Erdélyi, G., Fellows, M.: Parameterized control complexity in Bucklin voting and in fallback voting. In: Conitzer, V., Rothe, J. (eds.) Proceedings of the 3rd International Workshop on Computational Social Choice, pp. 163–174. Universität Düsseldorf (2010)
Erdélyi, G., Fellows, M., Rothe, J., Schend, L.: Control complexity in Bucklin and fallback voting. Computing Research Repository (2012). Tech. Rep. arXiv:1103.2230 [cs.CC]. March, 2011. Revised August 21, 2012
Erdélyi, G., Hemaspaandra, L., Rothe, J., Spakowski, H.: Frequency of correctness versus average-case polynomial time and generalized juntas. Tech. Rep. TR-934, Department of Computer Science, University of Rochester, Rochester, NY (2008)
Erdélyi, G., Hemaspaandra, L., Rothe, J., Spakowski, H.: Frequency of correctness versus average polynomial time. Inf. Process. Lett. 109(16), 946–949 (2009)
Erdélyi, G., Hemaspaandra, L., Rothe, J., Spakowski, H.: Generalized juntas and NP-hard sets. Theor. Comput. Sci. 410(38–40), 3995–4000 (2009)
Erdélyi, G., Nowak, M., Rothe, J.: Sincere-strategy preference-based approval voting fully resists constructive control and broadly resists destructive control. Math. Log. Q. 55(4), 425–443 (2009)
Erdélyi, G., Piras, L., Rothe, J.: The complexity of voter partition in Bucklin and fallback voting: solving three open problems. In: Proceedings of the 10th International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 837–844. IFAAMAS (2011)
Erdélyi, G., Rothe, J.: Control complexity in fallback voting. In: Proceedings of Computing: the 16th Australasian Theory Symposium, vol. 32, no. 8, pp. 39–48. Conferences in Research and Practice in Information Technology Series. Australian Computer Society (2010)
Escoffier, B., Lang, J., Öztürk, M.: Single-peaked consistency and its complexity. In: Proceedings of the 18th European Conference on Artificial Intelligence, pp. 366–370. IOS Press (2008)
Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L.: Using complexity to protect elections. Commun. ACM 53(11), 74–82 (2010)
Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L.: The complexity of manipulative attacks in nearly single-peaked electorates. In: Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge, pp. 228–237. ACM Press (2011)
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., Rothe, J.: Llull and Copeland voting computationally resist bribery and constructive control. J. Artif. Intell. Res. 35, 275–341 (2009)
Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L., Rothe, J.: A richer understanding of the complexity of election systems. In: Ravi, S., Shukla, S. (eds.) Fundamental Problems in Computing: Essays in Honor of Professor Daniel J. Rosenkrantz, chap. 14, pp. 375–406. Springer (2009)
Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L., Rothe, J.: The shield that never was: Societies with single-peaked preferences are more open to manipulation and control. Inf. Comput. 209(2), 89–107 (2011)
Faliszewski, P., Hemaspaandra, E., Schnoor, H.: Copeland voting: ties matter. In: Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 983–990. IFAAMAS (2008)
Faliszewski, P., Hemaspaandra, E., Schnoor, H.: Manipulation of Copeland elections. In: Proceedings of the 9th International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 367–374. IFAAMAS (2010)
Faliszewski, P., Procaccia, A.: AI’s war on manipulation: are we winning? AI Mag. 31(4), 53–64 (2010)
Flum, J., Grohe, M.: Parameterized Complexity Theory. EATCS Texts in Theoretical Computer Science. Springer-Verlag (2006)
Friedgut, E., Kalai, G., Nisan, N.: Elections can be manipulated often. In: Proceedings of the 49th IEEE Symposium on Foundations of Computer Science, pp. 243–249. IEEE Computer Society (2008)
Friedgut, E., Keller, N., Kalai, G., Nisan, N.: A quantitative version of the Gibbard–Satterthwaite theorem for three alternatives. SIAM J. Comput. 40(3), 934–952 (2011)
Gailmard, S., Patty, J., Penn, E.: Arrow’s theorem on single-peaked domains. In: Aragonés, E., Beviá, C., Llavador, H., Schofield, N. (eds.) The Political Economy of Democracy, pp. 335–342. Fundación BBVA (2009)
Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company (1979)
Gasarch, W.: The \({\ensuremath{\mathrm{P}}} =\,? \,{\ensuremath{\mathrm{NP}}}\) poll. SIGACT News 33(2), 34–47 (2002)
Gehrlein, W., Berg, S.: The effect of social homogeneity on coincidence probabilities for pairwise proportional lottery and simple majority rules. Soc. Choice Welf. 9(4), 361–372 (1992)
Gibbard, A.: Manipulation of voting schemes. Econometrica 41(4), 587–601 (1973)
Goldreich, O.: Notes on Levin’s theory of average-case complexity. Tech. Rep. TR97-058. Electronic Colloquium on Computational Complexity (1997)
Hemaspaandra, E., Hemaspaandra, L.: Dichotomy for voting systems. J. Comput. Syst. Sci. 73(1), 73–83 (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, pp. 377–388. Leibniz-Zentrum für Informatik (2013)
Hemaspaandra, E., Hemaspaandra, L., Rothe, J.: Exact analysis of Dodgson elections: Lewis Carroll’s 1876 voting system is complete for parallel access to NP. J. ACM 44(6), 806–825 (1997)
Hemaspaandra, E., Hemaspaandra, L., Rothe, J.: Raising NP lower bounds to parallel NP lower bounds. SIGACT News 28(2), 2–13 (1997)
Hemaspaandra, E., Hemaspaandra, L., Rothe, J.: Anyone but him: the complexity of precluding an alternative. Artif. Intell. 171(5–6), 255–285 (2007)
Hemaspaandra, E., Hemaspaandra, L., Rothe, J.: Hybrid elections broaden complexity-theoretic resistance to control. Math. Log. Q. 55(4), 397–424 (2009)
Hemaspaandra, L., Williams, R.: An atypical survey of typical-case heuristic algorithms. SIGACT News 43(4), 71–89 (2012)
Homan, C., Hemaspaandra, L.: Guarantees for the success frequency of an algorithm for finding Dodgson-election winners. J. Heuristics 15(4), 403–423 (2009)
Isaksson, M., Kindler, G., Mossel, E.: The geometry of manipulation: a quantitative proof of the Gibbard–Satterthwaite theorem. In: Proceedings of the 51st IEEE Symposium on Foundations of Computer Science, pp. 319–328. IEEE Computer Society (2010)
Isaksson, M., Kindler, G., Mossel, E.: The geometry of manipulation—a quantitative proof of the Gibbard–Satterthwaite theorem. Combinatorica 32(2), 221–250 (2012)
Konczak, K., Lang, J.: Voting procedures with incomplete preferences. In: Proceedings of the Multidisciplinary IJCAI-05 Workshop on Advances in Preference Handling, pp. 124–129 (2005)
Korf, R.: From approximate to optimal solutions: a case study of number partitioning. In: Proceedings of the 14th International Joint Conference on Artificial Intelligence, pp. 266–272 (1995)
Ladner, R., Lynch, N., Selman, A.: A comparison of polynomial time reducibilities. Theor. Comput. Sci. 1(2), 103–124 (1975)
Lenstra Jr., H.: Integer programming with a fixed number of variables. Math. Oper. Res. 8, 538–548 (1983)
Lepelley, D.: Constant scoring rules, Condorcet criteria, and single-peaked preferences. Economic Theory 7(3), 491–500 (1996)
Levin, L.: Average case complete problems. SIAM J. Comput. 15(1), 285–286 (1986)
Lindner, C., Rothe, J.: Fixed-parameter tractability and parameterized complexity, applied to problems from computational social choice. In: Holder, A. (ed.) Mathematical Programming Glossary. INFORMS Computing Society (2008)
Liu, H., Feng, H., Zhu, D., Luan, J.: Parameterized computational complexity of control problems in voting systems. Theor. Comput. Sci. 410(27–29), 2746–2753 (2009)
Liu, H., Zhu, D.: Parameterized complexity of control problems in maximin election. Inf. Process. Lett. 110(10), 383–388 (2010)
Mattei, N.: Empirical evaluation of voting rules with strictly ordered preference data. In: Proceedings of the 2nd International Conference on Algorithmic Decision Theory, pp. 165–177. Lecture Notes in Artificial Intelligence #6992. Springer-Verlag (2011)
McCabe-Dansted, J., Pritchard, G., Slinko, A.: Approximability of Dodgson’s rule. Soc. Choice Welf. 31(2), 311–330 (2008)
McCabe-Dansted, J., Slinko, A.: Exploratory analysis of similarities between common social choice rules. Group Decis. Negot. 15, 77–107 (2006)
Meir, R., Procaccia, A., Rosenschein, J., Zohar, A.: Complexity of strategic behavior in multi-winner elections. J. Artif. Intell. Res. 33, 149–178 (2008)
Menton, C.: Normalized range voting broadly resists control. Computing Research Repository (2012). Tech. Rep. arXiv:1005.5698 [cs.GT]. April 25, 2011. Revised June 26, 2012
Mossel, E., Rácz, M.: Election manipulation: the average case. ACM SIGecom Exchanges 11(2), 22–24 (2012)
Mossel, E., Rácz, M.: A quantitative Gibbard–Satterthwaite theorem without neutrality. In: Proceedings of the 44th Symposium on Theory of Computing, pp. 1041–1060. ACM (2012)
Nanson, E.: Methods of election. Proc. R. Soc. Vic. 19, 197–240 (1882)
Narodytska, N., Walsh, T., Xia, L.: Manipulation of Nanson’s and Baldwin’s rules. In: Proceedings of the 25th AAAI Conference on Artificial Intelligence, pp. 713–718. AAAI Press (2011)
Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press (2006)
Ogiwara, M., Watanabe, O.: On polynomial-time bounded truth-table reducibility of NP sets to sparse sets. SIAM J. Comput. 20(3), 471–483 (1991)
Procaccia, A.: Can approximation circumvent Gibbard-Satterthwaite? In: Proceedings of the 24th AAAI Conference on Artificial Intelligence, pp. 836–841 (2010)
Procaccia, A., Rosenschein, J.: Average-case tractability of manipulation in voting via the fraction of manipulators. In: Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems, vol. 718–720 (2007). Short paper
Procaccia, A., Rosenschein, J.: Junta distributions and the average-case complexity of manipulating elections. J. Artif. Intell. Res. 28, 157–181 (2007)
Reisch, Y.: Das Manipulationsproblem für Bucklin–Wahlen. Bachelor thesis, Heinrich-Heine-Universität Düsseldorf, Institut für Informatik, Düsseldorf, Germany (2012)
Rothe, J., Schend, L.: Control complexity in Bucklin, fallback, and plurality voting: an experimental approach. In: Proceedings of the 11th International Symposium on Experimental Algorithms, pp. 356–368. Lecture Notes in Computer Science #7276. Springer-Verlag (2012)
Rothe, J., Schend, L.: Control complexity in Bucklin, fallback, and plurality voting: an experimental approach. Computing Research Repository (2012). Tech. Rep. arXiv:1203.3967v1 [cs.GT]. March 18, 2012. Revised August 20, 2012
Satterthwaite, M.: Strategy-proofness and Arrow’s conditions: existence and correspondence theorems for voting procedures and social welfare functions. J. Econ. Theory 10(2), 187–217 (1975)
Schöning, U.: Complete sets and closeness to complexity classes. Math. Syst. Theory 19(1), 29–42 (1986)
Slinko, A.: On asymptotic strategy-proofness of classical social choice rules. Theory Decis. 52(4), 389–398 (2002)
Slinko, A.: On asymptotic strategy-proofness of the plurality and the run-off rules. Soc. Choice Welf. 19(2), 313–324 (2002)
Slinko, A.: How large should a coalition be to manipulate an election? Math. Soc. Sci. 47(3), 289–293 (2004)
Tideman, N.: Independence of clones as a criterion for voting rules. Soc. Choice Welf. 4(3), 185–206 (1987)
Walsh, T.: Uncertainty in preference elicitation and aggregation. In: Proceedings of the 22nd AAAI Conference on Artificial Intelligence, pp. 3–8. AAAI Press (2007)
Walsh, T.: Where are the really hard manipulation problems? The phase transition in manipulating the veto rule. In: Proceedings of the 21st International Joint Conference on Artificial Intelligence, pp. 324–329. IJCAI (2009)
Walsh, T.: An empirical study of the manipulability of single transferable voting. In: Proceedings of the 19th European Conference on Artificial Intelligence, pp. 257–262. IOS Press (2010)
Wang, J.: Average-case computational complexity theory. In: Hemaspaandra, L., Selman, A. (eds.) Complexity Theory Retrospective II, pp. 295–328. Springer-Verlag (1997)
Wang, J.: Average-case intractable NP problems. In: Du, D., Ko, K. (eds.) Advances in Languages, Algorithms, and Complexity, pp. 313–378. Kluwer Academic Publishers (1997)
Xia, L., Conitzer, V.: Generalized scoring rules and the frequency of coalitional manipulability. In: Proceedings of the 9th ACM Conference on Electronic Commerce, pp. 109–118. ACM Press (2008)
Xia, L., Conitzer, V.: A sufficient condition for voting rules to be frequently manipulable. In: Proceedings of the 9th ACM Conference on Electronic Commerce, pp. 99–108. ACM Press (2008)
Xia, L., Conitzer, V., Procaccia, A.: A scheduling approach to coalitional manipulation. In: Proceedings of the 11th ACM Conference on Electronic Commerce, pp. 275–284. ACM Press (2010)
Xia, L., Zuckerman, M., Procaccia, A., Conitzer, V., Rosenschein, J.: Complexity of unweighted coalitional manipulation under some common voting rules. In: Proceedings of the 21st International Joint Conference on Artificial Intelligence, pp. 348–353. IJCAI (2009)
Zuckerman, M., Lev, O., Rosenschein, J.: An algorithm for the coalitional manipulation problem under maximin. In: Proceedings of the 10th International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 845–852. IFAAMAS (2011)
Zuckerman, M., Procaccia, A., Rosenschein, J.: Algorithms for the coalitional manipulation problem. Artif. Intell. 173(2), 392–412 (2009)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported in part by DFG grant RO-1202/15-1, SFF grant “Cooperative Normsetting” of HHU Düsseldorf, and a DAAD grant for a PPP project in the PROCOPE programme.
Rights and permissions
About this article
Cite this article
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, 161–193 (2013). https://doi.org/10.1007/s10472-013-9359-5
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10472-013-9359-5