TL;DR
This paper introduces a mathematical programming framework to precisely map out fairness and sparsity tradeoffs within the "Rashomon set"—the collection of all models that perform nearly as well as the absolute optimal model. By using an enumeration-free approach based on the true 0/1 loss rather than convex approximations, the authors certifiably prove how strict interpretability (sparsity) constraints can restrict a model's fairness options or even mandate systemic bias.
What Problem Does This Paper Address?
When training a machine learning model, we usually look for the single model that maximizes accuracy. However, many distinct models can achieve virtually identical performance while making completely different predictions—a phenomenon known as predictive multiplicity. The set of all such well-performing models is called the $\epsilon$-Rashomon set.
Because these models perform equally well, developers have the freedom to choose one that satisfies other critical real-world criteria, such as fairness (not discriminating against protected groups) and sparsity (having fewer parameters or nodes to ensure human interpretability).
Existing methods to explore Rashomon sets suffer from two major flaws:
- Enumeration-based methods try to sample every single model in the set, which is computationally impossible for large hypothesis spaces.
- Enumeration-free methods avoid sampling but rely on convex upper bounds (like logistic or hinge loss) instead of the actual classification error (0/1 loss). This drastically underestimates the true size of the Rashomon set and hides the real tradeoffs available to practitioners.
Furthermore, no prior work has rigorously analyzed how enforcing strict sparsity constraints impacts the available fairness options within these sets.
Methods
The authors propose a generic, enumeration-free framework using Mixed-Integer Linear Programming (MILP). Instead of finding all good models, the framework directly solves for the fairest and least fair models possible within a given performance threshold ($\epsilon$) and sparsity budget ($\alpha$). Crucially, it optimizes these bounds using the true 0/1 loss.
The optimization problem is structured as follows:
- Objective: Minimize (or maximize) a target fairness metric, such as Statistical Parity or Equal Opportunity.
- Constraint 1: Stay within the $\epsilon$-Rashomon set (i.e., training loss must be within $\epsilon$ of the optimal model's loss).
- Constraint 2: Maintain a sparsity level $\le \alpha$ (e.g., limiting the number of non-zero coefficients or active decision nodes).
The authors instantiate this framework for two inherently interpretable model classes:
- Scoring Systems: Sparse linear models with integer coefficients (built on the SLIM framework).
- Decision Diagrams: A generalization of decision trees where branches can merge, preventing data fragmentation.
Datasets
The framework was evaluated on three standard fairness benchmarks:
- UCI Adult Income Dataset: Predicting whether an individual earns over \$50k/year (Sensitive attribute: Gender).
- Default of Credit Card Clients: Predicting credit card default (Sensitive attribute: Gender).
- COMPAS Dataset: Predicting criminal recidivism within two years (Sensitive attribute: Race).
Key Insights and Ideas
- Sparsity Strangles Fairness: Enforcing high sparsity (fewer features/rules) shrinks the hypothesis space, which severely narrows the range of achievable fairness. In some cases, forcing a model to be highly interpretable completely eliminates the possibility of finding a fair model.
- The Asymmetry of Bias: The bounds of the Rashomon set are rarely centered around zero bias. For certain datasets, every single high-performing model under a strict sparsity constraint exhibits a bias against the protected group.
- Hypothesis Complexity as a Fairness Enabler: Decision diagrams (which allow multivariate splits) yield a much wider range of fairness options than simpler scoring systems. Increased model complexity gives the optimization framework more "wiggle room" to find fair alternatives without sacrificing accuracy.
- More Data Can Lock In Bias: Counterintuitively, increasing the training set size ($N$) shrinks the Rashomon set. This means that if the underlying data contains systemic biases, a larger dataset can certifiably ensure that every accurate model inherits that bias, leaving no room for algorithmic mitigation.
Key Results
- UCI Adult Income: For scoring systems within a 20%-Rashomon set, tightening the sparsity constraint below $\alpha = 20$ coefficients systematically forced the minimum statistical parity to become positive, meaning females were inevitably disadvantaged under high sparsity.
- COMPAS Dataset: When restricting scoring systems to a very sparse configuration ($\alpha = 5$) within a 20%-Rashomon set, the minimum statistical parity was 18.7%. This certifiably proves that all accurate, highly sparse models on this dataset predict higher recidivism risks for African-Americans.
Limitations and Future Work
The primary limitation is computational complexity. Because the framework relies on exact MILP formulations with 0/1 loss, solving the optimization problem is NP-hard. While the authors successfully scaled their experiments to $N=4000$ using solver warm-starts, applying this directly to massive datasets or highly complex deep network architectures remains out of reach.
Future work includes extending this declarative framework to other interpretable hypothesis classes—such as rule-based models and tree ensembles—and integrating alternative metrics like counterfactual fairness or adversarial robustness.
Summary updated