{"ID":2868746,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.15812","arxiv_id":"2509.15812","title":"Diversity of Structured Domains via k-Kemeny Scores","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.","short_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, incl...","url_abs":"https://arxiv.org/abs/2509.15812","url_pdf":"https://arxiv.org/pdf/2509.15812v1","authors":"[\"Piotr Faliszewski\",\"Krzysztof Sornat\",\"Stanisław Szufa\",\"Tomasz Wąs\"]","published":"2025-09-19T09:40:39Z","proceeding":"cs.GT","tasks":"[\"cs.GT\",\"cs.AI\",\"cs.MA\"]","methods":"[]","has_code":false}