Skip to main content
SpringerLink
Log in

Computing and testing Pareto optimal committees

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

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.

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

Fig. 1
Fig. 2

Similar content being viewed by others

Notes

  1. 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

  1. Aziz, H., & Lee, B. E. (2020). The expanding approvals rule: Improving proportional representation and monotonicity. Social Choice and Welfare, 54, 1–45.

    Article  MathSciNet  Google Scholar 

  2. 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.

  3. Aziz, H., Brandt, F., & Brill, M. (2013a). The computational complexity of random serial dictatorship. Economics Letters, 121(3), 341–345.

    Article  MathSciNet  Google Scholar 

  4. 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.

  5. 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).

  6. 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).

  7. 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.

  8. Aziz, H., Biro, P., Lang, J., Lesca, J., & Monnot, J. (2019). Efficient reallocation under additive and ordinal preferences. Theoretical Computer Science, 790, 1–15.

    Article  MathSciNet  Google Scholar 

  9. 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.

  10. Benoît, J.-P., & Kornhauser, L. (2010). Only a dictatorship is efficient. Games and Economic Behavior, 70(2), 261–270.

    Article  MathSciNet  Google Scholar 

  11. Betzler, N., Slinko, A., & Uhlmann, J. (2013). On the computation of fully proportional representation. Journal of Artificial Intelligence Research, 47, 475–519.

    Article  MathSciNet  Google Scholar 

  12. Bossert, W. (1995). Preference extension rules for ranking sets of alternatives with a fixed cardinality. Theory and Decision, 39, 301–317.

    Article  MathSciNet  Google Scholar 

  13. Brams, S., Kilgour, D., & Sanver, R. (2007). A minimax procedure for electing committees. Public Choice, 3–4(132), 401–420.

    Article  Google Scholar 

  14. Brandl, F. (2013). Efficiency and incentives in randomized social choice. Master’s thesis, Technische Universität München.

  15. 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.

  16. 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).

  17. Cechlárová, K. (2008). Stable partition problem. In M.-Y. Kao (Ed.), Encyclopedia of algorithms (pp. 885–888). Berlin: Springer.

    Chapter  Google Scholar 

  18. 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.

    Article  Google Scholar 

  19. Cho, W. J. (2016). Incentive properties for ordinal mechanisms. Games and Economic Behavior, 95, 168–177.

    Article  MathSciNet  Google Scholar 

  20. Cuhadaroǧlu, T., & Lainé, J. (2012). Pareto efficiency in multiple referendum. Theory and Decision, 72(4), 525–536.

    Article  MathSciNet  Google Scholar 

  21. 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.

    Article  MathSciNet  MATH  Google Scholar 

  22. 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).

  23. 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.

  24. 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).

  25. Elkind, E., Lang, J., & Saffidine, A. (2015). Condorcet winning sets. Social Choice and Welfare, 44(3), 493–517.

    Article  MathSciNet  Google Scholar 

  26. 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).

  27. 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.

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

    MATH  Google Scholar 

  29. Klamler, C., Pferschy, U., & Ruzika, S. (2012). Committee selection under weight constraints. Mathematical Social Sciences, 64(1), 48–56.

    Article  MathSciNet  Google Scholar 

  30. 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).

  31. 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.

  32. Monroe, B. L. (1995). Fully proportional representation. The American Political Science Review, 89(4), 925–940.

    Article  Google Scholar 

  33. Moulin, H. (2003). Fair division and collective welfare. Cambridge: The MIT Press.

    Book  Google Scholar 

  34. Özkal-Sanver, İ., & Sanver, R. (2006). Ensuring Pareto-optimality by referendum voting. Social Choice and Welfare, 27, 211–219.

    Article  Google Scholar 

  35. 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).

  36. Procaccia, A. D., Rosenschein, J. S., & Zohar, A. (2008). On the complexity of achieving proportional representation. Social Choice and Welfare, 30, 353–362.

    Article  MathSciNet  Google Scholar 

  37. Roth, A. E., & Sotomayor, M. A. O. (1990). Two-sided matching: A study in game theoretic modelling and analysis. Cambridge: Cambridge University Press.

    Book  Google Scholar 

  38. Skowron, P., Faliszewski, P., & Slinko, A. (2015a). Achieving fully proportional representation: Approximability results. Artificial Intelligence, 222, 67–103.

    Article  MathSciNet  Google Scholar 

  39. 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

Download references

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

  1. UNSW Sydney and Data61 CSIRO, Sydney, 2052, Australia

    Haris Aziz

  2. LAMSADE, Université Paris-Dauphine, Paris, France

    Jérôme Monnot

Authors
  1. Haris Aziz
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jérôme Monnot
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Haris Aziz.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Published:

  • DOI: https://doi.org/10.1007/s10458-020-09445-y

Keywords

JEL Classification

Search

Navigation