Diversity of Structured Domains via k-Kemeny Scores
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_ | 1866914047181455360 |
|---|---|
| author | Faliszewski, Piotr Sornat, Krzysztof Szufa, Stanisław Wąs, Tomasz |
| author_facet | Faliszewski, Piotr Sornat, Krzysztof Szufa, Stanisław Wąs, Tomasz |
| contents | In the k-Kemeny problem, we are given an ordinal election, i.e., a collection of votes ranking the candidates from best to worst, and we seek the smallest number of swaps of adjacent candidates that ensure that the election has at most k different rankings. We study this problem for a number of structured domains, including the single-peaked, single-crossing, group-separable, and Euclidean ones. We obtain two kinds of results: (1) We show that k-Kemeny remains intractable under most of these domains, even for k=2, and (2) we use k-Kemeny to rank these domains in terms of their diversity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_15812 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Diversity of Structured Domains via k-Kemeny Scores Faliszewski, Piotr Sornat, Krzysztof Szufa, Stanisław Wąs, Tomasz Computer Science and Game Theory Artificial Intelligence Multiagent Systems In the k-Kemeny problem, we are given an ordinal election, i.e., a collection of votes ranking the candidates from best to worst, and we seek the smallest number of swaps of adjacent candidates that ensure that the election has at most k different rankings. We study this problem for a number of structured domains, including the single-peaked, single-crossing, group-separable, and Euclidean ones. We obtain two kinds of results: (1) We show that k-Kemeny remains intractable under most of these domains, even for k=2, and (2) we use k-Kemeny to rank these domains in terms of their diversity. |
| title | Diversity of Structured Domains via k-Kemeny Scores |
| topic | Computer Science and Game Theory Artificial Intelligence Multiagent Systems |
| url | https://arxiv.org/abs/2509.15812 |