Fairness and Sparsity within Rashomon sets: Enumeration-Free Exploration and Characterization

Lucas Langlade, Julien Ferry, Gabriel Laberge, Thibaut Vidal

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:

  1. Enumeration-based methods try to sample every single model in the set, which is computationally impossible for large hypothesis spaces.
  2. 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:

  1. UCI Adult Income Dataset: Predicting whether an individual earns over \$50k/year (Sensitive attribute: Gender).
  2. Default of Credit Card Clients: Predicting credit card default (Sensitive attribute: Gender).
  3. 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.
Figure 1: Minimum statistical parity (SP) and equal opportunity (EO) achievable on the UCI Adult Income dataset, within a 20%-Rashomon set for scoring systems, as a function of the chosen sparsity value α. Negative values favour group G2 (females) over group G1 (males), for predicting a high salary. We display both average value and standard deviation.
  • 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

Abstract

We introduce an enumeration-free method based on mathematical programming to precisely characterize various properties such as fairness or sparsity within the set of "good models", known as Rashomon set. This approach is generically applicable to any hypothesis class, provided that a mathematical formulation of the model learning task exists. It offers a structured framework to define the notion of business necessity and evaluate how fairness can be improved or degraded towards a specific protected group, while remaining within the Rashomon set and maintaining any desired sparsity level. We apply our approach to two hypothesis classes: scoring systems and decision diagrams, leveraging recent mathematical programming formulations for training such models. As seen in our experiments, the method comprehensively and certifiably quantifies trade-offs between predictive performance, sparsity, and fairness. We observe that a wide range of fairness values are attainable, ranging from highly favorable to significantly unfavorable for a protected group, while staying within less than 1% of the best possible training accuracy for the hypothesis class. Additionally, we observe that sparsity constraints limit these trade-offs and may disproportionately harm specific subgroups. As we evidenced, thoroughly characterizing the tensions between these key aspects is critical for an informed and accountable selection of models.
BibTeX
@inproceedings{langlade2025fairness,
  author = {Lucas Langlade and Julien Ferry and Gabriel Laberge and Thibaut Vidal},
  title = {{Fairness and Sparsity within Rashomon sets: Enumeration-Free Exploration and Characterization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aies.v8i2.36653},
}
Figure