How Similar Are Two Elections?
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917225350299648 |
|---|---|
| author | Faliszewski, Piotr Skowron, Piotr Slinko, Arkadii Sornat, Krzysztof Szufa, Stanisław Talmon, Nimrod |
| author_facet | Faliszewski, Piotr Skowron, Piotr Slinko, Arkadii Sornat, Krzysztof Szufa, Stanisław Talmon, Nimrod |
| contents | We introduce and study isomorphic distances between ordinal
elections (with the same numbers of candidates and voters). The main
feature of these distances is that they are invariant to renaming
the candidates and voters, and two elections are at distance zero if
and only if they are isomorphic. Specifically, we consider
isomorphic extensions of distances between preference orders: Given
such a distance d, we extend it to distance d-ID between
elections by unifying candidate names and finding a matching between
the votes, so that the sum of the d-distances between the matched
votes is as small as possible.
We show that testing isomorphism of two elections can be done in
polynomial time so, in principle, such distances can be tractable.
Yet, we show that two very natural isomorphic distances are
NP-complete and hard to approximate. We attempt to rectify the
situation by showing FPT algorithms for several natural
parameterizations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_19716 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | How Similar Are Two Elections? Faliszewski, Piotr Skowron, Piotr Slinko, Arkadii Sornat, Krzysztof Szufa, Stanisław Talmon, Nimrod Computer Science and Game Theory We introduce and study isomorphic distances between ordinal elections (with the same numbers of candidates and voters). The main feature of these distances is that they are invariant to renaming the candidates and voters, and two elections are at distance zero if and only if they are isomorphic. Specifically, we consider isomorphic extensions of distances between preference orders: Given such a distance d, we extend it to distance d-ID between elections by unifying candidate names and finding a matching between the votes, so that the sum of the d-distances between the matched votes is as small as possible. We show that testing isomorphism of two elections can be done in polynomial time so, in principle, such distances can be tractable. Yet, we show that two very natural isomorphic distances are NP-complete and hard to approximate. We attempt to rectify the situation by showing FPT algorithms for several natural parameterizations. |
| title | How Similar Are Two Elections? |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2601.19716 |