Abstract
We consider the general case of approval-based committee elections, where some attributes divide the voters into diverse groups which vary in size. This scenario occurs in applications like the presidential election, where voters come from different parties, or the student board election at a university with students from different schools. However, all existing committee election rules either are derived for the single-group case, or neglect the welfare of groups with few votes. Therefore, new voting rules are needed for this setting. In this paper, We propose two natural axioms for this setting, namely, small group benefited representation (SGBR) and large group benefited representation (LGBR). SGBR requires that if the committee size exceeds the number of groups, at least one candidate approved by each group is in the winning committee. LGBR requires that the winning committee must have at least as many candidates approved by a large group as by a small group. Based on the axioms, we propose three models and investigate parameterized complexity of the models with respect to various parameters. We show that all models are fixed-parameter tractable (FPT) when parameterized by the number n of votes, whereas they become fixed-parameter intractable when parameterized by the size k of the committee or d of the satisfaction bound.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aziz, H., Brill, M., Conitzer, V., Elkind, E., Freeman, R., Walsh, T.: Justified representation in approval-based committee voting. Soc. Choice Welfare 48(2), 461–485 (2017)
Aziz, H., Gaspers, S., Gudmundsson, J., Mackenzie, S., Mattei, N., Walsh, T.: Computational aspects of multi-winner approval voting. In: AAMAS 2015, pp. 107–115 (2015)
Baumeister, D., Dennisen, S., Rey, L.: Winner determination and manipulation in minisum and minimax committee elections. In: ADT 2015. vol. 9346, pp. 469–485 (2015)
Bei, X., Liu, S., Poon, C.K., Wang, H.: Candidate selections with proportional fairness constraints. Auton. Agent. Multi-Agent Syst. 36(1), 5 (2022)
Brams, S.: Mathematics and democracy: designing better voting and fair-division procedures. Math. Comput. Modell. 48(9–10), 1666–1670 (2008)
Brams, S., Kilgour, D.M., Sanver, M.R.: A minimax procedure for electing committees. Public Choice 132, 401–420 (2007)
Brams, S.J., Kilgour, D.M.: Satisfaction approval voting. In: Fara, R., Leech, D., Salles, M. (eds.) Voting Power and Procedures. SCW, pp. 323–346. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-05158-1_18
Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A.D. (eds.): Handbook of Computational Social Choice. Cambridge University Press, Cambridge (2016)
Bredereck, R., Chen, J., Faliszewski, P., Guo, J., Niedermeier, R., Woeginger, G.J.: Parameterized algorithmics for computational social choice: Nine research challenges. Tsinghua Sci. Technol. 19(4), 358–373 (2014)
Bredereck, R., Faliszewski, P., Igarashi, A., Lackner, M., Skowron, P.: Multiwinner elections with diversity constraints. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence, pp. 933–940 (2018)
Celis, L.E., Huang, L., Vishnoi, N.K.: Multiwinner voting with fairness constraints. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence, pp. 144–151 (2018)
Chamberlin, J., Courant, P.: Representative deliberations and representative decisions: proportional representation and the Borda rule. Am. Polit. Sci. Rev. 77(3), 718–733 (1983)
Conitzer, V.: Making decisions based on the preferences of multiple agents. Commun. ACM 53(3), 84–94 (2010)
Downey, R., Fellows, M.: Parameterized Complexity. Springer Science & Business Media (2012)
Faliszewski, P., Talmon, N.: Between proportionality and diversity: balancing district sizes under the Chamberlin-courant rule. In: Proceedings of the 17th International Conference on Autonomous Agents and Multi-Agent Systems, pp. 14–22 (2018)
Fernández, L., et al.: Proportional justified representation. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence, pp. 670–676 (2017)
Fishburn, P.: Axioms for approval voting: direct proof. J. Econ. Theory 19(1), 180–185 (1978)
Ianovski, E.: Electing a committee with dominance constraints. Ann. Oper. Res. 318(2), 985–1000 (2022)
Kilgour, D.M., Marshall, E.: Approval balloting for fixed-size committees. Electoral systems: paradoxes, assumptions, and procedures, pp. 305–326 (2012)
Kilgour, M.: Approval balloting for multi-winner elections. In: Handbook on Approval Voting, pp. 105–124. Springer (2010). https://doi.org/10.1007/978-3-642-02839-7_6
Lang, J., Skowron, P.: Multi-attribute proportional representation. Artif. Intell. 263, 74–106 (2018)
LeGrand, R., Markakis, E., Mehta, A.: Some results on approximating the minimax solution in approval voting. In: AAMAS 2007, p. 198 (2007)
Lenstra, H.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538–548 (1983)
Obraztsova, S., Zick, Y., Elkind, E.: On manipulation in multi-winner elections based on scoring rules. In: AAMAS 2013, pp. 359–366 (2013)
Procaccia, A.D., Rosenschein, J.S., Zohar, A.: On the complexity of achieving proportional representation. Soc. Choice Welfare 30(3), 353–362 (2008)
Talmon, N.: Structured proportional representation. Theoret. Comput. Sci. 708, 58–74 (2018)
Thiele, T.N.: Om flerfoldsvalg. Oversigt over det Kongelige Danske Videnskabernes Selskabs Forhandlinger 1895, 415–441 (1895)
Zwicker, W.S.: Introduction to the theory of voting. In: Handbook of Computational Social Choice, pp. 23–56. Cambridge University Press (2016)
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Wen, Y., Song, C., Zhou, A., Guo, J. (2024). Multi-winner Approval Voting with Grouped Voters. In: Wu, W., Guo, J. (eds) Combinatorial Optimization and Applications. COCOA 2023. Lecture Notes in Computer Science, vol 14462. Springer, Cham. https://doi.org/10.1007/978-3-031-49614-1_20
Download citation
DOI: https://doi.org/10.1007/978-3-031-49614-1_20
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-49613-4
Online ISBN: 978-3-031-49614-1
eBook Packages: Computer ScienceComputer Science (R0)