How Similar Are Two Elections?
How Similar Are Two Elections?
复制标题
两次选举有多相似？
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Nimrod Talmon
中科院分区：
文献类型：
--
作者：
Piotr Faliszewski;P. Skowron;A. Slinko;Stanislaw Szufa;Nimrod Talmon
我们介绍了选举同构问题及其一系列近似变体，我们将其称为同构距离（d-ID）问题（其中 d 是偏好顺序之间的度量）。我们证明了选举同构是多项式时间可解的，并且 d-同构距离问题概括了各种经典的等级聚合方法（例如 Kemeny 和 Litvak 的方法）。我们确定问题的复杂性（包括它们的不可近似性），并提供有关在实践中解决这些问题的能力的初步实验。
We introduce the ELECTION ISOMORPHISM problem and a family of its approximate variants, which we refer to as dISOMORPHISM DISTANCE (d-ID) problems (where d is a metric between preference orders). We show that ELECTION ISOMORPHISM is polynomial-time solvable, and that the d-ISOMORPHISM DISTANCE problems generalize various classic rank-aggregation methods (e.g., those of Kemeny and Litvak). We establish the complexity of our problems (including their inapproximability) and provide initial experiments regarding the ability to solve them in practice.