Reimagining Meaningful Model Multiplicity

Predictive model multiplicity is when multiple models in a hypothesis class $\mathcal{H}$ disagree on their predictions while having similar overall error to the risk minimizer h*. This has substantial implications for algorithmic fairness: if such multiplicity exists, then there may be a model competitive with the risk minimizer of the target hypothesis class which does substantially better in terms of target fairness metrics; some argue that searching for such a less discriminatory model is a legal duty. Standard approaches formalize this via search over a Rashomon set $\mathcal{R}(\mathcal{H})$ of models, but this search is computationally expensive and does not easily provide generalization guarantees. We propose a reframing to ``meaningful" model multiplicity that avoids both obstacles. Rather than asking how to find the most fair model in $\mathcal{R}(\mathcal{H})$, we ask whether any $h \in \mathcal{H}$ can outperform $h*$ on a target group $g$. We provide efficient ensembling techniques over models which witness such multiplicity which simultaneously will outperform $h*$ on all affected groups and with generalization guarantees. We further show that multiaccuracy with respect to $\mathcal{G} \times \mathcal{H}$---efficiently achievable via a polynomial number of oracle calls to $\mathcal{H}$---entirely precludes meaningful multiplicity. Finally, for constraint-based fairness metrics for classification tasks, we show that building a multicalibrated predictor for the label probability $\mathbb{E}[y \vert x]$ and then postprocessing it to satisfy the fairness guarantees will Pareto dominate any approach based on searching the Rashomon set of classifiers.