Szczegóły publikacji
Opis bibliograficzny
The complexity of election problems with group-separable preferences / Piotr FALISZEWSKI, Alexander Karpov, Svetlana Obraztsova // Autonomous Agents and Multi-Agent Systems ; ISSN 1387-2532. — 2022 — vol. 36 iss. 1 art. no. 18, s. 1–28. — Bibliogr. s. 26–28, Abstr. — Publikacja dostępna online od: 2022-02-26
Autorzy (3)
- AGHFaliszewski Piotr
- Karpov Alexander
- Obraztsova Svetlana
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 139603 |
|---|---|
| Data dodania do BaDAP | 2022-03-24 |
| Tekst źródłowy | URL |
| DOI | 10.1007/s10458-022-09549-7 |
| Rok publikacji | 2022 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Autonomous Agents and Multi-Agent Systems |
Abstract
We analyze the complexity of several NP-hard election-related problems under the assumptions that the voters have group-separable preferences. We show that under this assumption our problems typically remain NP-hard, but we provide more efficient algorithms if additionally the clone decomposition tree is of moderate height. We also show a polynomial-time algorithm for sampling group-separable elections uniformly at random.
