Summary

In 2016 ProPublica published an investigation showing that COMPAS — a widely used recidivism risk assessment tool — labelled Black defendants who did not reoffend as high-risk about twice as often as White defendants who did not reoffend. The tool’s developer responded that COMPAS is well-calibrated: among defendants of any race assigned a given score, the subsequent recidivism rates are consistent with that score. Both claims were correct descriptions of the same data.

The apparent contradiction is illuminated by mathematical results published in 2017. For a thresholded binary classifier with unequal group prevalences, predictive parity and equal false-positive and false-negative rates cannot all hold simultaneously, except in degenerate cases. A related result for calibrated risk scores reaches a closely connected trade-off.

This is not a property of COMPAS specifically. It is not fixed by a better algorithm, more diverse training data, or more careful engineering alone. It is a constraint on specified statistical criteria for non-degenerate predictions when the relevant base rates differ.

The question this forces is not “how do we make the algorithm fair?” The question is “which fairness criterion do we endorse, and can we defend that choice to the people it disadvantages?” That is not a technical question.

The COMPAS Investigation

Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner published “Machine Bias” in ProPublica on 23 May 2016 [[1]]. They had obtained COMPAS risk scores for approximately 7,000 defendants in Broward County, Florida, along with actual two-year recidivism data. Their finding: among defendants who did not go on to reoffend, Black defendants were falsely labelled higher-risk at roughly twice the rate of White defendants, 45% against 23%, counting every score above “low” as higher risk. Among those who did reoffend, the error ran the other way: 48% of White and 28% of Black defendants had been labelled lower risk [[2]].

Northpointe (now Equivant), the tool’s developer, responded that ProPublica’s analysis was misleading. COMPAS is calibrated: within any given score band, the actual recidivism rate is the same regardless of race. A score of 7 means approximately the same thing for a Black defendant as for a White defendant. This is a genuine and important property for a risk assessment to have. At ProPublica’s threshold the positive predictive values were also close: 0.63 for Black and 0.59 for White defendants [[2]]. The two-year recidivism rates were not: 51% and 39% [[3]].

The two analyses addressed different quantities and choices of threshold, outcome and data have been debated. The important point is not that either headline settles COMPAS fairness; it is that several legitimate statistical criteria can conflict.

Four Reasonable Definitions

Let \(Y \in \{0, 1\}\) be the true outcome (reoffend/not), \(\hat{Y}\) be the classifier’s prediction, and \(A \in \{0, 1\}\) indicate group membership.

Calibration: for all score values \(s\),

$$P(Y = 1 \mid \hat{Y} = s, A = 0) = P(Y = 1 \mid \hat{Y} = s, A = 1)$$

If the model assigns a score of 7 to a defendant, the observed reoffending rate should be the same regardless of race. This is a property of a score, rather than of a thresholded decision.

For a binary decision, predictive parity instead requires equal positive predictive values:

$$P(Y = 1 \mid \hat{Y} = 1, A = 0) = P(Y = 1 \mid \hat{Y} = 1, A = 1).$$

False positive rate parity:

$$P(\hat{Y} = 1 \mid Y = 0, A = 0) = P(\hat{Y} = 1 \mid Y = 0, A = 1)$$

Among defendants who will not reoffend, the probability of being incorrectly labelled high-risk should be equal across groups. This is what ProPublica found violated.

False negative rate parity:

$$P(\hat{Y} = 0 \mid Y = 1, A = 0) = P(\hat{Y} = 0 \mid Y = 1, A = 1)$$

Among defendants who will reoffend, the probability of being incorrectly labelled low-risk should be equal across groups.

All four seem like reasonable things to ask of a fair classifier. The binary impossibility result concerns predictive parity together with the two error-rate conditions above. The calibrated-score result uses different, though related, conditions.

The Impossibility Theorem

Alexandra Chouldechova proved the binary result in 2017, using the Broward County data as her case study [[3]]. Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan independently proved a related result for calibrated risk scores [[4]].

The argument is short. Suppose a classifier produces a binary prediction (high/low risk). In a group of $n$ people with base rate $p$ — the proportion who actually reoffend — write the confusion-matrix counts as $\mathrm{TP}$, $\mathrm{FP}$, $\mathrm{FN}$, $\mathrm{TN}$. The positive predictive value $\mathrm{PPV} = \mathrm{TP}/(\mathrm{TP} + \mathrm{FP})$ gives $\mathrm{FP} \cdot \mathrm{PPV} = \mathrm{TP} \cdot (1 - \mathrm{PPV})$. Substituting $\mathrm{FP} = \mathrm{FPR}\,(1-p)\,n$ and $\mathrm{TP} = (1 - \mathrm{FNR})\,p\,n$ and dividing by $n$,

$$\mathrm{FPR} \cdot \mathrm{PPV} \cdot (1 - p) = p \cdot (1 - \mathrm{PPV}) \cdot (1 - \mathrm{FNR}). \tag{1}$$

For $\mathrm{PPV} > 0$ this is Chouldechova’s $\mathrm{FPR} = \frac{p}{1-p}\,\frac{1-\mathrm{PPV}}{\mathrm{PPV}}\,(1 - \mathrm{FNR})$.

Now give two groups with base rates $p_0 \neq p_1$ the same PPV, the same FPR and the same FNR. Writing Eq. (1) for both groups and subtracting gives

$$(p_1 - p_0)\,\bigl[\mathrm{FPR} \cdot \mathrm{PPV} + (1 - \mathrm{PPV})(1 - \mathrm{FNR})\bigr] = 0.$$

Both terms in the bracket are non-negative, so with $p_0 \neq p_1$ both must vanish: $\mathrm{FPR} \cdot \mathrm{PPV} = 0$ and $(1 - \mathrm{PPV})(1 - \mathrm{FNR}) = 0$. The three conditions can therefore hold together only if either:

  1. $p_0 = p_1$: the base rates are equal;
  2. $\mathrm{FPR} = 0$: the classifier makes no false positives at all, whatever its false negative rate (a perfect classifier is the special case with $\mathrm{FNR} = 0$ as well); or
  3. $\mathrm{FNR} = 1$: it flags none of the people who reoffend.

Cases 2 and 3 are degenerate for any instrument used in practice. Call a classifier non-degenerate if it makes at least one false positive and catches at least one reoffender. For a non-degenerate classifier with unequal base rates, predictive parity and equalised error rates are mutually exclusive. Geometrically, a common PPV strictly between 0 and 1 puts each group on its own straight line of possible error rates, and the lines meet only in the degenerate corner (Fig. 1).

Figure 1. With equal predictive values, groups with different base rates live on different lines of error rates. Each line is Eq. (1) for $\mathrm{PPV} = 0.61$, between the two observed values, at the base rates reported in [[3]]; the lines meet only at $\mathrm{FNR} = 1$, $\mathrm{FPR} = 0$. Points: COMPAS at ProPublica’s “higher risk” threshold [[2]], whose own predictive values (0.63 and 0.59) put them slightly off the drawn lines.

Read the other way, the identity says that equal error rates force the predictive values apart. With the same true positive rate and false positive rate in both groups, both nonzero, $\mathrm{PPV} = \mathrm{TPR}\,p / (\mathrm{TPR}\,p + \mathrm{FPR}\,(1-p))$ rises with the base rate. At a true positive rate of 0.7 and a false positive rate of 0.3, base rates of 0.39 and 0.51 give positive predictive values of 0.60 and 0.71 (Fig. 2).

Figure 2. Equal nonzero error rates give unequal predictive values whenever base rates differ. Two illustrative classifiers with the same error rates in both groups; the highlighted points are the Broward base rates on the solid curve.

A calibrated continuous score faces an analogous conflict. Kleinberg, Mullainathan and Raghavan formalise calibration within groups and balance for the positive and negative classes, and show that the three can hold together only under perfect prediction or equal base rates [[4]]. These are algebraic constraints, not an engineering limitation.

A Structural Analogy

The structural similarity to another impossibility result is worth noting.

The Robertson inequality in quantum mechanics [[5]] states that for any two observables \(\hat{A}\) and \(\hat{B}\):

$$\Delta A \cdot \Delta B \geq \frac{1}{2} \left| \langle [\hat{A}, \hat{B}] \rangle \right|$$

This is not an engineering failure. It is a consequence of the algebraic structure of the theory: wherever the commutator has a nonzero expectation value, \(\Delta A\) and \(\Delta B\) cannot simultaneously be made arbitrarily small. For position and momentum the commutator is the constant \(i\hbar\), so the bound holds in every state. No measurement apparatus, however precise, can violate it. The constraint is in the mathematics, not the hardware.

The fairness impossibility has the same character: specified desiderata, a structural constraint that prevents simultaneous satisfaction, and no purely algorithmic escape route. A better model may reduce error, but it does not remove the trade-off unless it reaches one of the degenerate cases. The constraint is in conditional probabilities and base rates.

The disanalogy is this: in quantum mechanics, \(\hbar\) is a fundamental constant — you cannot reduce it. In fairness, the base rates are not constants of nature. They are historical outcomes of social processes: incarceration rates, policing patterns, economic conditions, educational access. The theorem does not tell you that unequal base rates are acceptable; it tells you that given unequal base rates, the three fairness criteria cannot all be satisfied by a non-degenerate classifier.

Gender Bias in AI Systems

The theorem is about a defined prediction task and defined group statistics. The empirical landscape of AI gender bias is relevant, but it is not a set of automatic applications of that theorem: each system requires its own target, population, measurement and error analysis.

In October 2018, Reuters reported that Amazon had developed and then abandoned an internal AI-based recruiting tool that systematically downgraded résumés from women [[6]]. The model had been trained on a decade of hiring decisions, in which successful hires were predominantly male. The model learned that “male” features were associated with success and penalised female indicators accordingly. Reuters’ account is reporting, not a public technical audit; it cannot establish the tool’s calibration or a general theorem about hiring.

Tolga Bolukbasi and colleagues showed in 2016 that word embeddings trained on large text corpora encoded gender stereotypes in their geometric structure [[7]]. The analogy \(\text{man} : \text{computer programmer} :: \text{woman} : \text{homemaker}\) could be recovered directly from the vector arithmetic of the embedding space. The result shows that embeddings can encode and reproduce corpus associations; it does not show calibration in the risk-score sense used above.

Jieyu Zhao and colleagues found that visual semantic role labelling and multilabel object classification models amplified existing gender associations [[8]]. “Cooking” was associated with women in 67% of training images; the models amplified that to 84% at inference. The result is measured bias amplification under that dataset and evaluation; it should not be read as an application of the recidivism impossibility theorem.

Joy Buolamwini and Timnit Gebru’s “Gender Shades” study found error rates of up to 34.7% for darker-skinned women in commercial gender-classification systems, compared to 0.8% for lighter-skinned men [[9]]. The study did not establish the vendors’ training data or score calibration; it measured an intersectional error disparity.

Hadas Kotek and colleagues tested four large language models on gender-stereotyped occupational prompts in 2023 [[10]]. The models were three to six times more likely to choose the gender-stereotyped occupation when responding to ambiguous prompts. The result is evidence of stereotype-sensitive model behaviour, not evidence that the models were calibrated in the statistical sense used here.

The Solutions and Their Limits

Three broad approaches exist to algorithmic debiasing, and all three face the same constraint.

Pre-processing removes bias from training data before training. Zemel and colleagues proposed “Learning Fair Representations” — a latent embedding that encodes the data usefully while obscuring group membership [[11]]. This can reduce bias in the learned representation, but it does not select a universally fair outcome or escape incompatible criteria in settings where the theorem applies.

Post-processing adjusts the classifier’s decisions after training. Moritz Hardt, Eric Price, and Nathan Srebro’s equalized odds approach [[12]] adjusts decision thresholds separately per group, randomising between two thresholds where necessary, to achieve FPR/FNR parity. This satisfies equalized odds by construction; for a non-degenerate classifier with unequal base rates, it cannot also retain predictive parity. Calibration of an underlying score is a separate question.

In-processing incorporates a fairness constraint into the training objective. Agarwal and colleagues reduce fair classification to a sequence of cost-sensitive problems: the practitioner states the constraint, demographic parity and equalized odds among them, and receives a randomised classifier with the lowest empirical error that satisfies it approximately [[13]]. But you must choose. No such method can deliver predictive parity and equal error rates together for a non-degenerate classifier when base rates differ.

Mitchell and colleagues describe the assumptions and value choices behind competing definitions [[14]]. The choice of objective and intervention has distributional consequences that fall differently on different groups.

The Political Choice

This is where Arvind Narayanan’s framing becomes essential. His 2018 tutorial catalogued 21 distinct definitions of algorithmic fairness and titled it “21 Fairness Definitions and Their Politics” [[15]]. The title is the argument: the definitions are not equivalent, choosing among them is not a technical decision, and the choice encodes a prior about what justice requires.

In the criminal justice context: a false positive (predicting recidivism when the defendant will not reoffend) imposes a cost on the defendant — higher bail, longer sentence, restricted conditions of release. A false negative (predicting non-recidivism when the defendant will reoffend) imposes a cost on potential future victims and on public safety. Insisting on equal false positive rates protects defendants in every group equally from false accusation. Insisting on equal false negative rates spreads the risk of a missed offender equally. These are both defensible values. They produce different error distributions across groups.

Choosing overall accuracy as the metric — which is what maximising predictive performance typically means — is itself a value choice: it implicitly weights errors by their frequency in the population, which means errors made on less-common outcomes are relatively under-penalised. When racial disparities in base rates are products of historical injustice, this choice compounds that injustice.

Solon Barocas, Moritz Hardt, and Arvind Narayanan’s textbook Fairness and Machine Learning (2023) makes explicit that the choice between fairness criteria is a normative, not technical, decision [[16]]. The book does not tell you which criterion to choose. It tells you that you must choose, that the choice has political content, and that presenting it as a technical optimisation problem conceals that content.

Reuben Binns reads the same debate through egalitarian political philosophy, from luck egalitarianism to Parfit’s deontic egalitarianism [[17]]. He does not rank the criteria. For COMPAS he suggests that a deontic perspective directs attention to the historical reasons for the unequal base rates, while conceding that this “may not in itself directly resolve the question of which fairness metric ought to apply”. My own reading goes one step further: the choice of fairness criterion carries a theory of justice, whether or not the engineers implementing the system have thought of it in those terms.

The Theorem Is Not the Problem

I want to be clear about what the impossibility theorem does and does not say.

It does not say that algorithmic fairness is impossible. It says that you must choose among competing fairness criteria when base rates differ across groups, and that the choice has distributional consequences. Systems can be built that satisfy predictive parity, or equalized odds — just not both at once for a non-degenerate classifier with unequal base rates.

It does not say that base rate disparities are natural or acceptable. The disparities in recidivism rates, hiring rates, image training sets, and text corpora are products of social history. The theorem constrains what a classifier can do given those disparities; it does not prescribe them.

What it does say is that “we built a fair algorithm” is not a statement that can be made without specifying which fairness criterion was satisfied and which was not. It is not a statement that can be defended on purely technical grounds. And it is not a statement that escapes political accountability by hiding behind mathematical precision.

The fairness debate in AI is, in part, a debate about which errors we are willing to make, in whom, with what consequences. The theorem makes that debate unavoidable. Whether we have the vocabulary and the will to conduct it in those terms is a different question entirely.

Literature and calculations checked through 2026-10-24.

References

[1] Angwin, J., Larson, J., Mattu, S., & Kirchner, L. (2016, May 23). Machine bias. ProPublica. https://www.propublica.org/article/machine-bias-risk-assessments-in-criminal-sentencing

[2] Larson, J., Mattu, S., Kirchner, L., & Angwin, J. (2016, May 23). How we analyzed the COMPAS recidivism algorithm. ProPublica. https://www.propublica.org/article/how-we-analyzed-the-compas-recidivism-algorithm

[3] Chouldechova, A. (2017). Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big Data, 5(2), 153–163. DOI: 10.1089/big.2016.0047

[4] Kleinberg, J., Mullainathan, S., & Raghavan, M. (2017). Inherent trade-offs in the fair determination of risk scores. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). DOI: 10.4230/LIPIcs.ITCS.2017.43

[5] Robertson, H. P. (1929). The uncertainty principle. Physical Review, 34, 163–164. DOI: 10.1103/PhysRev.34.163

[6] Dastin, J. (2018, October 10). Amazon scraps secret AI recruiting tool that showed bias against women. Reuters. https://www.reuters.com/article/us-amazon-com-jobs-automation-insight-idUSKCN1MK08G

[7] Bolukbasi, T., Chang, K.-W., Zou, J., Saligrama, V., & Kalai, A. (2016). Man is to computer programmer as woman is to homemaker? Debiasing word embeddings. In Advances in Neural Information Processing Systems 29 (NeurIPS 2016). arXiv:1607.06520

[8] Zhao, J., Wang, T., Yatskar, M., Ordonez, V., & Chang, K.-W. (2017). Men also like shopping: Reducing gender bias amplification using corpus-level constraints. In Proceedings of EMNLP 2017, pp. 2979–2989. ACL Anthology: D17-1323

[9] Buolamwini, J., & Gebru, T. (2018). Gender shades: Intersectional accuracy disparities in commercial gender classification. In Proceedings of the 1st Conference on Fairness, Accountability and Transparency (FAT* 2018), PMLR Vol. 81, pp. 77–91. https://proceedings.mlr.press/v81/buolamwini18a.html

[10] Kotek, H., Dockum, R., & Sun, D. Q. (2023). Gender bias and stereotypes in large language models. In Proceedings of The ACM Collective Intelligence Conference (CI ‘23), pp. 12–24. DOI: 10.1145/3582269.3615599

[11] Zemel, R., Wu, Y., Swersky, K., Pitassi, T., & Dwork, C. (2013). Learning fair representations. In Proceedings of the 30th International Conference on Machine Learning (ICML 2013), PMLR Vol. 28, No. 3, pp. 325–333. https://proceedings.mlr.press/v28/zemel13.html

[12] Hardt, M., Price, E., & Srebro, N. (2016). Equality of opportunity in supervised learning. In Advances in Neural Information Processing Systems 29 (NeurIPS 2016), pp. 3315–3323. arXiv:1610.02413

[13] Agarwal, A., Beygelzimer, A., Dudik, M., Langford, J., & Wallach, H. (2018). A reductions approach to fair classification. In Proceedings of the 35th International Conference on Machine Learning (ICML 2018), PMLR Vol. 80, pp. 60–69. arXiv:1803.02453

[14] Mitchell, S., Potash, E., Barocas, S., D’Amour, A., & Lum, K. (2021). Algorithmic fairness: Choices, assumptions, and definitions. Annual Review of Statistics and Its Application, 8, 141–163. DOI: 10.1146/annurev-statistics-042720-125902

[15] Narayanan, A. (2018). 21 Fairness Definitions and Their Politics. Tutorial at FAT* 2018. PDF

[16] Barocas, S., Hardt, M., & Narayanan, A. (2023). Fairness and Machine Learning: Limitations and Opportunities. MIT Press. https://fairmlbook.org

[17] Binns, R. (2018). Fairness in machine learning: Lessons from political philosophy. In Proceedings of the 2018 Conference on Fairness, Accountability, and Transparency (FAT* 2018), PMLR Vol. 81, pp. 149–159. arXiv:1712.03586


Changelog

  • 2025-11-05: Updated the Zhao et al. (2017) cooking statistics to match the paper: 67% female agents for cooking in the training set (33% was the male share), amplified to 84% female at inference.
  • 2026-07-11: Distinguished score calibration from binary predictive parity and equalised error rates; narrowed the COMPAS and AI-bias examples to their measured claims and corrected the description of Gender Shades as gender classification rather than facial recognition.
  • 2026-10-03: Replaced “calibration, equalized odds, or demographic parity” with the criteria the article actually defines (predictive parity and equalised error rates cannot both hold); corrected the page range of Hardt et al. (2016) to 3315-3323.
  • 2026-10-24: Corrected the exceptions to the impossibility result. With unequal base rates, predictive parity and equal error rates can coexist only if the classifier makes no false positives (any false negative rate) or catches no reoffenders; the article previously named only the perfect classifier, FPR = FNR = 0. Derived the identity, Eq. (1), and replaced “imperfect” with “non-degenerate” in the summary and text. Added ProPublica’s error rates and predictive values and Chouldechova’s base rates (51% and 39%), and two figures: the error-rate lines that a common PPV allows at each base rate (Fig. 1), and the predictive values that equal error rates force apart (Fig. 2). Changed Kleinberg et al.’s result from “equivalent” to related. Corrected the Robertson analogy: the bound constrains both spreads only where the commutator’s expectation is nonzero. Restated Binns (2018), who does not rank the criteria, and Agarwal et al. (2018), whose method takes constraints such as demographic parity and equalized odds, not “any one of the three criteria”; noted that equalized odds may need randomised thresholds. Corrected the tasks in Zhao et al. (2017): semantic role labelling and multilabel object classification, not captioning and activity recognition. Citations are now numbered and linked, with ProPublica’s methodology article added as [2].