How Similar Are Two Elections?

Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, Stanislaw Szufa, Nimrod Talmon

AAAI 2019 pp. 1909-1916

doi:10.1609/AAAI.V33I01.33011909 /aaai/2019/faliszewski2019aaai-similar/

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.

PDF AAAI Semantic Scholar

Cite

Text

Faliszewski et al. "How Similar Are Two Elections?." AAAI Conference on Artificial Intelligence, 2019. doi:10.1609/AAAI.V33I01.33011909

Markdown

[Faliszewski et al. "How Similar Are Two Elections?." AAAI Conference on Artificial Intelligence, 2019.](https://mlanthology.org/aaai/2019/faliszewski2019aaai-similar/) doi:10.1609/AAAI.V33I01.33011909

BibTeX

@inproceedings{faliszewski2019aaai-similar,
  title     = {{How Similar Are Two Elections?}},
  author    = {Faliszewski, Piotr and Skowron, Piotr and Slinko, Arkadii and Szufa, Stanislaw and Talmon, Nimrod},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2019},
  pages     = {1909-1916},
  doi       = {10.1609/AAAI.V33I01.33011909},
  url       = {https://mlanthology.org/aaai/2019/faliszewski2019aaai-similar/}
}