Intersectional Fairness via Mixed-Integer Optimization

True fairness requires addressing bias at the intersections of protected groups, and this paper proposes a unified framework leveraging Mixed-Integer Optimization (MIO) to train intersectionally fair and intrinsically interpretable classifiers. The central finding is that it proves the equivalence of two measures of intersectional fairness (MSD and SPSF) in detecting the most unfair subgroup, and empirically demonstrates that the MIO-based algorithm improves performance in finding bias.

Key Concepts in Fairness Evaluation

The paper distinguishes between three categories of classifier unfairness: marginal fairness, individual fairness, and intersectional fairness. Marginal fairness focuses on treating all protected groups the same based on a single attribute. Intersectional fairness extends this by considering all intersections of marginal groups, which accounts for compounded discrimination against uniquely disadvantaged subgroups defined by combinations of sensitive attributes. The authors note that simply expanding group intersections into new attributes is insufficient due to the exponential growth and data sparsity issues. They introduce several notions, including Statistical Parity Subgroup Fairness (SPSF), which generalizes Statistical Parity from marginal fairness to intersectional fairness, and False Positive Subgroup Fairness (FPSF).

Detection of the Most Unfair Subgroup

The framework utilizes Mixed-Integer Optimization (MIO) to reliably identify the most unfair subgroup. The paper proves the equivalence between Statistical Parity Subgroup Fairness (SPSF) and Maximum Subgroup Discrepancy (MSD) in detecting the most biased subgroup. Specifically, Theorem 1 establishes that the set of subgroups S ∈ SA that maximize the SPSF metric is identical to the set of subgroups achieving the Maximum Subgroup Discrepancy between the distributions of positively- and negatively-classified samples. This equivalence is crucial because MSD offers a sample-efficient distance measure, whereas traditional distance metrics like Wasserstein or Total Variation have exponential sample complexity.

Training Framework for Intersectional Fairness

The training framework aims to improve fairness for the most disadvantaged groups by optimizing a balanced 0-1 loss function subject to intersectional fairness constraints. The optimization problem is formulated as:

min Xn i=1 J yˆi != y i K/Nyi (3a)

s.t. h(x i) = ˆy i ∀ i ∈ D (3b)

UnfairnessS(x, y, ŷ) ≤ γ ∀S ∈ S (3c).

To manage the exponential number of constraints arising from all possible subgroups, the framework employs lazy constraints, also known as cutting planes. This approach involves iteratively finding the most unfair subgroup and adding it as a constraint to the model if it violates the threshold γ, thereby avoiding an exponential number of constraints. The paper validates this by showing that this lazy approach enables consideration of exponentially many fairness constraints (in the number of protected features) within the framework of intersectionally fair training.

Model Representation and Optimization

The paper explores training various interpretable models using MIO, including linear classifiers and Decision-First Negation (DNF) rule sets. For linear classifiers, the formulation includes a sparsity term to encourage simpler models:

min 1/D0 X i∈D0 yˆ i + 1/D1 X i∈D1 (1 - yˆ i) + σ d X j i=1 s.t. c T x i − t ≥ (ˆy i - 1) · 2d i ∈ D (8b).

The paper demonstrates that MIO allows for finding globally optimal solutions, i.e., models with the highest performance, which is vital given the inherent interpretability-performance tradeoff.

Empirical Validation and Results

Experiments on five datasets from the folktables library empirically validate the theoretical results. The comparison between conjunction-based subgroups (SA) and linear subgroups (SL) in detection shows that MIO consistently finds subgroups with notably higher unfairness than GerryFair. Furthermore, in training, FPSF or SD generally works better for training more generally compared to SPSF. The use of sparsity terms in the linear model formulation was shown to lead to a notable decrease in unfairness on the test set while maintaining comparable accuracy. Finally, the results confirm that MIO is feasible through lazy constraints, achieving fairness while constraining only a few dozen subgroups (at most 47).

Conclusion

The research demonstrates that MSD and SPSF yield the same set of subgroups when detecting the most unfair subgroup. The work validates Mixed-Integer Optimization for identifying subgroups with higher unfairness, which is an essential task in bias auditing and mitigation. Furthermore, the lazy approach to fairness constraint generation enables consideration of exponentially many fairness constraints within the framework of intersectionally fair training.

The gist: The equivalence between Maximum Subgroup Discrepancy (MSD) and Statistical Parity Subgroup Fairness (SPSF) is proven, and a Mixed-Integer Optimization framework using lazy constraints

Here are specific improvements to AI systems based on the proposed framework:

1. Improved Bias Auditing through Subgroup Discrepancy (SD) and Statistical Parity Subgroup Fairness (SPSF):

2. Development of Certifiably Fair and Interpretable Classifiers via Mixed-Integer Optimization (MIO):

3. Creation of a Robust, Sample-Efficient Fairness Constraint Generation Mechanism:

1. Improved Bias Auditing through Subgroup Discrepancy (SD) and Statistical Parity Subgroup Fairness (SPSF):

The system can move beyond single-attribute fairness metrics to detect the most unfair subgroup by maximizing the Maximum Subgroup Discrepancy (MSD).

Furthermore, it can compare the effectiveness of MSD with Statistical Parity Subgroup Fairness (SPSF) in identifying these subgroups, proving their equivalence for detection.

The system can pinpoint exactly which intersectional group is disproportionately affected by algorithmic errors (e.g., rejections or misclassifications), allowing auditors to prioritize targeted intervention strategies against the most marginalized subgroups.

2. Development of Certifiably Fair and Interpretable Classifiers via Mixed-Integer Optimization (MIO):

The system can train high-performing, intrinsically interpretable models (like decision trees or rule sets) while simultaneously enforcing intersectional fairness constraints during training.

By using MIO, the system can optimize for global performance while ensuring that the resulting classifier is provably fair across a set of defined intersectional subgroups (e.g., female and under 18). This means deployed models are not just accurate, but are mathematically constrained to operate within an acceptable threshold of intersectional bias.

3. Creation of a Robust, Sample-Efficient Fairness Constraint Generation Mechanism:

The system can handle the exponential complexity of defining all possible intersectional subgroups by using lazy constraints (cutting planes) within the MIO framework.

This mechanism allows the model to search for and enforce fairness constraints on exponentially many potential subgroups without needing to explicitly define every single one. This makes it feasible to train complex, multi-attribute AI models that are fair across numerous overlapping demographic intersections, even when data is sparse for specific subgroups.

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.