# Fairness of Classifiers in the Presence of Constraints between Features

arXiv: https://arxiv.org/abs/2605.00592 · HTML: https://mlsanity.com/paper/2605.00592/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 38 references that are in the map.
- First posted on arXiv 1 May 2026.

## Builds on (most cited first, 22 of 22)

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [A Survey on Bias and Fairness in Machine Learning](https://mlsanity.com/paper/1908.09635/) (2019)
- [Counterfactual Fairness](https://mlsanity.com/paper/1703.06856/) (2017)
- [Fair prediction with disparate impact: A study of bias in recidivism prediction instruments](https://mlsanity.com/paper/1610.07524/) (2016)
- [Inherent Trade-Offs in the Fair Determination of Risk Scores](https://mlsanity.com/paper/1609.05807/) (2016)
- [Algorithmic decision making and the cost of fairness](https://mlsanity.com/paper/1701.08230/) (2017)
- [Fairness in Criminal Justice Risk Assessments: The State of the Art](https://mlsanity.com/paper/1703.09207/) (2017)
- [Avoiding Discrimination through Causal Reasoning](https://mlsanity.com/paper/1706.02744/) (2017)
- [Fairness in Machine Learning: Lessons from Political Philosophy](https://mlsanity.com/paper/1712.03586/) (2017)
- [Fair Inference On Outcomes](https://mlsanity.com/paper/1705.10378/) (2017)
- [A Symbolic Approach to Explaining Bayesian Network Classifiers](https://mlsanity.com/paper/1805.03364/) (2018)
- [Fairness Testing: Testing Software for Discrimination](https://mlsanity.com/paper/1709.03221/) (2017)
- [Model Interpretability through the Lens of Computational Complexity](https://mlsanity.com/paper/2010.12265/) (2020)
- [On Explaining Random Forests with SAT](https://mlsanity.com/paper/2105.10278/) (2021)
- [How Do Fairness Definitions Fare? Examining Public Attitudes Towards Algorithmic Definitions of Fairness](https://mlsanity.com/paper/1811.03654/) (2018)
- [On the Computational Intelligibility of Boolean Classifiers](https://mlsanity.com/paper/2104.06172/) (2021)
- [SAT-Based Rigorous Explanations for Decision Lists](https://mlsanity.com/paper/2105.06782/) (2021)
- [Eliminating The Impossible, Whatever Remains Must Be True](https://mlsanity.com/paper/2206.09551/) (2022)
- [Local vs. Global Interpretability: A Computational Complexity Perspective](https://mlsanity.com/paper/2406.02981/) (2024)
- [Abductive explanations of classifiers under constraints: Complexity and properties](https://mlsanity.com/paper/2409.12154/) (2024)
- [Procedural Fairness in Machine Learning](https://mlsanity.com/paper/2404.01877/) (2024)
- [Explaining Decisions in ML Models: a Parameterized Complexity Analysis](https://mlsanity.com/paper/2407.15780/) (2024)

## Abstract (arXiv)

In Machine Learning, an accepted definition of fairness of a decision taken by a classifier is that it should not depend on protected features, such as gender. Unfortunately, when constraints exist between features, such dependencies can be obscured by the constraints. To avoid this problem, we propose that a decision be considered fair if it has a fair explanation. We define a fair explanation as a prime-implicant reason for the decision that does not contain any protected feature (where the constraints are taken into account in the definition of prime-implicant). Surprisingly, ignoring constraints can completely change the fairness of a decision (according to this definition) even in the absence of constraints between protected and unprotected features. Three possible definitions of fairness of a classifier are that for all its decisions (1) there are only fair explanations, (2) there is at least one fair explanation, or (3) changing protected features does not change the outcome. We identify the relationships between these different definitions of fairness and study the computational complexity of testing fairness of classifiers.