Complexity of Candidate Control for Single Nontransferable Vote and Bloc Voting | SpringerLink
Skip to main content
Springer Nature Link
Log in

Complexity of Candidate Control for Single Nontransferable Vote and Bloc Voting

  • Conference paper
  • First Online:
Algorithmic Decision Theory (ADT 2024)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 15248))

Included in the following conference series:

  • 113 Accesses

Abstract

Electoral control is a scenario where an election chair changes the structure of an election by actions such as adding or deleting either candidates or voters with the goal of either making a favorite candidate win or precluding a despised candidate’s victory. Much work has been done on the computational complexity of controlling elections for single-winner voting rules, yet much less work on the control complexity for multiwinner voting rules which aim at electing not only a single winner but a winning committee of candidates. Meir et al. [20] initiated the investigation of electoral control for multiwinner voting rules, including single nontransferable vote (SNTV) and bloc voting. We study these two rules with respect to control by adding, deleting, or replacing candidates.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 6634
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 8293
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Bartholdi, J., III., Tovey, C., Trick, M.: How hard is it to control an election? Math. Comput. Model. 16(8/9), 27–40 (1992)

    Article  MathSciNet  Google Scholar 

  2. Baumeister, D., Faliszewski, P., Rothe, J., Skowron, P.: Multiwinner voting. In: Rothe, J. (ed.) Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division. Classroom Companion: Economics, 2nd edn., chap. 6, pp. 403–465. Springer, Cham (2024). https://doi.org/10.1007/978-3-031-60099-9

  3. Baumeister, D., Rothe, J.: Preference aggregation by voting. In: Rothe, J. (ed.) Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division. Classroom Companion: Economics, 2nd edn., chap. 4, pp. 233–367. Springer, Cham (2024). https://doi.org/10.1007/978-3-031-60099-9_4

  4. Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A. (eds.): Handbook of Computational Social Choice. Cambridge University Press, Cambridge (2016)

    Google Scholar 

  5. Chamberlin, J., Courant, P.: Representative deliberations and representative decisions: proportional representation and the Borda rule. Am. Polit. Sci. Rev. 77(3), 718–733 (1983)

    Article  Google Scholar 

  6. Conitzer, V., Walsh, T.: Barriers to manipulation in voting. In: Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A. (eds.) Handbook of Computational Social Choice, chap. 6, pp. 127–145. Cambridge University Press (2016)

    Google Scholar 

  7. Dwork, C., Kumar, R., Naor, M., Sivakumar, D.: Rank aggregation methods for the web. In: Proceedings of the 10th International World Wide Web Conference, pp. 613–622. ACM Press (2001)

    Google Scholar 

  8. Ephrati, E., Rosenschein, J.: The Clarke Tax as a consensus mechanism among automated agents. In: Proceedings of the 9th National Conference on Artificial Intelligence, pp. 173–178. AAAI Press (1991)

    Google Scholar 

  9. Ephrati, E., Rosenschein, J.: A heuristic technique for multi-agent planning. Ann. Math. Artif. Intell. 20(1–4), 13–67 (1997)

    Article  MathSciNet  Google Scholar 

  10. Erdélyi, G., Neveling, M., Reger, C., Rothe, J., Yang, Y., Zorn, R.: Towards completing the puzzle: complexity of control by replacing, adding, and deleting candidates or voters. J. Auton. Agents Multi-Agent Syst. 35(2), 41:1–41:48 (2021)

    Google Scholar 

  11. Fagin, R., Kumar, R., Sivakumar, D.: Efficient similarity search and classification via rank aggregation. In: Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, pp. 301–312. ACM Press (2003). Corrigendum: https://doi.org/10.1145/1376616.1376778

  12. Faliszewski, P., Rothe, J.: Control and bribery in voting. In: Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A. (eds.) Handbook of Computational Social Choice, chap. 7, pp. 146–168. Cambridge University Press (2016)

    Google Scholar 

  13. Faliszewski, P., Skowron, P., Slinko, A., Talmon, N.: Multiwinner voting: a new challenge for social choice theory. In: Endriss, U. (ed.) Trends in Computational Social Choice, chap. 2, pp. 27–47. AI Access Foundation (2017)

    Google Scholar 

  14. Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company (1979)

    Google Scholar 

  15. Hemaspaandra, E., Hemaspaandra, L., Rothe, J.: Anyone but him: the complexity of precluding an alternative. Artif. Intell. 171(5–6), 255–285 (2007)

    Article  MathSciNet  Google Scholar 

  16. Lang, J., Maudet, N., Polukarov, M.: New results on equilibria in strategic candidacy. In: Vöcking, B. (ed.) SAGT 2013. LNCS, vol. 8146, pp. 13–25. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-41392-6_2

    Chapter  Google Scholar 

  17. Loreggia, A.: Iterative voting, control and sentiment analysis. Ph.D. thesis, University of Padova (2016)

    Google Scholar 

  18. Loreggia, A., Narodytska, N., Rossi, F., Venable, B., Walsh, T.: Controlling elections by replacing candidates or votes (extended abstract). In: Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems, pp. 1737–1738. IFAAMAS (2015)

    Google Scholar 

  19. Maushagen, C., Niclaus, D., Nüsken, P., Rothe, J., Seeger, T.: Toward completing the picture of control in Schulze and ranked pairs elections. In: Proceedings of the 33rd International Joint Conference on Artificial Intelligence. ijcai.org (2024)

    Google Scholar 

  20. Meir, R., Procaccia, A., Rosenschein, J., Zohar, A.: Complexity of strategic behavior in multi-winner elections. J. Artif. Intell. Res. 33, 149–178 (2008)

    Article  MathSciNet  Google Scholar 

  21. Pennock, D., Horvitz, E., Giles, C.: Social choice theory and recommender systems: analysis of the axiomatic foundations of collaborative filtering. In: Proceedings of the 17th National Conference on Artificial Intelligence, pp. 729–734. AAAI Press (2000)

    Google Scholar 

  22. Rothe, J. (ed.): Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division. Classroom Companion: Economics, 2nd edn. Springer, Cham (2024)

    Google Scholar 

  23. Yang, Y.: Complexity of manipulating and controlling approval-based multiwinner voting. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 637–643. ijcai.org (2019)

    Google Scholar 

Download references

Acknowledgments

We thank the anonymous reviewers for helpful comments. This work was supported in part by Deutsche Forschungsgemeinschaft (DFG) under grants RO-1202/21-1 and RO-1202/21-2 (project number 438204498).

Author information

Authors and Affiliations

  1. MNF, Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany

    Garo Karh Bet, Jörg Rothe & Roman Zorn

Authors
  1. Garo Karh Bet
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jörg Rothe
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Roman Zorn
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jörg Rothe .

Editor information

Editors and Affiliations

  1. University of Virginia, Charlottesville, USA

    Rupert Freeman

  2. Tulane University, New Orleans, LA, USA

    Nicholas Mattei

Rights and permissions

Reprints and permissions

Copyright information

© 2025 The Author(s), under exclusive license to Springer Nature Switzerland

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Karh Bet, G., Rothe, J., Zorn, R. (2025). Complexity of Candidate Control for Single Nontransferable Vote and Bloc Voting. In: Freeman, R., Mattei, N. (eds) Algorithmic Decision Theory. ADT 2024. Lecture Notes in Computer Science(), vol 15248. Springer, Cham. https://doi.org/10.1007/978-3-031-73903-3_1

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-73903-3_1

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-73902-6

  • Online ISBN: 978-3-031-73903-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation