🤖 machine learning

Fairness of Classifiers in the Presence of Constraints between Features

This paper proposes defining classifier fairness through the existence of "fair explanations" (prime-implicant reasons excluding protected features) that account for feature constraints, and it analyzes the relationships and computational complexity of three distinct fairness definitions under these conditions.

Original authors: Martin C. Cooper, Imane Bousdira

Published 2026-05-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Martin C. Cooper, Imane Bousdira

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a judge deciding who gets a job, a loan, or a bonus. In the world of Artificial Intelligence (AI), we want to make sure these judges are fair. Usually, "fair" means the judge doesn't look at sensitive things like a person's gender or race.

But this paper argues that looking at the "sensitive" features isn't enough. You also have to look at the rules of the game (the constraints) that connect different pieces of information. If you ignore these rules, you might think a judge is unfair when they are actually fair, or vice versa.

Here is a breakdown of the paper's main ideas using simple analogies.

1. The Trap of "Hidden Rules"

Imagine a club with a rule: "You can only enter if you are wearing a red hat AND you are a member."

The Features: "Wearing a red hat" and "Being a member."
The Constraint: In this specific club, only members are allowed to wear red hats. If you aren't a member, you can't have a red hat.

Now, imagine an AI judge decides who gets in.

Scenario A (Ignoring Rules): The AI sees a person with a red hat but no membership card (which is impossible in reality, but the AI doesn't know the rule). It says, "No, because you don't have a card." It looks like the AI is ignoring the hat.
Scenario B (Knowing Rules): The AI knows the rule: "Red hats only exist for members." So, if someone has a red hat, they must be a member. The AI says, "Yes, you get in because you have a red hat."

The paper says: If you don't know the rule (the constraint), you might think the AI is unfair because it seems to care about the hat. But if you do know the rule, you realize the hat is just a shortcut for membership. The AI is actually fair.

The Paper's Claim: You cannot judge fairness by just looking at the inputs; you must look at how the inputs are legally or logically connected.

2. The "Fair Explanation" Test

The authors propose a new way to check if a decision is fair. Instead of asking, "Did the AI look at gender?", they ask: "Can the AI explain its decision without mentioning gender?"

They call this a "Fair Explanation."

The Analogy: Imagine you are applying for a loan.
- Unfair Explanation: "You were rejected because you are a woman." (This is bad).
- Fair Explanation: "You were rejected because your income is too low." (This is good).
- The Twist: Sometimes, the AI's logic is messy. It might say, "Rejected because (You are a woman AND income is low) OR (You are a man AND income is low)."
- The Paper's Solution: If the AI can find one simple reason that doesn't mention gender (e.g., "Income is low"), then the decision is Existentially Fair. If every possible reason it could give involves gender, then it is Unfair.

3. Three Levels of Fairness

The paper defines three ways a whole AI system (a classifier) can be considered fair:

Existential Fairness (The "At Least One" Rule):
- Analogy: For every decision the AI makes, can it find at least one excuse that doesn't mention gender?
- Verdict: If yes, the system passes this test. It's like saying, "I can justify this decision without being sexist, even if I have other sexist reasons floating around in my brain."
Universal Fairness (The "All Reasons" Rule):
- Analogy: For every decision, are all possible explanations free of gender?
- Verdict: This is much stricter. It means the AI cannot possibly use gender as a reason, even if it wanted to.
Fairness Through Unawareness (The "Blindfold" Rule):
- Analogy: If two people are identical in every way except for their gender, do they get the same result?
- Verdict: The paper shows that in a world with rules (constraints), this "blindfold" test can be tricky. Sometimes, because of the rules, two people can't be identical except for gender (e.g., you can't be a man on maternity leave). So, the blindfold test might fail even if the AI is fair.

4. The "Magic" of Constraints

The paper uses math to show some surprising things:

Ignoring constraints can make a fair AI look unfair. (Like the maternity leave example: If you don't know that only women take maternity leave, you might think an AI is discriminating against men when it's just following the law).
Ignoring constraints can make an unfair AI look fair. (If an AI uses a hidden rule to discriminate, but you don't see the rule, you might think it's innocent).

5. The Cost of Checking Fairness

The paper ends with a warning about complexity.

The Analogy: Checking if a simple "blindfold" rule is followed is like checking a grocery list; it's fast.
The Reality: Checking if an AI has a "Fair Explanation" (especially when rules are involved) is like trying to solve a massive, multi-layered puzzle where you have to imagine every possible version of reality.
The Result: The authors found that checking these advanced fairness definitions is computationally very hard (mathematically speaking, it's in a high tier of difficulty). However, they found some shortcuts (like "loose constraints") where the check becomes easier again.

Summary

This paper argues that fairness is not just about what data you feed the AI, but about the rules that connect that data.

If you ignore the rules, you might punish a fair AI or let a biased one slide.
The best way to check fairness is to ask: "Can you explain this decision without using the protected feature?"
Doing this check perfectly is very hard for computers to do, but it's necessary to ensure true fairness.

1. Problem Statement

The paper addresses a critical gap in the definition and evaluation of fairness in Machine Learning classifiers: the presence of logical constraints between features.

Context: Standard definitions of fairness (e.g., Fairness Through Unawareness) often assume that a decision is fair if it does not depend on protected features (e.g., gender, race).
The Issue: In real-world scenarios, features are rarely independent. Constraints exist due to:
- Encoding: e.g., One-hot encoding where exactly one boolean feature must be true.
- Real-world logic: e.g., "If a person is on maternity leave, they must be female and employed."
The Consequence: Ignoring these constraints can lead to false positives (deeming a fair classifier unfair) or false negatives (deeming an unfair classifier fair).
- Example: A model might appear to depend on gender because the model output changes when gender flips, but if the constraint implies that flipping gender also forces a change in another feature (like employment status), the decision might actually be independent of gender in the valid feature space.
Goal: To formally define fairness in the presence of constraints ( $C$ ) and analyze the computational complexity of verifying these definitions.

2. Methodology and Core Concepts

The authors utilize Abductive Explanations (AXp) and Prime Implicants (PI) within a constrained feature space.

Key Definitions

Feature Space ( $F$ ): The Cartesian product of feature domains.
Constraints ( $C$ ): A set of logical rules restricting valid instances. The valid space is $F[C]$ .
Protected Features ( $P$ ) vs. Unprotected Features ( $N$ ): $P$ contains sensitive attributes (e.g., gender); $N$ contains others.
Abductive Explanation (AXp): A subset of features $S$ such that fixing the values of $S$ to those in instance $x$ guarantees the classifier output $\kappa(x)$ , considering only instances in $F[C]$ .
Prime-Implicant Explanation (PI-explanation): An AXp that is not strictly subsumed by another AXp. In constrained spaces, subsumption is defined by logical implication within $F[C]$ , not just set inclusion.
Fair PI-explanation: A PI-explanation that contains no protected features ( $S \cap P = \emptyset$ ).

Proposed Definitions of Fairness

The paper proposes three distinct definitions for the fairness of a classifier $\kappa$ :

Constrained Fairness Through Unawareness (FTU):
- For all $x, y \in F[C]$ , if $x_N = y_N$ (unprotected features are identical), then $\kappa(x) = \kappa(y)$ .
- This ensures the decision depends only on unprotected features within the valid space.
Existential Fairness:
- For every decision $\kappa(x) = c$ , there exists at least one fair PI-explanation.
- Meaning: There is some valid reason for the decision that does not rely on protected features.
Universal Fairness:
- For every decision $\kappa(x) = c$ , all PI-explanations are fair.
- Meaning: Every minimal reason for the decision avoids protected features.

Theoretical Analysis

The authors analyze the relationships between these definitions under different constraint scenarios:

Constraints between $P$ and $N$ : Ignoring these can drastically alter fairness assessments. A decision can be universally fair in $F[C]$ but appear unfair in unconstrained $F$ , or vice versa.
Constraints within $P$ only: If constraints exist only between protected features, the existence of a fair PI-explanation is preserved from unconstrained to constrained spaces (Proposition 1).
Constraints within $N$ only: The existence of a fair PI-explanation is independent of these constraints (Proposition 2). However, constraints within $N$ can create unfair PI-explanations that did not exist in the unconstrained space (Example 7).

Special Conditions for Equivalence

The paper identifies conditions where the complex definitions (Existential/Universal) simplify to the easier-to-check Constrained FTU:

Loose Constraints: If no partial assignment of a protected feature strictly subsumes the assignment of all unprotected features, then Constrained FTU implies Existential Fairness.
Disentangled Classifiers: A classifier is "disentangled" if the set of unprotected features $N$ is a weak AXp not strictly subsumed by any unfair AXp. This guarantees Existential Fairness.

3. Key Contributions

Formalization of Fairness with Constraints: The paper moves beyond the standard "unawareness" definition by integrating logical constraints directly into the definition of explanations (PI-explanations).
Demonstration of Constraint Impact: Through multiple examples (e.g., maternity leave, adoption agencies), the authors prove that ignoring constraints leads to incorrect fairness assessments.
Hierarchy of Fairness Definitions: The paper establishes the logical relationships between Constrained FTU, Existential Fairness, and Universal Fairness.
- Universal $\implies$ Existential $\implies$ Constrained FTU.
- The reverse implications generally do not hold unless specific conditions (like "loose constraints" or "no constraints between P and N") are met.
Complexity Analysis: The authors map the computational complexity of verifying these fairness notions within the Polynomial Hierarchy.

4. Results and Complexity Analysis

The paper provides a rigorous complexity analysis for testing these fairness definitions:

Fairness Notion	Complexity Class	Notes
Existence of Fair PI-explanation (for a single decision)	$\Sigma^P_3$	Involves $\exists \forall \exists$ quantifier alternation.
Existence of Unfair PI-explanation	$\Sigma^P_3$	Complement of the above.
Testing Existential Fairness (Classifier)	$\Pi^P_4$	Requires checking all instances ( $\forall x$ ) for the $\Sigma^P_3$ property.
Testing Universal Fairness (Classifier)	$\Pi^P_3$	Equivalent to checking that no unfair explanation exists for any instance.
Testing Constrained FTU	coNP-complete	Can be solved by a single SAT solver call (checking if $\exists x, y$ with same $N$ but different outputs).

Key Complexity Insight:

Testing Constrained FTU is computationally feasible (coNP-complete) and can be handled by standard SAT solvers.
Testing Existential/Universal Fairness is significantly harder ( $\Pi^P_3$ or $\Pi^P_4$ ), requiring Quantified Boolean Formula (QBF) solvers.
Practical Implication: The authors propose using "Loose Constraints" or "Disentangled" checks (which are $\Pi^P_2$ ) as sufficient conditions to guarantee Existential Fairness, allowing the use of simpler SAT solvers instead of QBF solvers.

5. Significance and Conclusion

Theoretical Foundation: The paper establishes that fairness cannot be assessed in a vacuum; the logical structure of the feature space (constraints) fundamentally alters the definition of a "reason" for a decision.
Practical Guidance: It warns practitioners that standard fairness tools (which often ignore constraints) may produce misleading results.
Trade-off: There is a trade-off between the strictness of the fairness definition and computational tractability.
- Universal Fairness is the strictest but hardest to verify.
- Constrained FTU is the easiest to verify but may miss cases where a decision is technically dependent on protected features via constraints.
Future Directions: The authors suggest extending this logical framework to handle statistical correlations and exploring the "choice of protected features" using causal graphs (Fairness Through Causal Independence - FTCI).

In summary, this paper argues that fairness is context-dependent on feature constraints. It provides a formal framework to define fairness via prime-implicant explanations and offers a roadmap for verifying these definitions, balancing theoretical rigor with computational feasibility.