TY - JOUR AU - Faliszewski, Piotr AU - Skowron, Piotr AU - Slinko, Arkadii AU - Szufa, Stanisław AU - Talmon, Nimrod PY - 2019/07/17 Y2 - 2024/03/29 TI - How Similar Are Two Elections? JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 33 IS - 01 SE - AAAI Technical Track: Game Theory and Economic Paradigms DO - 10.1609/aaai.v33i01.33011909 UR - https://ojs.aaai.org/index.php/AAAI/article/view/4017 SP - 1909-1916 AB - <p>We introduce the ELECTION ISOMORPHISM problem and a family of its approximate variants, which we refer to as <em>d</em>ISOMORPHISM DISTANCE (<em>d</em>-ID) problems (where <em>d</em> is a metric between preference orders). We show that ELECTION ISOMORPHISM is polynomial-time solvable, and that the <em>d</em>-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.</p> ER -