Abstract
Compiling the votes of a subelectorate is a well-known problem in computational social choice. The goal is to store the information contained in the votes cast by a subelectorate in a space-efficient way, such that when the rest of the votes become available, the winners can be accurately ascertained. This problem has been studied for single-winner voting rules. We provide a comprehensive compilation complexity landscape for several ordinal and approval-based multi-winner voting rules.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
For approval-based rules, by (abc) we indicate that a, b, c are approved in the vote. For ordinal rules we sometimes use (abc) to indicate the vote \(a \succ b \succ c\).
References
Aziz, H., Elkind, E., Faliszewski, P., Lackner, M., Skowron, P.: The Condorcet principle for multiwinner elections: from shortlisting to proportionality. In: Proceedings of IJCAI 2017, pp. 84–90 (2017)
Barberà, S., Coelho, D.: How to choose a non-controversial list with k names. Soc. Choice Welf. 31(1), 79–96 (2008)
Chevaleyre, Y., Lang, J., Maudet, N., Monnot, J.: Compilation and communication protocols for voting rules with a dynamic set of candidates. In: Proceedings of TARK 2011, pp. 153–160 (2011)
Chevaleyre, Y., Lang, J., Maudet, N., Ravilly-Abadie, G.: Compiling the votes of a subelectorate. In: Proceedings of IJCAI 2009, pp. 97–102 (2009)
Coelho, D.: Understanding, evaluating and selecting voting rules through games and axioms. Ph.D. thesis (2004)
Conitzer, V., Sandholm, T.: Vote elicitation: complexity and strategy-proofness. In: Proceedings of AAAI-2001, pp. 392–397 (2002)
Dey, P., Bhattacharyya, A.: Sample complexity for winner prediction in elections. In: Proceedings of AAMAS 2015, pp. 1421–1430 (2015)
Dey, P., Talmon, N., Van Handel, O.: Proportional representation in vote streams. arXiv preprint arXiv:1702.08862 (2017)
Elkind, E., Faliszewski, P., Skowron, P., Slinko, A.: Properties of multiwinner voting rules. Soc. Choice Welf. 48(3), 599–632 (2017)
Elkind, E., Lang, J., Saffidine, A.: Condorcet winning sets. Soc. Choice Welf. 44(3), 493–517 (2015)
Faliszewski, P., Skowron, P., Slinko, A., Talmon, N.: Multiwinner voting: a new challenge for social choice theory. Trends Comput. Soc. Choice 74, 27–47 (2017)
Gehrlein, W.: The condorcet criterion and committee selection. Math. Soc. Sci. 10(3), 199–209 (1985)
Hazon, N., Aumann, Y., Kraus, S., Wooldridge, M.: On the evaluation of election outcomes under uncertainty. Artif. Intell. 189, 1–18 (2012)
Janson, S.: Phragmén’s and thiele’s election methods. Technical report (2016)
Konczak, K., Lang, J.: Voting procedures with incomplete preferences. In: Proceedings of the IJCAI-2005 Multidisciplinary Workshop on Advances in Preference Handling, vol. 20. Citeseer (2005)
Lackner, M., Skowron, P.: Multi-Winner Voting with Approval Preferences - Artificial Intelligence, Multiagent Systems, and Cognitive Robotics. Springer Briefs in Intelligent Systems, Springer, Cham (2023). https://doi.org/10.1007/978-3-031-09016-5
Peters, D., Pierczyński, G., Skowron, P.: Proportional participatory budgeting with additive utilities. In: Proceedings of NeurIPS 2021, pp. 12726–12737 (2021)
Skowron, P., Faliszewski, P., Slinko, A.: Axiomatic characterization of committee scoring rules. J. Econ. Theory 180, 244–273 (2019)
Xia, L., Conitzer, V.: Compilation complexity of common voting rules. In: Proceedings of AAAI 2010, pp. 915–920 (2010)
Acknowledgements
We are grateful to the anonymous reviewers for their careful reading and helpful comments. This work was supported in part by project ANR-22-CE26-0019 “Citizens”, funded by the French Agence Nationale de la Recherche.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2025 The Author(s), under exclusive license to Springer Nature Switzerland
About this paper
Cite this paper
Karia, N., Lang, J. (2025). Compiling the Votes of a Subelectorate for Multi-winner Voting Rules. 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_2
Download citation
DOI: https://doi.org/10.1007/978-3-031-73903-3_2
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)