The Complexity of Subelection Isomorphism Problems

P. Faliszewski, K. Sornat, S. Szufa
AAAI 2022
https://ojs.aaai.org/index.php/AAAI/article/view/20430
DOI: 10.1609/aaai.v36i5.20430
DBLP: conf/aaai/FaliszewskiSS22
arXiv: 2105.11923
Code link: https://github.com/Project-PRAGMA/Subelections
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.

Experiments:

Election type Culture Candidates Voters Instances Parameters
Ordinal Euclidean 1D {4, 7, 10} {50} 1000 Uniform 1D {[0,1]}
Ordinal Identity {4, 7, 10} {50} 1000 None
Ordinal Impartial Culture {4, 7, 10} {50} 1000 None
Ordinal Mallows {4, 7, 10} {50} 1000 $\phi \in \{0.33,0.67\}$
Ordinal Single-Peaked (Conitzer/Random Peak) {4, 7, 10} {50} 1000 None
Ordinal Single-Peaked (Walsh/Uniform) {4, 7, 10} {50} 1000 None
Ordinal Urn Model {4, 7, 10} {50} 1000 $\alpha \in \{0.1,0.5\}$
Ordinal Euclidean 1D {10} {5, 10, 15, 20, 25, 30, 35, 40, 45, 50} 1000 Uniform 1D {[0,1]}
Ordinal Euclidean 1D [3-10] {50} 1000 Uniform 1D {[0,1]}
Ordinal Identity {10} {5, 10, 15, 20, 25, 30, 35, 40, 45, 50} 1000 None
Ordinal Identity [3-10] {50} 1000 None
Ordinal Impartial Culture {10} {5, 10, 15, 20, 25, 30, 35, 40, 45, 50} 1000 None
Ordinal Impartial Culture [3-10] {50} 1000 None
Ordinal Mallows {10} {5, 10, 15, 20, 25, 30, 35, 40, 45, 50} 1000 $\phi \in \{0.5\}$
Ordinal Mallows [3-10] {50} 1000 $\phi \in \{0.5\}$
Ordinal Single-Peaked (Conitzer/Random Peak) {10} {5, 10, 15, 20, 25, 30, 35, 40, 45, 50} 1000 None
Ordinal Single-Peaked (Conitzer/Random Peak) [3-10] {50} 1000 None
Ordinal Single-Peaked (Walsh/Uniform) {10} {5, 10, 15, 20, 25, 30, 35, 40, 45, 50} 1000 None
Ordinal Single-Peaked (Walsh/Uniform) [3-10] {50} 1000 None