Szczegóły publikacji
Opis bibliograficzny
Algorithms for structured elections under Thiele voting rules / Alexandra Lassota, Krzysztof SORNAT // W: AAAI-26 [Dokument elektroniczny] : proceedings of the 40th annual AAAI conference on Artificial Intelligence : thirty-eighth conference on Innovative Applications of Artificial Intelligence : sixteenth symposium on Educational Advances in Artificial Intelligence : January 20-27, 2026, Singapore / eds. Sven Koenig, Chad Jenkins, Matthew E. Taylor ; Association for the Advancement of Artificial Intelligence. — Wersja do Windows. — Dane tekstowe. — Washington, DC, USA : AAAI Press, cop. 2026. — ( Proceedings of the ... AAAI Conference on Artificial Intelligence ; ISSN 2159-5399 ). — e-ISBN: 978-1-57735-906-7; e-ISBN: 1-57735-906-2. — S. 17084–17092. — Wymagania systemowe: Adobe Reader. — Bibliogr. s. 17091–17092, Abstr. — Publikacja dostępna online od: 2026-03-14
Autorzy (2)
- Lassota Alexandra
- AGHSornat Krzysztof
Dane bibliometryczne
| ID BaDAP | 168974 |
|---|---|
| Data dodania do BaDAP | 2026-09-01 |
| Tekst źródłowy | URL |
| DOI | 10.1609/aaai.v40i20.38757 |
| Rok publikacji | 2026 |
| Typ publikacji | materiały konferencyjne (aut.) |
| Otwarty dostęp |  |
| Konferencja | National Conference of the American Association for Artificial Intelligence 2026 |
| Czasopismo/seria | Proceedings of the ... AAAI Conference on Artificial Intelligence |
Abstract
We study the computational complexity of winner determination problems in approval-based committee elections under Thiele voting rules. These form a class of rules parameterized by a fixed weight vector that specifies how a voter's satisfaction depends on the number of approved candidates elected. We first analyze the structure of optimal solutions based on the sets of voters who approve each candidate—that is, how voters' approval ballots induce dependencies between candidates—revealing constraints on a winning committee under any fixed Thiele voting rule. Using this, we design FPT algorithms for Proportional Approval Voting (PAV) and other Thiele rules on a natural restricted domain known as the Voter Interval domain—that is, after a suitable ordering of voters, each candidate is approved by a consecutive interval of voters. In particular, we show that every Thiele rule on Voter Interval is FPT with respect to a parameter for which the problem is NP-hard on general instances, even when the parameter takes constant values. Our results advance the understanding of the computational complexity of PAV on Voter Interval instances, which remains one of the central open questions in this area. We further resolve two open questions from the literature on PAV (and other Thiele voting rules) by providing a polynomial-time algorithm for instances where each candidate is approved by at most two voters, and an FPT algorithm parameterized by the total score of a winning committee.
