The Complexity of Subelection Isomorphism Problems

Authors

  • Piotr Faliszewski AGH University, Kraków, Poland
  • Krzysztof Sornat AGH University, Kraków, Poland
  • Stanisław Szufa AGH University, Kraków, Poland Jagiellonian University, Kraków, Poland

DOI:

https://doi.org/10.1609/aaai.v36i5.20430

Keywords:

Game Theory And Economic Paradigms (GTEP)

Abstract

We study extensions of the Election Isomorphism problem, focused on the existence of isomorphic subelections. Specifically, we propose the Subelection Isomorphism and the Maximum Common Subelection problems and study their computational complexity and approximability. Using our problems in experiments, we provide some insights into the nature of several statistical models of elections.
AAAI-22 Proceedings Cover

Downloads

Published

2022-06-28

How to Cite

Faliszewski, P., Sornat, K., & Szufa, S. (2022). The Complexity of Subelection Isomorphism Problems. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5), 4991-4998. https://doi.org/10.1609/aaai.v36i5.20430

Issue

Vol. 36 No. 5: AAAI-22 Technical Tracks 5

Section

AAAI Technical Track on Game Theory and Economic Paradigms