Document Open Access Logo

Fault Tolerance in Euclidean Committee Selection

Authors Chinmay Sonar , Subhash Suri, Jie Xue

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.95.pdf
  • Filesize: 0.78 MB
  • 14 pages

Document Identifiers

Author Details

Chinmay Sonar
  • Department of Computer Science, University of California, Santa Barbara, CA, USA
Subhash Suri
  • Department of Computer Science, University of California, Santa Barbara, CA, USA
Jie Xue
  • Department of Computer Science, New York University, Shanghai, China

Cite AsGet BibTex

Chinmay Sonar, Subhash Suri, and Jie Xue. Fault Tolerance in Euclidean Committee Selection. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 95:1-95:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ESA.2023.95

Abstract

In the committee selection problem, the goal is to choose a subset of size k from a set of candidates C that collectively gives the best representation to a set of voters. We consider this problem in Euclidean d-space where each voter/candidate is a point and voters' preferences are implicitly represented by Euclidean distances to candidates. We explore fault-tolerance in committee selection and study the following three variants: (1) given a committee and a set of f failing candidates, find their optimal replacement; (2) compute the worst-case replacement score for a given committee under failure of f candidates; and (3) design a committee with the best replacement score under worst-case failures. The score of a committee is determined using the well-known (min-max) Chamberlin-Courant rule: minimize the maximum distance between any voter and its closest candidate in the committee. Our main results include the following: (1) in one dimension, all three problems can be solved in polynomial time; (2) in dimension d ≥ 2, all three problems are NP-hard; and (3) all three problems admit a constant-factor approximation in any fixed dimension, and the optimal committee problem has an FPT bicriterion approximation.

Subject Classification

ACM Subject Classification
  • Theory of computation → Randomness, geometry and discrete structures
Keywords
  • Multiwinner elections
  • Fault tolerance
  • Geometric Hitting Set
  • EPTAS

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Kenneth Arrow. Advances in the spatial theory of voting. Cambridge University Press, 1990. Google Scholar
  2. Nadja Betzler, Arkadii Slinko, and Johannes Uhlmann. On the computation of fully proportional representation. Journal of Artificial Intelligence Research, 47:475-519, 2013. Google Scholar
  3. Robert Bredereck, Piotr Faliszewski, Andrzej Kaczmarczyk, Rolf Niedermeier, Piotr Skowron, and Nimrod Talmon. Robustness among multiwinner voting rules. Artificial Intelligence, 290:103403, 2021. Google Scholar
  4. Robert Bredereck, Andrzej Kaczmarczyk, and Rolf Niedermeier. On coalitional manipulation for multiwinner elections: Shortlisting. Autonomous Agents and Multi-Agent Systems, 35(2):38, 2021. Google Scholar
  5. John R Chamberlin and Paul N Courant. Representative deliberations and representative decisions: Proportional representation and the borda rule. American Political Science Review, 77(3):718-733, 1983. Google Scholar
  6. Shiva Chaudhuri, Naveen Garg, and Ramamoorthi Ravi. The p-neighbor k-center problem. Information Processing Letters, 65(3):131-134, 1998. Google Scholar
  7. Otto A Davis, Melvin J Hinich, and Peter C Ordeshook. An expository development of a mathematical model of the electoral process. American political science review, 64(2):426-448, 1970. Google Scholar
  8. Edith Elkind, Piotr Faliszewski, Jean-François Laslier, Piotr Skowron, Arkadii Slinko, and Nimrod Talmon. What do multiwinner voting rules do? an experiment over the two-dimensional euclidean domain. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31 of AAAI'17, pages 494-501, 2017. Google Scholar
  9. Edith Elkind, Piotr Faliszewski, Piotr Skowron, and Arkadii Slinko. Properties of multiwinner voting rules. Social Choice and Welfare, 48(3):599-632, 2017. Google Scholar
  10. Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra, and Jörg Rothe. Llull and copeland voting computationally resist bribery and constructive control. J. Artif. Intell. Res., 35:275-341, 2009. URL: https://doi.org/10.1613/jair.2697.
  11. Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, and Nimrod Talmon. Multiwinner voting: A new challenge for social choice theory. Trends in computational social choice, 74(2017):27-47, 2017. Google Scholar
  12. Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, and Nimrod Talmon. Committee scoring rules: Axiomatic characterization and hierarchy. ACM Transactions on Economics and Computation (TEAC), 7(1):1-39, 2019. Google Scholar
  13. Eric J Friedman, Vasilis Gkatzelis, Christos-Alexandros Psomas, and Scott Shenker. Fair and efficient memory sharing: Confronting free riders. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1965-1972, July 2019. Google Scholar
  14. Ashish Goel, Anilesh K Krishnaswamy, Sukolsak Sakshuwong, and Tanja Aitamurto. Knapsack voting for participatory budgeting. ACM Transactions on Economics and Computation (TEAC), 7:1-27, 2019. Google Scholar
  15. Arnaud Grivet Sébert, Nicolas Maudet, Patrice Perny, and Paolo Viappiani. Preference aggregation in the generalised unavailable candidate model. In International Conference on Algorithmic Decision Theory, pages 35-50. Springer, 2021. Google Scholar
  16. Mohammadtaghi Hajiaghayi, Wei Hu, Jian Li, Shi Li, and Barna Saha. A constant factor approximation algorithm for fault-tolerant k-median. ACM Transactions on Algorithms (TALG), 12(3):1-19, 2016. Google Scholar
  17. Edith Hemaspaandra, Lane A Hemaspaandra, and Jörg Rothe. Anyone but him: The complexity of precluding an alternative. Artificial Intelligence, 171(5-6):255-285, 2007. Google Scholar
  18. Dorit S Hochbaum and Wolfgang Maass. Approximation schemes for covering and packing problems in image processing and VLSI. Journal of the ACM (JACM), pages 130-136, 1985. Google Scholar
  19. Samir Khuller, Robert Pless, and Yoram J Sussmann. Fault tolerant k-center problems. Theoretical Computer Science, 242(1-2):237-245, 2000. Google Scholar
  20. Sven Oliver Krumke. On a generalization of the p-center problem. Information processing letters, 56(2):67-71, 1995. Google Scholar
  21. Tyler Lu and Craig Boutilier. Budgeted social choice: From consensus to personalized decision making. In Twenty-Second International Joint Conference on Artificial Intelligence, pages 280-286, 2011. Google Scholar
  22. Tyler Lu and Craig E Boutilier. The unavailable candidate model: a decision-theoretic view of social choice. In Proceedings of the 11th ACM conference on Electronic commerce, pages 263-274, 2010. Google Scholar
  23. Sujaya Maiyya, Victor Zakhary, Divyakant Agrawal, and Amr El Abbadi. Database and distributed computing fundamentals for scalable, fault-tolerant, and consistent maintenance of blockchains. Proceedings of the VLDB Endowment, 11(12), 2018. Google Scholar
  24. Neeldhara Misra and Chinmay Sonar. Robustness radius for chamberlin-courant on restricted domains. In International Conference on Current Trends in Theory and Practice of Informatics, pages 341-353. Springer, 2019. Google Scholar
  25. Kamesh Munagala, Zeyu Shen, and Kangning Wang. Optimal algorithms for multiwinner elections and the chamberlin-courant rule. EC '21: Proceedings of the 22nd ACM Conference on Economics and Computation, pages 697-717, 2021. Google Scholar
  26. Piotr Skowron, Piotr Faliszewski, and Jérôme Lang. Finding a collective set of items: From proportional multirepresentation to group recommendation. Artificial Intelligence, 241:191-216, 2016. Google Scholar
  27. Piotr Skowron, Piotr Faliszewski, and Arkadii Slinko. Achieving fully proportional representation: Approximability results. Artificial Intelligence, 222:67-103, 2015. Google Scholar
  28. Chinmay Sonar, Palash Dey, and Neeldhara Misra. On the complexity of winner verification and candidate winner for multiwinner voting rules. In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence, pages 89-95, 2021. Google Scholar
  29. Chinmay Sonar, Subhash Suri, and Jie Xue. Multiwinner elections under minimax chamberlin-courant rule in euclidean space. In Lud De Raedt, editor, Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, pages 475-481. International Joint Conferences on Artificial Intelligence Organization, July 2022. Google Scholar
  30. Chaitanya Swamy and David B Shmoys. Fault-tolerant facility location. ACM Transactions on Algorithms (TALG), 4(4):1-27, 2008. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact