Szczegóły publikacji
Opis bibliograficzny
Justifying groups in multiwinner approval voting / Edith Elkind, Piotr FALISZEWSKI, Ayumi Igarashi, Pasin Manurangsi, Ulrike Schmidt-Kraepelin, Warut Suksompong // W: Algorithmic Game Theory : 15th International Symposium, SAGT 2022, Colchester, UK, September 12–15, 2022 : proceedings / eds. Panagiotis Kanellopoulos, Maria Kyropoulou, Alexandros Voudouris. — Cham : Springer Nature Switzerland, cop. 2022. — (Lecture Notes in Computer Science ; ISSN 0302-9743 ; LNCS 13584. Advanced Research in Computing and Software Science). — ISBN: 978-3-031-15713-4; e-ISBN: 978-3-031-15714-1. — S. 472–489. — Bibliogr. s. 488–489, Abstr.
Autorzy (6)
- Elkind Edith
- AGHFaliszewski Piotr
- Igarashi Ayumi
- Manurangsi Pasin
- Schmidt-Kraepelin Ulrike
- Suksompong Warut
Dane bibliometryczne
| ID BaDAP | 142806 |
|---|---|
| Data dodania do BaDAP | 2022-10-26 |
| DOI | 10.1007/978-3-031-15714-1_27 |
| Rok publikacji | 2022 |
| Typ publikacji | materiały konferencyjne (aut.) |
| Otwarty dostęp |  |
| Wydawca | Springer |
| Konferencja | International Symposium on Algorithmic Game Theory 2022 |
| Czasopismo/seria | Lecture Notes in Computer Science |
Abstract
Justified representation (JR) is a standard notion of representation in multiwinner approval voting. Not only does a JR committee always exist, but previous work has also shown through experiments that the JR condition can typically be fulfilled by groups of fewer than k candidates, where k is the target size of the committee. In this paper, we study such groups—known as n/k-justifying groups—both theoretically and empirically. First, we show that under the impartial culture model, n/k-justifying groups of size less than k/2 are likely to exist, which implies that the number of JR committees is usually large. We then present efficient approximation algorithms that compute a small n/k-justifying group for any given instance, and a polynomial-time exact algorithm when the instance admits a tree representation. In addition, we demonstrate that small n/k-justifying groups can often be useful for obtaining a gender-balanced JR committee even though the problem is NP-hard.
