Szczegóły publikacji
Opis bibliograficzny
The price of justified representation / Edith Elkind, Piotr FALISZEWSKI, Ayumi Igarashi, Pasin Manurangsi, Ulrike Schmidt-Kraepelin, Warut Suksompong // ACM Transactions on Economics and Computation ; ISSN 2167-8375. — 2024 — vol. 12 no. 3 art. no. 11, s. 1–27. — Bibliogr. s. 25–27, Abstr. — Publikacja dostępna online od: 2024-09-06
Autorzy (6)
- Elkind Edith
- AGHFaliszewski Piotr
- Igarashi Ayumi
- Manurangsi Pasin
- Schmidt-Kraepelin Ulrike
- Suksompong Warut
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 157979 |
|---|---|
| Data dodania do BaDAP | 2025-03-10 |
| Tekst źródłowy | URL |
| DOI | 10.1145/3676953 |
| Rok publikacji | 2024 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Creative Commons | |
| Czasopismo/seria | ACM Transactions on Economics and Computation |
Abstract
In multiwinner approval voting, the goal is to select a k-member committee based on voters’ approval ballots. A well-studied concept of proportionality in this context is the justified representation (JR) axiom, which demands that no large cohesive group of voters remains unrepresented. However, the JR axiom may conflict with other desiderata, such as social welfare (the number of approvals obtained by committee members) or coverage (the number of voters who approve at least one committee member). In this article, we investigate the price of imposing the JR axiom (as well as the more demanding extended justified representation axiom) on social welfare and coverage. Our approach is twofold: We derive worst-case bounds on the loss of welfare/coverage caused by imposing JR and study the computational complexity of finding committees with high welfare that provide JR (obtaining hardness results, approximation algorithms, and an exact algorithm for one-dimensional preferences).
