2026/03/14 by Piotr Faliszewski, Krzysztof Sornat, Stanisław Szufa +1 · 1 voice
Economics, Econometrics and Finance · Computer Science · #Game Theory and Voting Systems #Complexity and Algorithms in Graphs #Advanced Graph Theory Research
paper · pdf · doi:10.1609/aaai.v40i20.38733
openalex publication_date 2026/03/14 · openalex created_date 2026/03/18 · openalex updated_date 2026/07/29
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.