How Similar Are Two Elections?

  • Piotr Faliszewski AGH Krakow
  • Piotr Skowron University of Warsaw
  • Arkadii Slinko University of Auckland
  • Stanisław Szufa Jagiellonian University
  • Nimrod Talmon Ben-Gurion University University

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.

Published
2019-07-17
Section
AAAI Technical Track: Game Theory and Economic Paradigms