Core-stable committees under restricted domains. (English) Zbl 1533.91184
Hansen, Kristoffer Arnsfelt (ed.) et al., Web and internet economics. 18th international conference, WINE 2022, Troy, NY, USA, December 12–15, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13778, 311-329 (2022).
Summary: We study the setting of committee elections, where a group of individuals needs to collectively select a given-size subset of available objects. This model is relevant for a number of real-life scenarios including political elections, participatory budgeting, and facility-location. We focus on the core – the classic notion of proportionality, stability and fairness. We show that for a number of restricted domains including voter-interval, candidate-interval, single-peaked, and single-crossing preferences the core is non-empty and can be found in polynomial time. We show that the core might be empty for strict top-monotonic preferences, yet we introduce a relaxation of this class, which guarantees non-emptiness of the core. Our algorithms work both in the randomized and discrete models. We also show that the classic known proportional rules do not return committees from the core even for the most restrictive domains among those we consider (in particular for 1D-Euclidean preferences). We additionally prove a number of structural results that give better insights into the nature of some of the restricted domains, and which in particular give a better intuitive understanding of the class of top-monotonic preferences.
For the entire collection see [Zbl 1516.91002].
For the entire collection see [Zbl 1516.91002].
References:
| [1] | Aziz, H., Bogomolnaia, A., Moulin, H.: Fair mixing: the case of dichotomous preferences. In: EC-2019, pp. 753-781 (2019) |
| [2] | 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) · Zbl 1392.91030 · doi:10.1007/s00355-016-1019-3 |
| [3] | Aziz, H., Elkind, E., Faliszewski, P., Lackner, M., Skowron, P.: The Condorcet principle for multiwinner elections: from shortlisting to proportionality. In: IJCAI-2017, pp. 84-90, August 2017 |
| [4] | Aziz, H.; Lee, B., The expanding approvals rule: improving proportional representation and monotonicity, Soc. Choice Welfare, 54, 1, 1-45 (2020) · Zbl 1437.91176 · doi:10.1007/s00355-019-01208-3 |
| [5] | Barberà, S.; Moreno, B., Top monotonicity: a common root for single peakedness, single crossing and the median voter result, Games Econom. Behav., 73, 2, 345-359 (2011) · Zbl 1274.91173 · doi:10.1016/j.geb.2011.02.004 |
| [6] | Black, D., On the rationale of group decision-making, J. Polit. Econ., 56, 1, 23-34 (1948) · doi:10.1086/256633 |
| [7] | Brandt, F.: Rolling the dice: recent results in probabilistic social choice. In: Endriss, U. (ed.) Trends in Computational Social Choice, pp. 3-26. AI Access (2017) |
| [8] | Brill, M., Gölz, P., Peters, D., Schmidt-Kraepelin, U., Wilker, K.: Approval-based apportionment. In: AAAI-2020, pp. 1854-1861 (2020) |
| [9] | Burdges, J., et al.: Overview of Polkadot and its design considerations. arXiv preprint arXiv:2005.13456 (2020) |
| [10] | Cevallos, A., Stewart, A.: A verifiably secure and proportional committee election rule. arXiv preprint arXiv:2004.12990 (2020) |
| [11] | Chalkiadakis, G., Elkind, E., Wooldridge, M.: Computational aspects of cooperative game theory. In: Synthesis Lectures on Artificial Intelligence and Machine Learning, vol. 5, no. 6, pp. 1-168 (2011) · Zbl 1258.91005 |
| [12] | Cheng, Y., Jiang, Z., Munagala, K., Wang, K.: Group fairness in committee selection. In: EC-2019, pp. 263-279 (2019) |
| [13] | Dummett, M., Voting Procedures (1984), Oxford: Oxford University Press, Oxford |
| [14] | Elkind, E.; Faliszewski, P.; Skowron, P., A characterization of the single-peaked single-crossing domain, Soc. Choice Welfare, 54, 167-181 (2020) · Zbl 1437.91184 · doi:10.1007/s00355-019-01216-3 |
| [15] | Elkind, E.; Faliszewski, P.; Skowron, P.; Slinko, A., Properties of multiwinner voting rules, Soc. Choice Welfare, 48, 3, 599-632 (2017) · Zbl 1392.91032 · doi:10.1007/s00355-017-1026-z |
| [16] | Elkind, E., Lackner, M.: Structure in dichotomous preferences. In: IJCAI-2015, pp. 2019-2025 (2015) |
| [17] | Elkind, E., Lackner, M., Peters, D.: Structured preferences. In: Trends in Computational Social Choice, pp. 187-207 (2017) |
| [18] | Fain, B.; Goel, A.; Munagala, K.; Cai, Y.; Vetta, A., The core of the participatory budgeting problem, Web and Internet Economics, 384-399 (2016), Heidelberg: Springer, Heidelberg · Zbl 1406.91137 · doi:10.1007/978-3-662-54110-4_27 |
| [19] | Fain, B., Munagala, K., Shah, N.: Fair allocation of indivisible public goods. In: Proceedings of the 2018 ACM Conference on Economics and Computation, pp. 575-592 (2018). Extended version. arXiv:1805.03164 |
| [20] | 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, pp. 27-47. AI Access (2017) |
| [21] | Farahani, RZ; Hekmatfar, M., Facility Location: Concepts, Models, Algorithms and Case Studies (2009), Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-7908-2151-2 |
| [22] | Jiang, Z., Munagala, K., Wang, K.: Approximately stable committee selection. In: STOC-2020, pp. 463-472 (2020) · Zbl 07298262 |
| [23] | Lackner, M., Skowron, P.: Approval-based committee voting: axioms, algorithms, and applications. Technical report. arXiv:2007.01795 [cs.GT], arXiv.org (2020) · Zbl 1507.91076 |
| [24] | Magiera, K.; Faliszewski, P., Recognizing top-monotonic preference profiles in polynomial time, J. Artif. Intell. Res., 66, 57-84 (2019) · Zbl 1496.91046 · doi:10.1613/jair.1.11331 |
| [25] | Mirrlees, J., An exploration in the theory of optimal income taxation, Rev. Econ. Stud., 38, 175-208 (1971) · Zbl 0222.90028 · doi:10.2307/2296779 |
| [26] | Osborne, JM; Rubinstein, A., A Course in Game Theory (1994), Cambridge: The MIT Press, Cambridge · Zbl 1194.91003 |
| [27] | Peters, D., Skowron, P.: Proportionality and the limits of welfarism. In: EC-2020, pp. 793-794 (2020). Extended version. arXiv:1911.11747 |
| [28] | Pierczyński, G., Skowron, P.: Core-stable committees under restricted domains (2021). doi:10.48550/ARXIV.2108.01987. https://arxiv.org/abs/2108.01987 · Zbl 1533.91184 |
| [29] | Roberts, KWS, Voting over income tax schedules, J. Public Econ., 8, 3, 329-340 (1977) · doi:10.1016/0047-2727(77)90005-6 |
| [30] | Sánchez-Fernández, L., et al.: Proportional justified representation. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI-2017), pp. 670-676 (2017) |
| [31] | Skowron, P.; Faliszewski, P.; Lang, J., Finding a collective set of items: from proportional multirepresentation to group recommendation, Artif. Intell., 241, 191-216 (2016) · Zbl 1406.91135 · doi:10.1016/j.artint.2016.09.003 |
| [32] | Skowron, P., Lackner, M., Brill, M., Peters, D., Elkind, E.: Proportional rankings. In: IJCAI-2017, pp. 409-415 (2017) |
| [33] | Srinivasan, A.: Distributions on level-sets with applications to approximation algorithms. In: FOCS-2001, pp. 588-597 (2001) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
