Szczegóły publikacji
Opis bibliograficzny
Detecting approximate clones under approval voting : extended abstract / Théo Delemazure, Piotr FALISZEWSKI, Łukasz JANECZKO, Dušan Knop, Kristýna PEKÁRKOVÁ, Jan Pokorný, Šimon SCHIERREICH, Ildikó Schlotter // W: AAMAS'2026 [Dokument elektroniczny] : proceedings of the 25th international conference on Autonomous Agents and Multiagent Systems : Paphos, Cyprus, May 25–29, 2026. — Wersja do Windows. — Dane tekstowe. — [USA] : International Foundation for Autonomous Agents and Multiagent Systems, cop. 2026. — e-ISBN: 979-8-4007-2317-9. — S. 3441–3443. — Wymagania systemowe: Adobe Reader. — Bibliogr. s. 3443, Abstr. — Publikacja dostępna online od: 2026-05-24
Autorzy (8)
- Delemazure Théo
- AGHFaliszewski Piotr
- AGHJaneczko Łukasz
- Knop Dušan
- AGHPekarkova Kristyna
- Pokorný Jan
- AGHSchierreich Šimon
- Schlotter Ildikó
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 168864 |
|---|---|
| Data dodania do BaDAP | 2026-08-28 |
| Tekst źródłowy | URL |
| DOI | 10.65109/MBRB4492 |
| Rok publikacji | 2026 |
| Typ publikacji | materiały konferencyjne (aut.) |
| Otwarty dostęp |  |
| Creative Commons | |
| Konferencja | International Joint Conference on Autonomous Agents and Multiagent Systems 2026 |
Abstract
In approval elections, two candidates are called perfect clones if they are approved by exactly the same set of voters. We propose a general framework for studying approximations of this notion, and demonstrate its power using two natural approximation measures with various appealing axiomatic properties. For both of these measures, we consider two fundamental tasks: deciding whether a large approximate clone set exists in a given election, and computing a partition of the candidate set into approximate clone sets. We show that both tasks are, in general, computationally intractable. To have a better understanding of the boundary between tractable and intractable instances, we analyze the parameterized complexity of these problems with respect to several parameters, including the number of voters and candidates, the approximation threshold, the number and size of partition parts, and structural properties of the instances, such as the number of approvals per voter or per candidate. Finally, we explore how our approximation measures behave in real-world approval elections.
