The Complexity of Subelection Isomorphism Problems
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
Authors
- Piotr Faliszewski (ORCID: https://orcid.org/0000-0002-0332-4364)
- Stanisław Szufa (ORCID: https://orcid.org/0000-0001-6301-6227)
- Krzysztof Sornat (ORCID: https://orcid.org/0000-0001-7450-4269)
Institutions
- Jagiellonian University (PL)
- Dalle Molle Institute for Artificial Intelligence Research (CH)
- Lamsade (FR)
- AGH University of Krakow (PL)
Publication Details
- Journal
- Journal of Artificial Intelligence Research
- Published
- 2024-08-10
- DOI
- https://doi.org/10.1613/jair.1.15550
- Citations
- 1
- Primary Topic
- Game Theory and Voting Systems
- Type
- article
- Field-Weighted Citation Impact
- 1.13