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:

Election type Culture Candidates Voters Instances Parameters
Ordinal Euclidean 1D {6} [6-16] 100 Uniform 1D {[0,1]}
Ordinal Euclidean 2D {6} [6-16] 100 Uniform 2D Sphere {(0, 0), r=1}
Ordinal Impartial Culture {6} [6-16] 100 None