Abstract
Selecting a set of alternatives based on the preferences of agents is an important problem in committee selection and beyond. Among the various criteria put forth for desirability of a committee, Pareto optimality is a minimal and important requirement. As asking agents to specify their preferences over exponentially many subsets of alternatives is practically infeasible, we assume that each agent specifies a weak order on single alternatives, from which a preference relation over subsets is derived using some preference extension. We consider five prominent extensions (responsive, downward lexicographic, upward lexicographic, best, and worst). For each of them, we consider the corresponding Pareto optimality notion, and we study the complexity of computing and verifying Pareto optimal outcomes. For each of the preference extensions, we give a complete characterization of the complexity of testing Pareto optimality when preferences are dichotomous or linear. We also consider strategic issues: for four of the set extensions, we present a linear-time, Pareto optimal and strategyproof algorithm that even works for weak preferences.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Notes
If there are exactly two candidates per seat, then designated voting is equivalent to multiple referenda, where a decision has to be taken on each of a series of yes-no issues.
References
Aziz, H., & Lee, B. E. (2020). The expanding approvals rule: Improving proportional representation and monotonicity. Social Choice and Welfare, 54, 1–45.
Aziz, H., & Savani, R. (2016). Hedonic games. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, & A. D. Procaccia (Eds.), Handbook of computational social choice, chapter 15. Cambridge: Cambridge University Press.
Aziz, H., Brandt, F., & Brill, M. (2013a). The computational complexity of random serial dictatorship. Economics Letters, 121(3), 341–345.
Aziz, H., Brandt, F., & Brill, M. (2013b) On the tradeoff between economic efficiency and strategyproofness in randomized social choice. In Proceedings of the 12th international conference on autonomous agents and multi-agent systems (AAMAS) (pp. 455–462). IFAAMAS.
Aziz, H., Lang, J., & Monnot, J. (2016). Computing pareto optimal committees. In Proceedings of the 25th international joint conference on artificial intelligence (IJCAI) (pp. 60–66).
Aziz, H., Elkind, E., Faliszewski, P., Lackner, M., & Skowron, P. (2017). The Condorcet principle for multiwinner elections: From shortlisting to proportionality. In Proceedings of the 26th international joint conference on artificial intelligence (IJCAI).
Aziz, H., Brandt, F., Elkind, E., & Skowron, P. (2018). Computational social choice: The first ten years and beyond. In B. Steffen & G. Woeginger (Eds.), Computing and software science, volume 10000 of Lecture notes in computer science (LNCS). Berlin: Springer.
Aziz, H., Biro, P., Lang, J., Lesca, J., & Monnot, J. (2019). Efficient reallocation under additive and ordinal preferences. Theoretical Computer Science, 790, 1–15.
Barberà, S., Bossert, W., & Pattanaik, P.K. (2004). Ranking sets of objects. In S. Barberà, P. J. Hammond, & C. Seidl (Eds.), Handbook of utility theory (Vol. II, chapter 17, pp. 893–977). Dordrecht: Kluwer Academic Publishers.
Benoît, J.-P., & Kornhauser, L. (2010). Only a dictatorship is efficient. Games and Economic Behavior, 70(2), 261–270.
Betzler, N., Slinko, A., & Uhlmann, J. (2013). On the computation of fully proportional representation. Journal of Artificial Intelligence Research, 47, 475–519.
Bossert, W. (1995). Preference extension rules for ranking sets of alternatives with a fixed cardinality. Theory and Decision, 39, 301–317.
Brams, S., Kilgour, D., & Sanver, R. (2007). A minimax procedure for electing committees. Public Choice, 3–4(132), 401–420.
Brandl, F. (2013). Efficiency and incentives in randomized social choice. Master���s thesis, Technische Universität München.
Brandt, F., & Brill, M. (2011). Necessary and sufficient conditions for the strategyproofness of irresolute social choice functions. In Proceedings of the 13th conference on theoretical aspects of rationality and knowledge (TARK) (pp. 136–142). ACM Press.
Caragiannis, I., Kalaitzis, D., & Markakis, E. (2010). Approximation algorithms and mechanism design for minimax approval voting. In Proceedings of the 24th AAAI conference on artificial intelligence (AAAI) (pp. 737–742).
Cechlárová, K. (2008). Stable partition problem. In M.-Y. Kao (Ed.), Encyclopedia of algorithms (pp. 885–888). Berlin: Springer.
Chamberlin, J. R., & Courant, P. N. (1983). Representative deliberations and representative decisions: proportional representation and the Borda rule. American Political Science Review, 77(3), 718–733.
Cho, W. J. (2016). Incentive properties for ordinal mechanisms. Games and Economic Behavior, 95, 168–177.
Cuhadaroǧlu, T., & Lainé, J. (2012). Pareto efficiency in multiple referendum. Theory and Decision, 72(4), 525–536.
Darmann, A. (2013). How hard is it to tell which is a condorcet committee? Mathematical Social Sciences, 66(3), 282–292. https://doi.org/10.1016/j.mathsocsci.2013.06.004.
de Keijzer, B., Bouveret, S., Klos, T., & Zhang, Y. (2009). On the complexity of efficiency and envy-freeness in fair division of indivisible goods with additive preferences. In Proceedings of the 1st international conference on algorithmic decision theory (pp. 98–110).
Elkind, E., & Ismaili, A. (2015) OWA-based extensions of the Chamberlin-Courant rule. In Proceedings of the 4th international conference on algorithmic decision theory (ADT) (pp. 486–502). Berlin: Springer.
Elkind, E., Faliszewski, P., Skowron, P., & Slinko, A. (2014). Properties of multiwinner voting rules. In Proceedings of the 13th international conference on autonomous agents and multi-agent systems (AAMAS) (pp. 53–60).
Elkind, E., Lang, J., & Saffidine, A. (2015). Condorcet winning sets. Social Choice and Welfare, 44(3), 493–517.
Faliszewski, P., Skowron, P., Slinko, A., & Talmon, N. (2016). Multiwinner analogues of the plurality rule: Axiomatic and algorithmic views. In Proceedings of the 28th AAAI conference on artificial intelligence (AAAI).
Faliszewski, P., Skowron, P., Slinko, A., & Talmon, N. (2017) Multiwinner voting: A new challenge for social choice theory. In U. Endriss (Ed.), Trends in computational social choice, chapter 2.
Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. New York: W.H. Freeman.
Klamler, C., Pferschy, U., & Ruzika, S. (2012). Committee selection under weight constraints. Mathematical Social Sciences, 64(1), 48–56.
Lang, J., Mengin, J., & Xia, L. (2012). Aggregating conditionally lexicographic preferences on multi-issue domains. In Proceedings of the international conference on principles and practice of constraint programming (pp. 973–987).
Lu, T., & Boutilier, C. (2011). Budgeted social choice: From consensus to personalized decision making. In Proceedings of the 22nd international joint conference on artificial intelligence (IJCAI) (pp. 280–286). AAAI Press.
Monroe, B. L. (1995). Fully proportional representation. The American Political Science Review, 89(4), 925–940.
Moulin, H. (2003). Fair division and collective welfare. Cambridge: The MIT Press.
Özkal-Sanver, İ., & Sanver, R. (2006). Ensuring Pareto-optimality by referendum voting. Social Choice and Welfare, 27, 211–219.
Peters, D. (2018). Proportionality and strategyproofness in multiwinner elections. In Proceedings of the 17th international conference on autonomous agents and multi-agent systems (AAMAS) (vol. 1549–1557).
Procaccia, A. D., Rosenschein, J. S., & Zohar, A. (2008). On the complexity of achieving proportional representation. Social Choice and Welfare, 30, 353–362.
Roth, A. E., & Sotomayor, M. A. O. (1990). Two-sided matching: A study in game theoretic modelling and analysis. Cambridge: Cambridge University Press.
Skowron, P., Faliszewski, P., & Slinko, A. (2015a). Achieving fully proportional representation: Approximability results. Artificial Intelligence, 222, 67–103.
Skowron, P. K., Faliszewski, P., & Lang, J. (2015b). Finding a collective set of items: From proportional multirepresentation to group recommendation. In Proceedings of the 23rd international joint conference on artificial intelligence (IJCAI) (pp. 2131–2137). AAAI Press
Acknowledgements
This is the extended version of the IJCAI conference paper [5]. We thank Jérôme Lang for useful comments and pointers to the literature. The authors thank Felix Brandt for useful pointers and comments. They also thank the reviewers of IJCAI 2016, COMSOC 2016, and the journal for useful comments. Aziz gratefully acknowledges the UNSW Scientia Fellowship and Defence Science and Technology (DST). Jérôme Monnot thanks the ANR project CoCoRICo-CoDec.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Aziz, H., Monnot, J. Computing and testing Pareto optimal committees. Auton Agent Multi-Agent Syst 34, 24 (2020). https://doi.org/10.1007/s10458-020-09445-y
Published:
DOI: https://doi.org/10.1007/s10458-020-09445-y