On the Complexity of Candidates-Embedded Multiwinner Voting under the Hausdorff Function
Pages 2567 - 2569
Abstract
We study candidates-embedded approval-based multiwinner voting. In this model, we are given a metric ƒ on the set of candidates, and voters are free to approve or disapprove any candidates. The task is to select a k-committee that either minimizes the sum of distances from the committee to all votes (utilitarian rules) or minimizes the maximum distance from the committee to any vote (egalitarian rules). The distance from a committee to a vote is measured by certain set-to-set functions derived from ƒ. Previous works have considered the min, the max, and the sum functions. This paper examines the Hausdorff function. We show that in general computing winners under the Hausdorff function is hard, but we also derive several polynomial-time algorithms for certain special cases.
References
[1]
P. K. Agarwal, S. Har-Peled, M. Sharir, and Y. Wang. 2010. Hausdorff Distance under Translation for Points and Balls. ACM Trans. Algorithms, Vol. 6, 4 (2010), 71:1--71:26. https://doi.org/10.1145/1824777.1824791
[2]
S. G. Aksoy, K. E. Nowak, E. Purvine, and S. J. Young. 2019. Relative Hausdorff Distance for Network Analysis. Appl. Netw. Sci., Vol. 4, 1 (2019), 80:1--80:25. https://doi.org/10.1007/s41109-019-0198-0
[3]
H. Aziz, E. Elkind, S. Huang, M. Lackner, L. Sá nchez-Ferná ndez, and P. Skowron. 2018. On the Complexity of Extended and Proportional Justified Representation. In AAAI. 902--909. https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/17279
[4]
J. S. Banks and J. Duggan. 2008. A Dynamic Model of Democratic Elections in Multidimensional Policy Spaces. Q. J. Polit. Sci., Vol. 3, 3 (2008), 269--299.
[5]
N. Betzler, A. Slinko, and J. Uhlmann. 2013. On the Computation of Fully Proportional Representation. J. Artif. Intell. Res., Vol. 47 (2013), 475--519. https://doi.org/10.1613/jair.3896
[6]
F. Brandl and F. Brandt. 2019. Arrovian Aggregation of Convex Preferences. Econometrica, Vol. 88, 2 (2019), 799--844.
[7]
M. Brill, P. Gölz, D. Peters, U. Schmidt-Kraepelin, and K. Wilker. 2020. Approval-Based Apportionment. In AAAI. 1854--1861.
[8]
B. B. Chaudhuri and A. Rosenfeld. 1999. A Modified Hausdorff Distance Between Fuzzy Sets. Inf. Sci., Vol. 118, 1--4 (1999), 159--171. https://doi.org/10.1016/S0020-0255(99)00037--7
[9]
V. D'Hondt. 1878. Question électorale: La représentation proportionnelle des partis. Bruxelles.
[10]
E. Elkind and M. Lackner. 2015. Structure in Dichotomous Preferences. In IJCAI. 2019--2025. http://ijcai.org/Abstract/15/286
[11]
E. Elkind, M. Lackner, and D. Peters. 2022. Preference Restrictions in Computational Social Choice: A Survey. CoRR, Vol. abs/2205.09092 (2022). https://doi.org/10.48550/arXiv.2205.09092 showeprint[arXiv]2205.09092
[12]
T. Erber and M. J. Frank. 2019. Arrow, Hausdorff, and Ambiguities in the Choice of Preferred States in Complex System. J. Interdiscip. Math., Vol. 22, 2 (2019), 129--137.
[13]
G. Gawron and P. Faliszewski. 2019. Robustness of Approval-Based Multiwinner Voting Rules. In ADT. 17--31. https://doi.org/10.1007/978-3-030-31489-7_2
[14]
F. Hausdorff. 2014. Grundzuege der Mengenlehre. Viet, Leipzig.
[15]
D. P. Huttenlocher, G. A. Klanderman, and W. Rucklidge. 1993. Comparing Images Using the Hausdorff Distance. IEEE Trans. Pattern Anal. Mach. Intell., Vol. 15, 9 (1993), 850--863. https://doi.org/10.1109/34.232073
[16]
R. Izsak, N. Talmon, and G. J. Woeginger. 2018. Committee Selection with Intraclass and Interclass Synergies. In AAAI. 1071--1078. https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/17312
[17]
O. Jesorsky, K. J. Kirchberg, and R. Frischholz. 2001. Robust Face Detection Using the Hausdorff Distance. In AVBPA. 90--95. https://doi.org/10.1007/3-540-45344-X_14
[18]
M. Lackner and P. Skowron. 2023. Multi-Winner Voting with Approval Preferences. Springer. https://doi.org/10.1007/978-3-031-09016-5
[19]
F. Mémoli. 2012. Some Properties of Gromov-Hausdorff Distances. Discret. Comput. Geom., Vol. 48, 2 (2012), 416--440. https://doi.org/10.1007/s00454-012-9406-8
[20]
D. Peters. 2018. Single-Peakedness and Total Unimodularity: New Polynomial-Time Algorithms for Multi-winner Elections. In AAAI. 1169--1176.
[21]
E. Phragmén. 1894. Sur une méthode nouvelle pour réaliser, dans les élections, la représentation proportionnelle des partis. Öfversigt af Kongliga Vetenskaps Akademiens Förhandlingar, Vol. 51, 3 ( 1894), 133--137.
[22]
G. Pierczynski and P. Skowron. 2019. Approval-Based Elections and Distortion of Voting Rules. In IJCAI. 543--549. https://doi.org/10.24963/ijcai.2019/77
[23]
D. Pompeiu. 1905. Sur la Continuité des Fonctions de Variables Complexes (Thèse). Ann. Fac. Sci. de Toulouse, Vol. 7 (1905), 264--315.
[24]
T. N. Thiele. 1895. Om Flerfoldsvalg. Oversigt over det Kongelige Danske Videnskabernes Selskabs Forhandlinger (1895), 415--441.
[25]
J.-Q. Wang, J.-T. Wu, J. Wang, H.-Y. Zhang, and X-H. Chen. 2016. Multi-Criteria Decision-Making Methods Based on the Hausdorff Distance of Hesitant Fuzzy Linguistic Numbers. Soft Comput., Vol. 20, 4 (2016), 1621--1633. https://doi.org/10.1007/s00500-015-1609-5
[26]
Y. Yang. 2019. Complexity of Manipulating and Controlling Approval-Based Multiwinner Voting. In IJCAI. 637--643. https://doi.org/10.24963/ijcai.2019/90
[27]
Y. Yang. 2022. On the Complexity of Calculating Approval-Based Winners in Candidates-Embedded Metrics. In IJCAI. 585--591. https://doi.org/10.24963/ijcai.2022/83
[28]
Y. Yang and J. Wang. 2018. Multiwinner Voting with Restricted Admissible Sets: Complexity and Strategyproofness. In IJCAI. 576--582. https://doi.org/10.24963/ijcai.2018/80
Index Terms
- On the Complexity of Candidates-Embedded Multiwinner Voting under the Hausdorff Function
Recommendations
Parameterized complexity of multiwinner determination: more effort towards fixed-parameter tractability
AbstractWe study the parameterized complexity of winner determination problems for three prevalent k-committee selection rules, namely the minimax approval voting (MAV), the proportional approval voting (PAV), and the Chamberlin–Courant’s approval voting (...
Bounded Approval Ballots: Balancing Expressiveness and Simplicity for Multiwinner Elections
AAMAS '23: Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent SystemsApproval ballots have been celebrated for many voting scenarios [16], in particular because of the low cognitive burden they put on the voters. This however, comes at the cost of expressiveness that can be problematic when voters have sophisticated ...
Robustness of Approval-Based Multiwinner Voting Rules
Algorithmic Decision TheoryAbstractWe investigate how robust are approval-based multiwinner voting rules to small perturbations of the preference profiles. In particular, we consider the extent to which a committee can change after we add/remove/swap one approval, and we consider ...
Comments
Information & Contributors
Information
Published In
May 2024
2898 pages
ISBN:9798400704864
- General Chairs:
- Mehdi Dastani,
- Jaime Simão Sichman,
- Program Chairs:
- Natasha Alechina,
- Virginia Dignum
Sponsors
Publisher
International Foundation for Autonomous Agents and Multiagent Systems
Richland, SC
Publication History
Published: 06 May 2024
Check for updates
Author Tags
Qualifiers
- Extended-abstract
Conference
AAMAS '23
Sponsor:
AAMAS '23: International Conference on Autonomous Agents and Multiagent Systems
May 6 - 10, 2024
Auckland, New Zealand
Acceptance Rates
Overall Acceptance Rate 1,155 of 5,036 submissions, 23%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 10Total Downloads
- Downloads (Last 12 months)10
- Downloads (Last 6 weeks)1
Reflects downloads up to 22 Sep 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in