TL;DR
When multiple machine learning models achieve nearly identical accuracy on a dataset (the Rashomon effect), picking one at random will rarely result in a fair model. By formalizing the largest possible Rashomon set through deviations from the Bayes-optimal classifier, this paper provides fast algorithms to find the fairest models, quantifies the arbitrariness of individual predictions, and proves that intentionally searching for fairness within the Rashomon set is essential.
What Problem Does This Paper Address?
In many machine learning applications, numerous distinct models achieve approximately equal predictive performance—a phenomenon known as model multiplicity or the Rashomon effect. Under legal doctrines like U.S. disparate impact law, model multiplicity presents a major opportunity: organizations can proactively search through equally performant models for Less Discriminatory Alternatives (LDAs).
However, foundational questions remain:
- Does selecting a model purely for accuracy yield a reasonably fair model by chance, or must one explicitly optimize for fairness?
- How does model multiplicity translate to individual arbitrariness (i.e., whether a person's prediction is unstable across equally good models)?
- How large is the Rashomon set, and how much predictive accuracy do models actually sacrifice?
Methods
The authors define the largest possible Rashomon set $R_N(\epsilon)$ across $N$ data points as the set of all binary classification decision vectors whose expected accuracy is within an allowable tolerance $\epsilon$ of the Bayes-optimal classifier $f_{\text{opt}}$. Every model is represented by a binary "flip vector" $\theta \in \{0, 1\}^N$, where $\theta_i = 1$ indicates a disagreement with $f_{\text{opt}}(x_i)$.
The paper introduces several methodological contributions:
- Fast Fairness Optimization ($O(N \log N)$):
- Statistical Parity (PPR): Casts disparity reduction as a 0-1 knapsack problem. Because individual flips only take two discrete efficiency values ($1/|A|$ and $1/|B|$), an incremental linear search over sorted weights yields the exact fairest model in $O(N \log N)$ time.
- Error Rate Disparities (FPR / TPR): Formulates an $O(N \log N)$ fractional knapsack relaxation that guarantees finding a model within $O(1/N)$ disparity of the global optimum.
- Uniform Gibbs Sampling: To study typical models in $R_N(\epsilon)$, the authors build an $O(N)$-per-step Gibbs sampler using exact conditional flip probabilities, circumventing the curse of dimensionality where naive rejection sampling fails.
- Large-Sample Asymptotics ($N \to \infty$): The authors derive closed-form asymptotic expressions for:
- The flip probability of an individual with weight $w = |2p_i - 1|$: $q(w) = \frac{1}{1 + \exp(C(\epsilon)w)}$.
- The size of the Rashomon set: $|R_N(\epsilon)| \approx B(\epsilon)^N$, where $B(\epsilon)$ is an exponential base derived analytically.
- Error budget saturation: A proof that as $N \to \infty$, the average model in $R_N(\epsilon)$ uses the entire error tolerance $\epsilon$.
Datasets
The authors evaluate their methods on three standard fairness benchmarks (no new datasets were introduced):
- German Credit ($N = 1,000$): Predicting loan risk; sensitive attribute is gender.
- Adult Income ($N = 46,443$): Predicting income $> \$50\text{k}$; sensitive attribute is sex.
- Heritage Health ($N = 184,308$): Predicting hospital admissions; sensitive attribute is age ($\ge 60$).
Bayes-optimal probabilities $p_i$ were estimated via 5-fold cross-validation using penalized logistic regression (and verified using XGBoost).
Key Insights and Ideas
- Intentionality is Required: Randomly selecting an accurate model almost never yields a fair model. The fairness gap between a randomly sampled model and an explicitly optimized model in the Rashomon set is vast.
- Error Budgets Get Maxed Out: As datasets grow large, typical models in the unconstrained Rashomon set do not sit near the optimal model; almost all of them consume the full error tolerance $\epsilon$.
- Arbitrariness Extends Beyond Boundary Cases: While individuals with probabilities near $0.5$ flip most frequently, larger $\epsilon$ tolerances cause individuals with confident predictions (e.g., $p_i = 0.1$ or $0.9$) to flip unpredictably.
- Fairness Optimization Can Distort Arbitrariness: Flips for underrepresented groups produce a larger drop in disparity per unit of error. Consequently, optimizing for group fairness can inadvertently subject minority groups to disproportionately higher rates of individual decision flips.
Key Results
- Disparity Eradication: On German Credit and Health, optimizing within the Rashomon set completely eliminated demographic disparity with less than a 0.5% drop in accuracy ($\epsilon < 0.005$). On Adult, disparity was erased at $\epsilon \approx 0.02$.
- High Flip Rates: At $\epsilon = 0.02$, randomly sampled models flipped 12% of individual predictions in German Credit, 7% in Adult, and 5% in Health.
- Exponential Set Explosion: For German Credit ($N = 1,000$), increasing $\epsilon$ from $0.005$ to $0.02$ increased the exponential base $B(\epsilon)$ from $1.16$ to $1.32$, driving Rashomon set size from $5 \times 10^{65}$ to $6 \times 10^{119}$.
- Restricted Model Classes: Unlike unconstrained flip vectors, restricted model classes (e.g., $L_2$-regularized logistic regression) only utilized a fraction of the error tolerance $\epsilon$ (~40% on German, 15% on Adult, 2% on Health).
Limitations and Future Work
- Unconstrained vs. Parametric Model Sets: The theoretical formulation allows any arbitrary input-to-output mapping. While these can be realized via randomized post-processing or threshold shifts, standard training methods (like SGD on deep networks) may explore restricted subspaces.
- Dependence on Bayes-Optimal Estimates: The framework assumes access to well-calibrated true posterior probabilities $p_i$. While experiments showed robustness across cross-validation splits and model families (logistic regression vs. XGBoost), small or discrete datasets may produce noisy estimates.
- Future Directions: Characterizing the size and geometry of Rashomon sets when explicitly restricted to specific model classes (e.g., decision trees, neural nets) remains an open challenge.