Abstract Minimal majority-vote ensembles are attractive for interpretability, yet minimality can induce solution multiplicity and instability. We study stability and robustness of minimal majority-vote ensembles of decision stumps. We define three complementary metrics: multiplicity rate, bootstrap stability (mean pairwise Jaccard similarity of minimal solutions), and feature-flip robustness. We introduce reproducible stability/robustness metrics for minimal ensembles and evaluate them on synthetic benchmarks (binary d=8 –10, n=10 –500) together with a curated binarized UCI suite. MILP-based solvers confirm that the observed stability/robustness trends persist at larger samples (n up to 500). Minimal solutions consistently fit the data yet exhibit low bootstrap stability and high multiplicity in low-sample regimes, while robustness degrades gradually with feature noise. On real datasets and broader UCI pilots, minimal ensembles remain accurate but are sensitive to perturbations unless stability is explicitly considered. Our study highlights the practical importance of reporting stability alongside size for interpretable models. Revision analyses add bootstrap-size sensitivity (B=5, 20, 50), randomized tie-breaking over multiple minima, label-noise sweeps (5–10%), and candidate-cap checks for conjunction pools; these confirm that minimality-only selection can yield brittle explanations in high-stakes settings.
Li et al. (Tue,) studied this question.