Diversity of Structured Domains via k-Kemeny Scores

Piotr Faliszewski; Krzysztof Sornat; Stanisław Szufa; Tomasz Wąs

AAAI 2026technical0 citations

Diversity of Structured Domains via k-Kemeny Scores

Piotr Faliszewski, Krzysztof Sornat, Stanisław Szufa, Tomasz Wąs

Abstract

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.

BibTeX

@inproceedings{aaai2026_diversityofstruc,
  title = {Diversity of Structured Domains via k-Kemeny Scores},
  author = {Piotr Faliszewski and Krzysztof Sornat and Stanisław Szufa and Tomasz Wąs},
  booktitle = {AAAI 2026},
  year = {2026}
}