Searching for Unfairness in Algorithms' Outputs: Novel Tests and Insights

Ian Davidson, S. S. RaviAAAI 2025 · DOI

Introduction

As AI systems are increasingly deployed in high-stakes domains like credit scoring, hiring, and law enforcement, ensuring their fairness has become a critical priority. Most current research focuses on a "fairness by design" approach, where developers incorporate constraints into an algorithm’s training phase to ensure equitable treatment of broad demographic groups, such as gender or race. However, this approach often fails to address intersectionality—the unique bias experienced by individuals at the crossing of multiple identities (e.g., "Older Hispanic Men").

The Intersectional Fairness Gap

The challenge of intersectional fairness is primarily combinatorial. With dozens of protected status variables (PSVs), the number of possible subgroup combinations grows exponentially into the billions. It is computationally infeasible to optimize for every possible intersection during model training. Consequently, an algorithm that appears "fair" when evaluating race and gender independently may still exhibit profound bias against specific intersectional subgroups.

This paper introduces a novel framework to audit the outputs of any "black-box" AI algorithm for intersectional unfairness. Unlike previous tools, this framework handles non-binary categories and accounts for the varying utility of different algorithmic outcomes.

Methodology: Auditing as Optimization

The researchers formulate the search for biased subgroups as a combinatorial optimization problem. They treat the algorithm as a black box that partitions individuals into $K$ categories. Unfairness is identified through two primary lenses:

  1. Count-Based Unfairness: This test identifies the simplest subgroup (defined by the minimum number of attributes) that is significantly under-represented in desirable categories compared to the general population.
  2. Utility-Weighted Unfairness: Recognizing that not all outcomes are equal (e.g., different credit limits or loyalty tiers), this test evaluates whether the total utility received by a subgroup deviates significantly from a random assignment baseline.
The probabilistic constraint used to define unfairness thresholds.

The search for the most unfair subgroup is proven to be NP-hard. To solve it, the authors employ Quadratic Integer Programming (QIP), allowing for a rigorous search across complex attribute combinations that provides human-interpretable results.

Experimental Evaluation

The framework was validated across three diverse datasets: Celeb-A (image data), the Adult Data Set (census data), and California Electoral Data.

The Fairness Paradox

A key finding of the study is the "fairness paradox." In experiments with the Celeb-A dataset, auditing a state-of-the-art "fair" outlier detector revealed that enforcing fairness on individual attributes actually increased intersectional unfairness. For instance, unfairness in two-way intersections rose from 39% to 48% when the "fair" version of the algorithm was used.

Visualizing intersectional subgroups identified during the Celeb-A dataset audit.

Real-World Auditing

In electoral auditing, the framework identified specific California districts where certain racial subgroups were assigned to districts with significantly lower "utility" (measured by property tax basis) than expected. In clustering tasks, forcing gender fairness led the algorithm to become more unfair toward combinations of education level and marital status, highlighting the "whack-a-mole" nature of constrained optimization in fairness.

Conclusion

This research highlights a critical blind spot in current AI fairness practices. By providing a robust, post-hoc auditing tool, the authors enable developers to identify and interpret specific patterns of intersectional bias that design-time constraints miss. While the computational cost of the NP-hard optimization remains a challenge, the ability to provide "simplicity as explanation" makes this a powerful tool for algorithmic accountability.

Summary updated

BibTeX
@inproceedings{davidson2025searching,
  author = {Ian Davidson and S. S. Ravi},
  title = {{Searching for Unfairness in Algorithms' Outputs: Novel Tests and Insights}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i26.34933},
}
Figure