How Similar Are Two Elections?
P. Faliszewski, P. Skowron, A. Slinko, S. Szufa, N. Talmon
AAAI 2019
Abstract
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.
Experiments: