Szczegóły publikacji
Opis bibliograficzny
Ties in multiwinner approval voting / Łukasz JANECZKO, Piotr FALISZEWSKI // W: IJCAI-23 [Dokument elektroniczny] : proceedings of the thirty-second International Joint Conference on Artificial Intelligence : Macao, SAR, 19-25 August 2023 / ed. by Edith Elkind. — Wersja do Windows. — Dane tekstowe. — Darmstadt : International Joint Conferences on Artificial Intelligence, cop. 2023. — (Proceedings of the International Joint Conference on Artificial Intelligence ; ISSN 1045-0823). — e-ISBN: 978-1-956792-03-4. — S. 2765-2773. — Wymagania systemowe: Adobe Reader. — Bibliogr. s. 2772-2773, Abstr.
Autorzy (2)
Słowa kluczowe
Dane bibliometryczne
ID BaDAP | 148591 |
---|---|
Data dodania do BaDAP | 2023-09-27 |
Tekst źródłowy | URL |
DOI | 10.24963/ijcai.2023/308 |
Rok publikacji | 2023 |
Typ publikacji | materiały konferencyjne (aut.) |
Otwarty dostęp | |
Konferencja | Thirty-Second International Joint Conference on Artificial Intelligence |
Czasopismo/seria | Proceedings of the International Joint Conference on Artificial Intelligence |
Abstract
We study the complexity of deciding if there is a tie in a given approval-based multiwinner election, as well as the complexity of counting tied winning committees. We consider a family of Thiele rules, their greedy variants, Phragmen's sequential rule, and Method of Equal Shares. For most cases, our problems are computationally hard, but for sequential rules we find an FPT algorithm for discovering ties (parameterized by the committee size). We also show experimentally that in elections of moderate size ties are quite frequent.