用相邻交换次数衡量选举规则的多样性，发现多数结构域仍难解。
Diversity of Structured Domains via k-Kemeny Scores
- 通过相邻交换最小化不同排名数，定义结构域多样性度量
- 即使k=2，单峰、单交叉等域仍属计算难解
- 首次量化比较多种选举结构域的复杂性差异
在k-Kemeny问题中，给定一个序数选举（即一组对候选人从优到劣排序的选票），目标是找到最少的相邻候选人交换次数，使得选举中最多只有k种不同的排名。本文研究了单峰、单交叉、组可分及欧氏等若干结构化选举域下的该问题。得到两类结果：(1) 在大多数此类结构域中，即使k=2，k-Kemeny问题依然难以求解；(2) 利用k-Kemeny作为工具，对这些结构域的多样性进行排序与比较。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。