Exploring Impossibility Results for Algorithmic Fairness Using PrSAT

Tina Eliassi-Rad & Branden Fitelson
June 5, 2023

PrSAT — A Decision Procedure for Probability Calculus

PrSAT is a decision procedure for probability calculus that has been implemented in Mathematica (it’s been tested on versions of Mathematica up to v12.3).   See Fitelson (2008) for details.

The package is self-contained, and can be downloaded from the following website (which also includes instructions for installation and use).

	http://fitelson.org/PrSAT/

We begin by loading the PrSAT package (which defines all the Mathematica functions we’ll be using).

<<PrSAT`

Notation, Fairness Measures, and Side Conditions/Auxiliary Assumptions

We will be discussing binary classification.  Our binary classifier (OverHat[T]) can take two values: (OverHat[T])  = 1 or (OverHat[T]) = 0.  We will denote these predicted values as (OverHat[T]) and ¬(OverHat[T]), respectively.  The actual value of the parameter in question will either take the value T = 1 or T = 0, and we will denote these two possibilities as T and ¬T, respectively.  

Initially, we will be looking at a single, (binary) protected attribute P, which can take either the value P = 1 or the value P = 0, and we will denote these two possibilities as P and ¬P, respectively.  

Assuming these notational conventions, we can define the following four traditional, confusion-matrix-based measures of algorithmic fairness (expressed in pure probability calculus), as follows:

PredictiveParity=Pr[T|(OverHat[T])∧P]==Pr[T|(OverHat[T])∧¬P];
TruePositiveParity=Pr[(OverHat[T])|T∧P]==Pr[(OverHat[T])|T∧¬P];
FalsePositiveParity=Pr[(OverHat[T])|¬T∧P]==Pr[(OverHat[T])|¬T∧¬P];
StatisticalParity=Pr[(OverHat[T])|P]==Pr[(OverHat[T])|¬P];

Terminological notes: Chouldechova (2017) refers to the conjunction of True Positive Parity & False Positive Parity as “Error Base Rate.” This conjunction is also sometimes referred to as “Equalized Odds” or “Positive Rate Parity.”  We are keeping these separate, because True Positive Parity is also implicated in several other impossibility results discussed below.  True Positive Parity is also known in the literature as “Equal Opportunity” (Mehrabi et al 2019).   Predictive Parity is sometimes also referred to as “Positive Predictive Value Parity.” 

We will also be working with the following three “side conditions” or “auxiliary assumptions”.

UnequalBaseRates=Pr[T|P]≠Pr[T|¬P];
ImperfectClassifier=And@@{Pr[(OverHat[T])|¬T∧P]≠0,Pr[(OverHat[T])|¬T∧¬P]≠0,Pr[(OverHat[T])|T∧P]≠1,Pr[(OverHat[T])|T∧¬P]≠1};
NonZeroPrecision=Pr[T|(OverHat[T])∧P]≠0∨Pr[T|(OverHat[T])∧¬P]≠0;

Verifying Two Well-Known Impossibility Results with PrSAT

Impossibility #1: Chouldechova (2017)

Here is a simple PrSAT verification of Chouldechova's (2017) impossibility theorem, expressed in pure probability calculus using the above notation.  

Impossibility #1. There are no probability models satisfying all four of these fairness constraints:

	(i) Predictive Parity (i.e., PredictiveParity)
	(ii) True Positive Parity (i.e., TruePositiveParity)
	(iii) False Positive Parity (i.e., FalsePositiveParity)
	(iv) Statistical Parity (i.e., StatisticalParity)
	
subject to the following side condition/auxiliary assumption: 

	(b) there are unequal base rates (of P) in the two populations P and ¬P (i.e., UnequalBaseRates).

PrSAT[
{
PredictiveParity,
TruePositiveParity,
FalsePositiveParity,
StatisticalParity,

UnequalBaseRates
},
BypassSearch->True
]

Moreover, no proper subset of these five conditions is unsatisfiable (i.e., such that there is no probability assignment Pr(•) which makes all of the claims true), as the following calculations reveal.

NonemptyProperSubsets[S_]:=Drop[Drop[Subsets[S],1],-1];

ChouldechovaSubsets=NonemptyProperSubsets[
{
PredictiveParity,
TruePositiveParity,
FalsePositiveParity,
StatisticalParity,

UnequalBaseRates
}
];

Select[ChouldechovaSubsets,PrSAT[#,BypassSearch->True]==={}&]

So, in this sense, this is the “minimal” Chouldechova-style impossibility theorem.

Impossibility #2: Kleinberg et al (2016)

Here is a simple PrSAT verification of Kleinberg et al’s (2016) impossibility theorem, expressed in pure probability calculus, using the above notation.  

Impossibility #2. There are no probability models satisfying all three of these fairness constraints:

	(i) Predictive Parity (i.e., PredictiveParity),
	(ii) True Positive Parity (i.e., TruePositiveParity), and
	(iii) False Positive Parity (i.e., FalsePositiveParity),
	
subject to the following three side conditions/auxiliary assumptions: 

	(a) there are unequal base rates (of T) in the two populations P and ¬P (i.e., UnequalBaseRates),
	(b) our classifier is imperfect (i.e., ImperfectClassifier), and
	(c) either Pr(T | (OverHat[T]) ∧ P) ≠ 0 or Pr(T | (OverHat[T]) ∧ ¬P) ≠ 0 (i.e., NonZeroPrecision).

PrSAT[
{
PredictiveParity,
TruePositiveParity,
FalsePositiveParity,

UnequalBaseRates,
ImperfectClassifier,
NonZeroPrecision
},
BypassSearch->True
]

To see that the side condition NonZeroPrecision is required for this impossibility result, we can use PrSAT to find a model of the remaining five conditions.

model=PrSAT[
{
PredictiveParity,
TruePositiveParity,
FalsePositiveParity,

UnequalBaseRates,
ImperfectClassifier
},
BypassSearch->True
]

We can use the function STT to represent this model as a stochastic truth-table, in the sense of Fitelson (2008).

STT[model]

And, we can verify the correctness of this model using the function EvaluateProbability.

EvaluateProbability[
{
PredictiveParity,
TruePositiveParity,
FalsePositiveParity,

UnequalBaseRates,
ImperfectClassifier
},
model]

Moreover, no proper subset of these six conditions is unsatisfiable (as the following calculations reveal).

KleinbergSubsets=NonemptyProperSubsets[
{
PredictiveParity,
TruePositiveParity,
FalsePositiveParity,

UnequalBaseRates,
ImperfectClassifier,
NonZeroPrecision
}
];

Select[KleinbergSubsets,PrSAT[#,BypassSearch->True]==={}&]

So, in this sense, this is the “minimal” Kleinberg et al-style impossibility theorem.

A Simplification of Kleinberg et al (2016) Based on Regularity

If we assume that the prior probability function Pr(•) is regular (i.e., that it only assigns extremal probability to non-contingent propositions), then we can obtain a simplification of the impossibility result of Kleinberg et al, involving the three fairness constraints.

	(i) Predictive Parity (i.e., PredictiveParity),
	(ii) True Positive Parity (i.e., TruePositiveParity), and
	(iii) False Positive Parity (i.e., FalsePositiveParity),
	
and the following two side conditions/auxiliary assumptions: 

	(a) there are unequal base rates (of T) in the two populations P and ¬P (i.e., UnequalBaseRates), and
	(b) Pr(•) is regular (note: this auxiliary assumption is a built-in option of the PrSAT function).  

Note: regularity is slightly stronger than Kleinberg et al’s two side-conditions.  So, this is a slightly weaker impossibility result than Kleinberg et al.   But, regularity is much simpler and easier to work with.

PrSAT[
{
PredictiveParity,
TruePositiveParity,
FalsePositiveParity,

UnequalBaseRates
},
BypassSearch->True,Probabilities->Regular
]

Moreover, assuming regularity, no proper subset of these four conditions is unsatisfiable (as the following calculations reveal).

KleinbergSubsets2=NonemptyProperSubsets[
{
PredictiveParity,
TruePositiveParity,
FalsePositiveParity,

UnequalBaseRates
}
];

Parallelize[Select[KleinbergSubsets2,PrSAT[#,Probabilities->Regular]==={}&]]

So, in this sense, this is the “minimal” Kleinberg et al-style (regularity-based) impossibility theorem.

Four Other (Contingency Table-Based) Fairness Measures

Here are four other (contingency table-based) fairness measures that have been discussed in the literature.

NegativePredictiveValueParity=Pr[T|¬(OverHat[T])∧P]==Pr[T|¬(OverHat[T])∧¬P];
OverallAccuracyEquality=Pr[(OverHat[T])|T∧P]+Pr[¬(OverHat[T])|¬T∧P]==Pr[(OverHat[T])|T∧¬P]+Pr[¬(OverHat[T])|¬T∧¬P];
EqualizingDisincentives=Pr[(OverHat[T])|T∧P]-Pr[(OverHat[T])|¬T∧P]==Pr[(OverHat[T])|T∧¬P]-Pr[(OverHat[T])|¬T∧¬P];
TreatmentEquality=((Pr[(OverHat[T])|¬T∧P])/(Pr[¬(OverHat[T])|T∧P]))==((Pr[(OverHat[T])|¬T∧¬P])/(Pr[¬(OverHat[T])|T∧¬P]));

Terminological Notes: In the literature on fairness measures, the conjunction of Predictive Parity & Negative Predictive Parity is known as “Conditional Use Accuracy.”  See Caton & Haas (2020, §3.2.2) for a survey of contingency table-based fairness measures (we adopt their terminology for our last three measures).

Automating the Search for Impossibility Results — And Impossibilities #3 and #4

We can use PrSAT to search for (e.g.) all 3-element subsets of our total set of 8 fairness constraints above which are jointly unsatisfiable (assuming Unequal Base Rates & Regularity).  In this way, we can fully automate the search for impossibility results (in the general style of Kleinberg et al).

Here’s how we can use PrSAT to exhaustively search for all 3-element sets of constraints (from our list of 8 fairness constraints, above) that are jointly unsatisfiable, in the presence of Unequal Base Rates and Regularity.

ElementQ[o_,s_]:=Or@@(#===o&/@s);

ThreeElementSubsets=Subsets[
{
PredictiveParity,
TruePositiveParity,
FalsePositiveParity,
StatisticalParity,
NegativePredictiveValueParity,
OverallAccuracyEquality,
EqualizingDisincentives,
TreatmentEquality
},{3}
];

There are 56 3-element subsets.  We search for all 3-element subsets which (assuming Unequal Base Rates & Regularity) yield impossibility, as follows.  Here, we limit each search to 60 seconds.  This yields 21 3-assumption impossibility theorems.

Impossibilities=Quiet[Parallelize[Select[ThreeElementSubsets,Quiet[TimeConstrained[PrSAT[Union[#,{UnequalBaseRates}],Probabilities->Regular],60]]==={}&]]];

Length[Impossibilities]

Impossibilities

That is, we now know that there are (at least) 21 jointly unsatisfiable 3-element subsets (containing TruePositiveParity) of our set of 8 fairness measures.  Two of these 11 correspond to the impossibility result of Kleinberg et al. (i.e., they are both notational variants of their result).

But, some of the impossibilities among these 21 appear to be novel.  

For instance, as far as we know, the following two impossibility results are novel (at least, we haven't seem them in the literature).

Impossibility #3. Statistical Parity, True Positive Parity, and Negative Predictive Parity are jointly unsatisfiable (assuming unequal base rates & regularity).

PrSAT[
{
StatisticalParity,
TruePositiveParity,
NegativePredictiveValueParity,

UnequalBaseRates
},BypassSearch->True,Probabilities->Regular
]

And, there are no proper subsets of this set that are unsatisfiable.

Subsets3=NonemptyProperSubsets[
{
StatisticalParity,
TruePositiveParity,
NegativePredictiveValueParity,

UnequalBaseRates
}
];

Select[Subsets3,PrSAT[#,BypassSearch->True,Probabilities->Regular]==={}&]

So, this appears to be a new “minimal” inconsistent set of three fairness measures (assuming unequal base rates & regularity).

Impossibility #4.  Predictive Parity, True Positive Parity, and Treatment Equality are jointly unsatisfiable (assuming unequal base rates & regularity).

PrSAT[
{
PredictiveParity,
TruePositiveParity,
TreatmentEquality,

UnequalBaseRates
},BypassSearch->True,Probabilities->Regular
]

And, there are no proper subsets of this set that are unsatisfiable.

Subsets4=NonemptyProperSubsets[
{
PredictiveParity,
TruePositiveParity,
TreatmentEquality,

UnequalBaseRates
}
];

Select[Subsets4,PrSAT[#,BypassSearch->True,Probabilities->Regular]==={}&]

So, this appears to be another new “minimal” inconsistent set of three fairness measures (assuming unequal base rates & regularity).

It is worth noting that there are no 2-element subsets of our set of 8 fairness measures that are jointly unsatisfiable (assuming unequal base rates and regularity).

TwoElementSubsets=Subsets[
{
PredictiveParity,
TruePositiveParity,
FalsePositiveParity,
StatisticalParity,
NegativePredictiveValueParity,
OverallAccuracyEquality,
EqualizingDisincentives,
TreatmentEquality
},{2}
];

Select[TwoElementSubsets,PrSAT[Union[#,{UnequalBaseRates,Pr[P]==(1/2),Pr[T|P]==(2/3),Pr[T|¬P]==(1/3)}],BypassSearch->True,Probabilities->Regular]==={}&]

Note: in this last search, we added a few equational constraints to speed-up the search for satisfying probability models.  Since models were found for each 2-element subset (even with these additional constraints added), this results in no loss of generality for present purposes.

PrSAT is a very useful tool for discovering, verifying, and generalizing impossibility results (in this notebook, we're just scratching the surface).

Generalizing The Impossibilities — Beyond P and ¬P

In our analysis above, we assumed that we had one (binary) protected attribute P.  This is tantamount to assuming we’re dealing with two populations (protected and non-protected) which are mutually exclusive and exhaustive.  All of the results above can be generalized by supposing we are dealing with two populations P and ℬ (instead of P and ¬P), which need not be mutually exclusive or exhaustive (thus allowing for the presence of intersectionality effects, etc.).  In fact, we need not assume anything about the relationship between populations P and ℬ (except what is already encoded in the fairness measures/side conditions).  Here are the corresponding (eight) generalized fairness conditions.

PredictiveParityG=Pr[T|(OverHat[T])∧P]==Pr[T|(OverHat[T])∧ℬ];
TruePositiveParityG=Pr[(OverHat[T])|T∧P]==Pr[(OverHat[T])|T∧ℬ];
FalsePositiveParityG=Pr[(OverHat[T])|¬T∧P]==Pr[(OverHat[T])|¬T∧ℬ];
StatisticalParityG=Pr[(OverHat[T])|P]==Pr[(OverHat[T])|ℬ];
NegativePredictiveValueParityG=Pr[T|¬(OverHat[T])∧P]==Pr[T|¬(OverHat[T])∧ℬ];
OverallAccuracyEqualityG=Pr[(OverHat[T])|T∧P]+Pr[¬(OverHat[T])|¬T∧P]==Pr[(OverHat[T])|T∧ℬ]+Pr[¬(OverHat[T])|¬T∧ℬ];
EqualizingDisincentivesG=Pr[(OverHat[T])|T∧P]-Pr[(OverHat[T])|¬T∧P]==Pr[(OverHat[T])|T∧ℬ]-Pr[(OverHat[T])|¬T∧ℬ];
TreatmentEqualityG=((Pr[(OverHat[T])|¬T∧P])/(Pr[¬(OverHat[T])|T∧P]))==((Pr[(OverHat[T])|¬T∧ℬ])/(Pr[¬(OverHat[T])|T∧ℬ]));

And, here is the generalized assumption of Unequal Base Rates.

UnequalBaseRatesG=Pr[T|P]≠Pr[T|ℬ];

Here is a verification of the generalized Chouldechova (2017) impossibility theorem.

PrSAT[
{
PredictiveParityG,
TruePositiveParityG,
FalsePositiveParityG,
StatisticalParityG,

UnequalBaseRatesG
},
BypassSearch->True
]

Here is a verification of the generalized Kleinberg et al (2016) impossibility theorem.

ImperfectClassifierG=And@@{Pr[(OverHat[T])|¬T∧P]≠0,Pr[(OverHat[T])|¬T∧ℬ]≠0,Pr[(OverHat[T])|T∧P]≠1,Pr[(OverHat[T])|T∧ℬ]≠1};
NonZeroPrecisionG=Pr[T|(OverHat[T])∧P]≠0∨Pr[T|(OverHat[T])∧ℬ]≠0;

PrSAT[
{
PredictiveParityG,
TruePositiveParityG,
FalsePositiveParityG,

UnequalBaseRatesG,
ImperfectClassifierG,
NonZeroPrecisionG
},
BypassSearch->True
]

The other two impossibilities discussed above also generalize in this fashion.

PrSAT[
{
StatisticalParityG,
TruePositiveParityG,
NegativePredictiveValueParityG,

UnequalBaseRatesG
},BypassSearch->True,Probabilities->Regular
]

PrSAT[
{
PredictiveParityG,
TruePositiveParityG,
TreatmentEqualityG,

UnequalBaseRatesG
},BypassSearch->True,Probabilities->Regular
]

Downloading this Mathematica Notebook

If you are reading a PDF version of this Mathematica notebook and you’d like to download the notebook itself, it is available at

	http://fitelson.org/exploring_impossibility.nb

References

Chouldechova, A. “Fair prediction with disparate impact: A study of bias in recidivism prediction instruments.” Big data 5.2 (2017): 153-163.

Fitelson, B. “A Decision procedure for Probability Calculus with Applications.” Review of Symbolic Logic 1.1 (2008): 111-125.

Kleinberg, J, S. Mullainathan, and M. Raghavan. “Inherent trade-offs in the fair determination of risk scores.” arXiv preprint arXiv:1609.05807 (2016).

Mehrabi, N., et al. “A survey on bias and fairness in machine learning.” arXiv preprint arXiv:1908.09635 (2019).

Caton, S., and C. Haas. “Fairness in Machine Learning: A Survey.” arXiv preprint arXiv:2010.04053 (2020).