Identifying Imperfect Clones in Elections
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912585983459328 |
|---|---|
| author | Faliszewski, Piotr Janeczko, Lukasz Lisowski, Grzegorz Pekarkova, Kristyna Schlotter, Ildiko |
| author_facet | Faliszewski, Piotr Janeczko, Lukasz Lisowski, Grzegorz Pekarkova, Kristyna Schlotter, Ildiko |
| contents | A perfect clone in an ordinal election (i.e., an election where the voters rank the candidates in a strict linear order) is a set of candidates that each voter ranks consecutively. We consider different relaxations of this notion: independent or subelection clones are sets of candidates that only some of the voters recognize as a perfect clone, whereas approximate clones are sets of candidates such that every voter ranks their members close to each other, but not necessarily consecutively. We establish the complexity of identifying such imperfect clones, and of partitioning the candidates into families of imperfect clones. We also study the parameterized complexity of these problems with respect to a set of natural parameters such as the number of voters, the size or the number of imperfect clones we are searching for, or their level of imperfection. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_11261 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Identifying Imperfect Clones in Elections Faliszewski, Piotr Janeczko, Lukasz Lisowski, Grzegorz Pekarkova, Kristyna Schlotter, Ildiko Computer Science and Game Theory Multiagent Systems A perfect clone in an ordinal election (i.e., an election where the voters rank the candidates in a strict linear order) is a set of candidates that each voter ranks consecutively. We consider different relaxations of this notion: independent or subelection clones are sets of candidates that only some of the voters recognize as a perfect clone, whereas approximate clones are sets of candidates such that every voter ranks their members close to each other, but not necessarily consecutively. We establish the complexity of identifying such imperfect clones, and of partitioning the candidates into families of imperfect clones. We also study the parameterized complexity of these problems with respect to a set of natural parameters such as the number of voters, the size or the number of imperfect clones we are searching for, or their level of imperfection. |
| title | Identifying Imperfect Clones in Elections |
| topic | Computer Science and Game Theory Multiagent Systems |
| url | https://arxiv.org/abs/2509.11261 |