  The ``impossibility theorem'' -- which is considered foundational in
algorithmic fairness literature -- asserts that there must be trade-offs
between common notions of fairness and performance when fitting statistical
models, except in two special cases: when the prevalence of the outcome being
predicted is equal across groups, or when a perfectly accurate predictor is
used. However, theory does not always translate to practice. In this work, we
challenge the implications of the impossibility theorem in practical settings.
First, we show analytically that, by slightly relaxing the impossibility
theorem (to accommodate a \textit{practitioner's} perspective of fairness), it
becomes possible to identify a large set of models that satisfy seemingly
incompatible fairness constraints. Second, we demonstrate the existence of
these models through extensive experiments on five real-world datasets. We
conclude by offering tools and guidance for practitioners to understand when --
and to what degree -- fairness along multiple criteria can be achieved. For
example, if one allows only a small margin-of-error between metrics, there
exists a large set of models simultaneously satisfying \emph{False Negative
Rate Parity}, \emph{False Positive Rate Parity}, and \emph{Positive Predictive
Value Parity}, even when there is a moderate prevalence difference between
groups. This work has an important implication for the community: achieving
fairness along multiple metrics for multiple groups (and their intersections)
is much more possible than was previously believed.
