Intersectional Fairness via Mixed-Integer Optimization

Jiří Němeček; Mark Kozdoba; Illia Kryvoviaz; Tomáš Pevný; Jakub Mareček

cs.LGJan 27, 2026

Intersectional Fairness via Mixed-Integer Optimization

Authors: Jiří Němeček, Mark Kozdoba, Illia Kryvoviaz, Tomáš Pevný, Jakub Mareček

Organizations: Czech Technical University in Prague · Technion

Abstract

The deployment of Artificial Intelligence in high-risk domains, such as finance and healthcare, necessitates models that are both fair and transparent. While regulatory frameworks, including the EU's AI Act, mandate bias mitigation, they are deliberately vague about the definition of bias. In line with existing research, we argue that true fairness requires addressing bias at the intersections of protected groups. We propose a unified framework that leverages Mixed-Integer Optimization (MIO) to train intersectionally fair and intrinsically interpretable classifiers. We prove the equivalence of two measures of intersectional fairness (MSD and SPSF) in detecting the most unfair subgroup and empirically demonstrate that our MIO-based algorithm improves performance in finding bias. We train high-performing, interpretable classifiers that bound intersectional bias below an acceptable threshold, offering a robust solution for regulated industries and beyond.

Figures & tables

Figure 1: An illustrative example of when marginal bias is not enough. Statistical parity is achieved, suggesting marginal fairness, while blue people aged 0-18 are disproportionately more rejected. The graphic is a modification of Figure 1 in Němeček et al. [34] .

Dataset name	# samples	$\|A\|$	# subgroups ( $\mathcal{S}_{A}$ )	Conjunction cuts	Linear cuts	Overall cuts
ACS Income	195,665	4	1,229	3.80 $\pm$ 1.03	11.33 $\pm$ 10.13	8.32 $\pm$ 8.63
ACS Public Coverage	138,554	12	56,008,799	9.90 $\pm$ 1.79	13.93 $\pm$ 11.14	12.32 $\pm$ 8.81
ACS Mobility	80,329	11	11,567,699	0.80 $\pm$ 0.79	21.33 $\pm$ 17.00	13.12 $\pm$ 16.56
ACS Employment	378,817	11	18,381,599	22.50 $\pm$ 8.59	15.87 $\pm$ 13.55	18.52 $\pm$ 12.07
ACS Travel Time	172,508	6	47,339	5.00 $\pm$ 1.56	10.67 $\pm$ 9.80	8.40 $\pm$ 8.06

Table 1: The number of samples, protected attributes (

|A|

), and intersectional subgroups representable by conjunctions of attribute-value pairs. And the mean number of subgroups (i.e., cuts of a candidate solution) considered during training of the fair models. Values after

\pm

represent standard deviation.

Figure 2: Mean fairness violation (and standard deviations). In detection, finding the subgroup with more unfairness is better. The bars with slanted lines represent the optimal solutions found over conjunction subgroups (

\mathcal{S}_{A}

), which are a subset of linear subgroups (

\mathcal{S}_{L}

), explaining the difference to the other setups. The blue bar with slanted lines to the left corresponds to MSD, and the orange bar to the right corresponds to GerryFair; the rest is our work.

Figure 3: Comparison of trained classifiers. We compare our MIO-based approach to a classifier without fairness constraints and GerryFair. The dashed line represents the fairness threshold

\gamma

used during training. Blue boxes indicate using SD as a proxy for FPSF to identify the violating subgroup; in training, all use the FPSF measure. We evaluate FPSF violation using MIO on conjunction subgroups (

\mathcal{S}_{A}

Figure 4: Change in fairness, accuracy, and number of cuts, after introducing a sparsity term into the objective. A positive value means an increase in value after introducing the sparsity term.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 5: Results of bias detection with a time limit of 5 minutes.

Figure 6: Results of bias detection with a time limit of 10 minutes.

Figure 7: Results of bias detection over the entire datasets.

Figure 8: Solver process in bias detection over the entire datasets, over 10 runs with linear subgroups. Values represent the incumbent detected bias, relative to the final discovered value. The thick line is median value, thinner lines denote single runs and ribbon covers the range of all values. Note that x axis is log-scale. First values are available after a few seconds in some runs, leading to some jaggedness of the line and the ribbon.

Figure 9: Detailed results of training a linear classifier without a sparsity term (

\sigma=0

) under the proposed framework.

Figure 10: Detailed results of training a linear classifier with a sparsity term

\sigma=0.1

under the proposed framework

Figure 11: Preliminary results of training a DNF classifier with 1 term (a conjunction) under the proposed framework.

Figure 12: Preliminary results of training a DNF classifier with 3 terms under the proposed framework.

Explore similar work

Data Bias Mitigation under Coverage Constraints & The Price of Fairness
Jun 18, 2026Bruno Scarone, Alfredo Viola, Renée J. MillerAlgorithmic Fairness Subgroups
Khoury College of Computer Sciences, Northeastern University, USA · Casa de Investigadores Científicos La Comarca, Uruguay · Cheriton School of Computer Science, University of Waterloo, Canada
When Interpretability Is Unequally Distributed: Fairness in Hybrid Interpretable Models
May 27, 2026Ziba Jabbar Zare, Ulrich Aïvodji, Julien Ferry +1Interpretability Algorithmic Fairness
Department of Mechanical, Industrial and Aerospace Engineering, Concordia University, Canada · Software and Information Technology Engineering Department, École de technologie supérieure, Canada · CIRRELT & SCALE-AI Chair in Data-Driven Supply Chains, Department of Mathematics and Industrial Engineering, Polytechnique Montréal, Canada
MIFair: A Mutual-Information Framework for Intersectionality and Multiclass Fairness
Apr 30, 2026Jeanne Monnier, Thomas George, Frédéric Guyard +2Algorithmic Fairness Multiclass Classification
Orange Research, Châtillon, France · EURECOM, Sophia Antipolis, France

Jun 18, 2026, cs.LGJ/K move · Enter open · S save

Data Bias Mitigation under Coverage Constraints & The Price of Fairness

Bruno Scarone, Alfredo Viola, Renée J. Miller

Khoury College of Computer Sciences, Northeastern University, USA · Casa de Investigadores Científicos La Comarca, Uruguay · Cheriton School of Computer Science, University of Waterloo, Canada

Algorithmic Fairness Subgroups Mitigation Discriminative Structural Constraints Governance

Open paper AskPDF arXiv

Machine learning models have been shown to exhibit discriminatory outcomes or degraded performance for individuals at the intersection of multiple sensitive attributes, such as race and gender. This stems in part from two interrelated challenges: the lack of principled measures for quantifying bias (potentially intersectional), and insufficient representation of intersectional subgroups in training data. We extend a recent bias mitigation framework to incorporate coverage constraints that enforce sufficient representation across groups, including intersectional subgroups. Since achieving exactly zero bias for all groups may not be data efficient (meaning it may require large amounts of data), our solution trades small approximation errors in bias for greater data efficiency while satisfying coverage constraints. We also formulate bias mitigation as an integer linear program that optimizes over all mitigation strategies, and characterize the price of fairness, the minimum data modification cost, as a function of fairness tolerance. This is essential both for legal compliance, where regulations may mandate specific fairness thresholds, and for data governance, enabling practitioners to make informed trade-offs between bias reduction and data modification (particularly, data purchasing) costs. We evaluate our techniques on publicly available datasets, demonstrating that bias mitigation via our framework preserves predictive accuracy across multiple classifiers, and that coverage constraints, while motivated by statistical considerations, are essential for preserving downstream ML performance.

Abstract

Explore similar work

Data Bias Mitigation under Coverage Constraints & The Price of Fairness

When Interpretability Is Unequally Distributed: Fairness in Hybrid Interpretable Models

MIFair: A Mutual-Information Framework for Intersectionality and Multiclass Fairness