Skip to main content

Advertisement

SpringerLink
Log in

Complexity of manipulation, bribery, and campaign management in Bucklin and fallback voting

  • Published:
Autonomous Agents and Multi-Agent Systems Aims and scope Submit manuscript

Abstract

A central theme in computational social choice is to study the extent to which voting systems computationally resist manipulative attacks seeking to influence the outcome of elections, such as manipulation (i.e., strategic voting), control, and bribery. Bucklin and fallback voting are among the voting systems with the broadest resistance (i.e., NP-hardness) to control attacks. However, only little is known about their behavior regarding manipulation and bribery attacks. We comprehensively investigate the computational resistance of Bucklin and fallback voting for many of the common manipulation and bribery scenarios; we also complement our discussion by considering several campaign-management problems for these two voting rules.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. Recall, for example, the celebrated Gibbard–Satterthwaite theorem [35, 46] that, essentially, says that only dictatorial voting rules are strategy-proof; see also its extension to irresolute voting rules that is due to Duggan and Schwartz [18]. The notion of strategic candidacy, studied by Dutta et al. [19], has a similar flavor from the point of view of candidate control. From the point of view of voter control, it is absolutely natural to expect that if we add sufficiently many votes supporting a given candidate, this candidate should win. The same applies to bribery: If we can bribe everyone, we should be able to ensure any candidate’s victory.

  2. Resistance to manipulative actions is most often meant to be NP-hardness in the literature. Being a worst-case measure only, NP-hardness does have its limitations. There are also a number of other approaches that challenge such NP-hardness results, surveyed in [45]; for example, there are some experimental results on the control complexity of Bucklin and fallback voting [44].

  3. Other voting systems whose control complexity has been thoroughly studied include plurality, Condorcet, and approval voting [3, 36], Llull and Copeland voting [29], a variant of approval voting known as SP-AV [24], range voting and normalized range voting [39], and Schulze voting [40, 42] (see [33] for an overview).

  4. In simplified Bucklin voting, all these candidates win. However, we consider Bucklin voting in the unsimplified version where winners are determined by a slightly more involved procedure. Note that every Bucklin winner, as defined in the main text, also wins in simplified Bucklin voting, but not necessarily the other way round.

  5. We introduce this notation for Proposition 1 only; throughout the rest of the paper we will slightly abuse notation by always using the abbreviations \(\fancyscript{E}\)-CCWM, \(\fancyscript{E}\)-CCUM, \(\fancyscript{E}\)-DCWM, and \(\fancyscript{E}\)-DCUM whenever the winner model will be clear from the context.

  6. Note that the first voter in Group 3 ranks \(c_{\frac{m}{2}}\) on position \(\frac{m}{2}+1\).

  7. By “all else being equal” we tacitly mean that all other candidates remain in the same position in each vote, except those candidates that improve their position by one due to shifting \(c\) toward the bottom. An analogous comment applies to the cases where \(c\)’s position is improved in the second statement of this lemma and where other candidates are swapped in the third statement of this lemma.

  8. Like fallback voting, SP-AV is a hybrid variant of approval voting. It has been introduced by Brams and Sanver [9] and slightly modified by Erdélyi et al. [24] to cope with certain control actions (see also the chapter by Baumeister et al. [4] for a thorough discussion of this voting system).

  9. We note that this approach to solving the destructive cases is not general, but it is easy to see that it works for fallback.

  10. They also show that the problem is hard in the sense of parametrized complexity for two natural parameters describing the extent of change to the number of approved candidates. Interestingly, they show the problem to be fixed-parameter tractable if the number of approved candidates can either only increase or only decrease.

References

  1. Bartholdi III, J., & Orlin, J. (1991). Single transferable vote resists strategic voting. Social Choice and Welfare, 8(4), 341–354.

  2. Bartholdi III, J., Tovey, C., & Trick, M. (1989). The computational difficulty of manipulating an election. Social Choice and Welfare, 6(3), 227–241.

  3. Bartholdi III, J., Tovey, C., & Trick, M. (1992). How hard is it to control an election? Mathematical and Computer Modelling, 16(8/9), 27–40.

  4. Baumeister, D., Erdélyi, G., Hemaspaandra, E., Hemaspaandra, L., & Rothe, J. (2010). Computational aspects of approval voting. In J. Laslier & R. Sanver (Eds.), Handbook on approval voting, chap. 10 (pp. 199–251). Berlin: Springer.

    Chapter  Google Scholar 

  5. Baumeister, D., Faliszewski, P., Lang, J., & Rothe, J. (2102). Campaigns for lazy voters: Truncated ballots. Proceedings of the 11th International Joint Conference on Autonomous Agents and Multiagent Systems, IFAAMAS (pp. 577–584).

  6. Betzler, N., Niedermeier, R., & Woeginger, G. (2011). Unweighted coalitional manipulation under the Borda rule is NP-hard. Proceedings of the 22nd International Joint Conference on Artificial Intelligence (pp. 55–60).

  7. Brams, S., & Fishburn, P. (1978). Approval voting. American Political Science Review, 72(3), 831–847.

    Article  Google Scholar 

  8. Brams, S., & Fishburn, P. (1983). Approval voting. Boston: Birkhäuser.

    MATH  Google Scholar 

  9. Brams, S., & Sanver, R. (2006). Critical strategies under approval voting: Who gets ruled in and ruled out. Electoral Studies, 25(2), 287–305.

    Article  Google Scholar 

  10. Brams, S., & Sanver, R. (2009). Voting systems that combine approval and preference. In S. Brams, W. Gehrlein, & F. Roberts (Eds.), The mathematics of preference, choice, and order: Essays in honor of Peter C. Fishburn (pp. 215–237). Berlin: Springer.

    Chapter  Google Scholar 

  11. Brandt, F., Conitzer, V., & Endriss, U. (2013). Computational social choice. In G. Weiß (Ed.), Multiagent systems (2nd ed., pp. 213–283). Cambridge, MA: MIT Press.

    Google Scholar 

  12. Bredereck, R., Chen, J., Faliszewski, P., Nichterlein, A., & Niedermeier, R. (2014). Prices matter for the parameterized complexity of shift bribery. Proceedings of the 28th AAAI Conference on Artificial Intelligence (pp. 1398–1404). AAAI Press.

  13. Brelsford, E., Faliszewski, P., Hemaspaandra, E., Schnoor, H., & Schnoor, I. (2008). Approximability of manipulating elections. In: Proceedings of the 23rd AAAI Conference on Artificial Intelligence (pp. 44–49). AAAI Press.

  14. Conitzer, V., Sandholm, T., & Lang, J. (2007). When are elections with few candidates hard to manipulate? Journal of the ACM, 54(3), 14.

    Article  MathSciNet  Google Scholar 

  15. Conitzer, V., & Walsh, T. (2014). Barriers to manipulation. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, & A. Procaccia (Eds.), Handbook of computational social choice. Cambridge: Cambridge University Press.

    Google Scholar 

  16. Davies, J., Katsirelos, G., Narodytska, N., & Walsh, T. (2011). Complexity of and algorithms for Borda manipulation. Proceedings of the 25th AAAI Conference on Artificial Intelligence (pp. 657–662).

  17. Dorn, B., & Schlotter, I. (2012). Multivariate complexity analysis of swap bribery. Algorithmica, 64(1), 126–151.

    Article  MathSciNet  MATH  Google Scholar 

  18. Duggan, J., & Schwartz, T. (2000). Strategic manipulability without resoluteness or shared beliefs: Gibbard–Satterthwaite generalized. Social Choice and Welfare, 17(1), 85–93.

    Article  MathSciNet  MATH  Google Scholar 

  19. Dutta, B., Jackson, M., & Le Breton, M. (2001). Strategic candidacy and voting procedures. Econometrica, 69(4), 1013–1037.

    Article  MathSciNet  MATH  Google Scholar 

  20. Elkind, E., & Faliszewski, P. (2010). Approximation algorithms for campaign management. Proceedings of the 6th International Workshop on Internet and Network Economics (pp. 473–482). Springer, Lecture Notes in Computer Science #6484.

  21. Elkind, E., Faliszewski, P., & Slinko, A. (2009). Swap bribery. Proceedings of the 2nd International Symposium on Algorithmic Game Theory (pp. 299–310). Springer, Lecture Notes in Computer Science #5814

  22. Erdélyi, G., & Fellows, M. (2010). Parameterized control complexity in Bucklin voting and in fallback voting. In V. Conitzer & J. Rothe (Eds.), Proceedings of the 3rd International Workshop on Computational Social Choice (pp. 163–174). Universität Düsseldorf.

  23. Erdélyi, G., Fellows, M., Rothe, J., & Schend, L. (2012). Control complexity in Bucklin and fallback voting. Technical Report arXiv:1103.2230 [cs.CC], Computing Research Repository, arXiv:org/corr/ (2012). March, 2011. Revised August, 2012. An extended version merging the CATS-2010, COMSOC-2010, AAMAS-2011, and SEA-2012 papers [26,22,25,44] has been accepted for publication in Journal of Computer and System Sciences.

  24. Erdélyi, G., Nowak, M., & Rothe, J. (2009). Sincere-strategy preference-based approval voting fully resists constructive control and broadly resists destructive control. Mathematical Logic Quarterly, 55(4), 425–443.

    Article  MathSciNet  MATH  Google Scholar 

  25. Erdélyi, G., Piras, L., & Rothe, J. (2011). The complexity of voter partition in Bucklin and fallback voting: Solving three open problems. Proceedings of the 10th International Joint Conference on Autonomous Agents and Multiagent Systems. IFAAMAS (pp. 837–844).

  26. Erdélyi, G., & Rothe, J. (2010). Control complexity in fallback voting. Proceedings of Computing: the 16th Australasian Theory Symposium (pp. 39–48). Australian Computer Society Conferences in Research and Practice in Information Technology Series, vol. 32, no. 8.

  27. Faliszewski, P., Hemaspaandra, E., & Hemaspaandra, L. (2009). How hard is bribery in elections? Journal of Artificial Intelligence Research, 35, 485–532.

    MathSciNet  MATH  Google Scholar 

  28. Faliszewski, P., Hemaspaandra, E., & Hemaspaandra, L. (2010). Using complexity to protect elections. Communications of the ACM, 53(11), 74–82.

    Article  Google Scholar 

  29. Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L., & Rothe, J. (2009). Llull and Copeland voting computationally resist bribery and constructive control. Journal of Artificial Intelligence Research, 35, 275–341.

    MathSciNet  MATH  Google Scholar 

  30. Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L., & Rothe, J. (2009). A richer understanding of the complexity of election systems. In S. Ravi & S. Shukla (Eds.), Fundamental problems in computing: Essays in honor of professor Daniel J. Rosenkrantz, chap. 14 (pp. 375–406). Dordrecht: Springer.

    Chapter  Google Scholar 

  31. Faliszewski, P., Hemaspaandra, E., & Schnoor, H. (2010). Manipulation of Copeland elections. Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (pp. 367–374). International Foundation for Autonomous Agents and Multiagent Systems.

  32. Faliszewski, P., & Procaccia, A. (2010). AI’s war on manipulation: Are we winning? AI Magazine, 31(4), 53–64.

    Google Scholar 

  33. Faliszewski, P., & Rothe, J. (2014). Control and bribery. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, & A. Procaccia (Eds.), Handbook of computational social choice. Cambridge: Cambridge University Press.

    Google Scholar 

  34. Garey, M., & Johnson, D. (1979). Computers and intractability: A guide to the theory of NP-completeness. New York: W. H. Freeman and Company.

    MATH  Google Scholar 

  35. Gibbard, A. (1973). Manipulation of voting schemes. Econometrica, 41(4), 587–601.

    Article  MathSciNet  MATH  Google Scholar 

  36. Hemaspaandra, E., Hemaspaandra, L., & Rothe, J. (2007). Anyone but him: The complexity of precluding an alternative. Artificial Intelligence, 171(5–6), 255–285.

    Article  MathSciNet  MATH  Google Scholar 

  37. Konczak, K., & Lang, J. (2005). Voting procedures with incomplete preferences. Proceedings of the Multidisciplinary IJCAI-05 Workshop on Advances in Preference Handling (pp. 124–129).

  38. Lin, A. (2012). Solving hard problems in election systems. Ph.D. thesis, Rochester Institute of Technology, Rochester, NY.

  39. Menton, C. (2013). Normalized range voting broadly resists control. Theory of Computing Systems, 53(4), 507–531.

    Article  MathSciNet  MATH  Google Scholar 

  40. Menton, C., & Singh, P. (2013). Control complexity of Schulze voting. Proceedings of the 23rd International Joint Conference on Artificial Intelligence (pp. 286–292). AAAI Press/IJCAI.

  41. Papadimitriou, C. (1995). Computational complexity (2nd ed.). Reading, MA: Addison-Wesley.

    Google Scholar 

  42. Parkes, D., & Xia, L. (2012). A complexity-of-strategic-behavior comparison between Schulze’s rule and ranked pairs. Proceedings of the 26th AAAI Conference on Artificial Intelligence (pp. 1429–1435). AAAI Press.

  43. Rothe, J. (2005). Complexity theory and cryptology. An introduction to cryptocomplexity. EATCS texts in theoretical computer science. Berlin: Springer.

    Google Scholar 

  44. Rothe, J., & Schend, L. (2012). Control complexity in Bucklin, fallback, and plurality voting: An experimental approach. Proceedings of the 11th International Symposium on Experimental Algorithms (pp. 356–368). Springer, Lecture Notes in Computer Science #7276.

  45. Rothe, J., & Schend, L. (2013). Challenges to complexity shields that are supposed to protect elections against manipulation and control: A survey. Annals of Mathematics and Artificial Intelligence, 68(1–3), 161–193.

    Article  MathSciNet  MATH  Google Scholar 

  46. Satterthwaite, M. (1975). Strategy-proofness and Arrow’s conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, 10(2), 187–217.

    Article  MathSciNet  MATH  Google Scholar 

  47. Schlotter, I., Faliszewski, P., & Elkind, E. (2011). Campaign management under approval-driven voting rules. Proceedings of the 25th AAAI Conference on Artificial Intelligence (pp. 726–731).

  48. Walsh, T. (2011). Where are the hard manipulation problems? Journal of Artificial Intelligence Research, 42, 1–29.

  49. Xia, L. (2012). Computing the margin of victory for various voting rules. Proceedings of the 13th ACM Conference on Electronic Commerce (pp. 982–999). ACM Press.

  50. Xia, L., & Conitzer, V. (2011). Determining possible and necessary winners given partial orders. Journal of Artificial Intelligence Research, 41, 25–67.

    MathSciNet  MATH  Google Scholar 

  51. Xia, L., Zuckerman, M., Procaccia, A., Conitzer, V., & Rosenschein, J. (2009). Complexity of unweighted coalitional manipulation under some common voting rules. Proceedings of the 21st International Joint Conference on Artificial Intelligence (pp. 348–353). IJCAI.

Download references

Acknowledgments

We thank Edith Hemaspaandra and Lane A. Hemaspaandra for interesting discussions on these results after a RIT/UR Theory Canal talk. This work was supported in part by DFG Grant RO 1202/15-1, by a DAAD Grant for a PPP Project in the PROCOPE Program, by NCN Grants 2012/06/M/ST1/00358 and 2011/03/B/ST6/01393, and by AGH University Grant 11.11.230.124.

Author information

Authors and Affiliations

  1. AGH University, Krakow, Poland

    Piotr Faliszewski

  2. Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany

    Yannick Reisch, Jörg Rothe & Lena Schend

Authors
  1. Piotr Faliszewski
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yannick Reisch
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jörg Rothe
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Lena Schend
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lena Schend.

Additional information

A preliminary version of this paper appeared as an extended abstract in the proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2014).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Faliszewski, P., Reisch, Y., Rothe, J. et al. Complexity of manipulation, bribery, and campaign management in Bucklin and fallback voting. Auton Agent Multi-Agent Syst 29, 1091–1124 (2015). https://doi.org/10.1007/s10458-014-9277-x

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10458-014-9277-x

Keywords

Search

Navigation