The Impossibility of Algorithmic Fairness

Two people can look at the same risk-scoring algorithm, run the numbers honestly, and reach opposite verdicts on whether it is fair, with both of them right. That is not a rhetorical trick or a case of one side fudging the data. It is a mathematical fact about what happens when a predictor is scored against two groups that reoffend at different rates. The COMPAS case made it famous: journalists proved the tool was biased, the vendor proved it was not, and the uncomfortable resolution is that the two proofs measure different things that cannot both be equalized at once. Fairness, it turns out, is not a single property a system either has or lacks. It is a set of criteria that pull against each other, and the pulling is provable.

The idea

In 2016 ProPublica found that among defendants who did not go on to reoffend, Black defendants were labeled high-risk almost twice as often as white defendants: an unequal false-positive rate. Northpointe, the vendor, replied that COMPAS was calibrated: among everyone assigned the same risk score, the same fraction actually reoffended regardless of race, so a score meant the same thing for each group. Both claims are true. The reason they cannot be fixed together is a theorem, proved independently by Chouldechova (2017) and by Kleinberg, Mullainathan and Raghavan (2016): when the base rates differ between groups, calibration and equal false-positive and false-negative rates cannot all hold at once, except in degenerate cases like a perfect predictor or identical base rates. So there is no fair algorithm in the sense of satisfying every reasonable fairness criterion. There is only a choice about which criterion to sacrifice, and that choice is normative, not technical.

The COMPAS collision

COMPAS is a proprietary tool that scores criminal defendants on their risk of reoffending, and its output feeds bail, sentencing, and parole decisions. In May 2016, ProPublica published an analysis of over 7,000 arrests in Broward County, Florida, and reported that the tool’s errors fell unequally by race. Among defendants who did not reoffend within two years, 44.9% of Black defendants had been labeled higher risk against 23.5% of white defendants. In ProPublica’s own phrasing, Black defendants were “almost twice as likely as whites to be labeled a higher risk but not actually re-offend.” That gap is a false-positive-rate disparity: the cost of the algorithm’s mistakes was landing harder on one group.

Northpointe, the company behind COMPAS, answered with a different statistic and did not dispute ProPublica’s numbers. It argued the tool satisfied predictive parity, also called calibration: for any given risk score, the actual reoffense rate was roughly the same for Black and white defendants, so a “7” meant the same empirical thing no matter who received it. As the plain-language summary of the fight puts it, both statements are true because they refer to two mutually exclusive definitions of fairness, one measuring the rate of classification errors and the other measuring the accuracy of the score as a prediction. Neither side was lying. They had quietly picked different definitions of the word “fair,” and the definitions turned out to be incompatible.

Why they cannot both hold

The incompatibility is not a coincidence of this dataset. It falls straight out of the confusion matrix once the two groups reoffend at different underlying rates, which they did in the data. Read the two fairness demands carefully and they are constraints on different conditional probabilities, related by Bayes’ rule and pinned apart by the base rate. Calibration is a statement about the score’s meaning: it fixes P(reoffends | score, group), demanding that a given score carry the same reoffense probability in each group. Error-rate balance is a statement about the score’s mistakes: it fixes P(high-risk | did not reoffend, group) and its counterpart for those who did, demanding equal false-positive and false-negative rates across groups. These are different conditional probabilities, conditioned on different things, and the base rate P(reoffends | group) is the hinge that connects them.

Here is the mechanism. Suppose you have forced calibration, so a score means the same reoffense probability in both groups. Now let group A reoffend more often than group B overall. Because A has more genuine reoffenders to find, a calibrated score that correctly identifies reoffenders in A will also sweep up more of A’s non-reoffenders into the high-risk bin along the way, simply because there is a denser population of true positives sitting near any given threshold. The false-positive rate among A’s non-reoffenders comes out higher than among B’s, not from malice in the model but from arithmetic: the same score threshold, applied to two populations with different proportions of reoffenders, produces different error rates on each side. The only ways out are the degenerate ones. If the predictor is perfect it makes no errors, so all error rates are zero and trivially equal. If the two base rates are identical there is no asymmetry for the error rates to inherit. Outside those corners, calibration and error-rate balance are mathematically exclusive.

That is exactly what the theorems say. Chouldechova’s 2017 paper states it in one line: the criteria “cannot all be simultaneously satisfied when recidivism prevalence differs across groups.” Kleinberg, Mullainathan and Raghavan reach the same wall from the score-design side, proving that “except in highly constrained special cases, there is no method that can satisfy these three conditions simultaneously.” The general form appears even in the summary literature: independence, separation, and sufficiency cannot jointly hold except in trivial cases, so what some call total fairness is not achievable. The upshot for any real risk tool is stark. Different groups almost always have different base rates, so almost every deployed classifier is forced to violate at least one fairness criterion, and the engineer’s job is not to eliminate the tradeoff but to choose where it lands.

The normative layer: which unfairness is the unfair one

The theorem tells you the criteria conflict. It does not tell you which one is the real measure of fairness, and that question is not mathematical. Two philosophers stake out opposite ends of it, and the argument connects this note to fairness as equal concern and the governance stakes in AI governance.

Brian Hedden argues that calibration within groups is the one criterion genuinely necessary for fairness, and that the others, including equal false-positive rates, are not. His move is a thought experiment: he builds a case with people flipping biased coins in two rooms, where the coins in one room cluster near 0 and 1 and the coins in the other cluster near 0.5, so the two groups have very different distributions even when their average is arranged to match. A single obviously fair and optimal predictor, applied to both rooms, violates most of the standard fairness metrics purely because the underlying distributions differ, while calibration survives. If a manifestly fair predictor can fail equal-FPR, then equal-FPR cannot be a necessary condition of fairness. Hedden’s conclusion is that most group-fairness constraints in the machine-learning literature are not necessary conditions for the fairness of predictions, a claim he proves by exhibiting that special case.

Deborah Hellman pushes from the other direction, and reframes what the ProPublica statistic is even telling us. Calibration, she argues, is about what you ought to believe about a scored person: it guarantees a score means the same thing as evidence for each group. But fairness is usually about what you ought to do, and belief and action are different domains. In her words, Northpointe’s measure “relates to what we ought to believe about a particular scored individual,” while ProPublica’s “relates instead to what we ought to do.” So predictive parity, being about belief, is ill-suited as the measure of fairness in the first place. That does not make the error-rate disparity decisive either. Hellman treats a lack of error-ratio parity as a signal rather than a proof: it “suggests that something is likely amiss” and that “the algorithm may be compounding a prior injustice.” The disparity is an alarm that obliges you to investigate whether the unequal base rates are themselves the residue of earlier wrongs, biased policing inflating one group’s arrest rate, for instance, so that a base rate you feed the model as neutral ground truth is actually laundered injustice. On that view the impossibility theorem is not the end of the ethics. It is where the ethics starts.

The confusion matrix, made concrete

Take a stylized version of the Broward pattern. Say group A reoffends at 50% and group B at 25%, and a calibrated score is applied to both.

1. Calibration holds. Pick everyone the model scored “high risk.” In both groups, the same fraction of those people actually reoffended. The score means the same thing on each side. Northpointe is satisfied.
2. The false-positive rates split. Now look only at the people who did not reoffend. In group A, with its larger pool of true reoffenders crowding the high-risk region, more of the non-reoffenders got swept into “high risk” too. Their false-positive rate is higher than group B’s. ProPublica is alarmed. (In the real data: 44.9% versus 23.5%.)
3. You cannot fix both. Lower A’s false-positive rate by raising its threshold and you break calibration, because a given score now means different reoffense probabilities in A and B. Restore calibration and the error gap returns. The base-rate difference guarantees it.
4. The escape hatches are unreal. Equal error rates and calibration reconcile only if the model is a perfect oracle, or if both groups reoffend at exactly the same rate. Neither is true of any real population, which is why the tradeoff is unavoidable rather than a bug someone can patch.

Related Notes

• Bayes’ Rule, the identity that ties a score’s meaning to its error rates through the base rate, which is why calibration and error-rate balance cannot move independently
• Conditional Probability, the language in which the conflicting fairness criteria are actually stated
• Fairness as Equal Concern, the deeper normative question the theorem hands off to once the statistics run out
• Social Categories and Machine Learning, where the base rates the model treats as ground truth may already encode prior injustice
• AI Governance, the policy problem of choosing which fairness criterion a deployed system is allowed to sacrifice
• Hypothesis Testing, the same confusion-matrix machinery of false positives and false negatives, seen in its statistical home

Sources

• “Machine Bias,” ProPublica, May 23 2016. https://www.propublica.org/article/machine-bias-risk-assessments-in-criminal-sentencing . Supports the COMPAS case, the Broward County analysis of over 7,000 arrests, and the exact figures: 44.9% of Black defendants versus 23.5% of white defendants were labeled higher risk but did not reoffend, “almost twice as likely.”
• “COMPAS (software),” Wikipedia. https://en.wikipedia.org/wiki/COMPAS_%28software%29 . Supports that ProPublica found COMPAS racially biased against Black defendants, that Northpointe responded that the algorithm predicted recidivism accurately regardless of race, and that “both statements are true: they refer to two mutually exclusive definitions of fairness,” one about classification-error rates and one about predictive accuracy.
• Chouldechova, “Fair prediction with disparate impact: A study of bias in recidivism prediction instruments,” 2017. https://arxiv.org/abs/1703.00056 . Supports the impossibility result in its own words: the criteria “cannot all be simultaneously satisfied when recidivism prevalence differs across groups.”
• Kleinberg, Mullainathan & Raghavan, “Inherent Trade-Offs in the Fair Determination of Risk Scores,” 2016. https://arxiv.org/abs/1609.05807 . Supports the independent proof that “except in highly constrained special cases, there is no method that can satisfy these three conditions simultaneously.”
• “Fairness (machine learning),” Wikipedia. https://en.wikipedia.org/wiki/Fairness_%28machine_learning%29 . Supports the general statement of the incompatibility: independence, separation, and sufficiency cannot all hold together (“total fairness is not possible to achieve except in specific rhetorical cases”), the confusion-matrix framing, and the calibration-versus-error-rate-balance conflict.
• Hedden, “On statistical criteria of algorithmic fairness,” Philosophy & Public Affairs, vol. 49 no. 2 (2021), pp. 209-231. https://onlinelibrary.wiley.com/doi/10.1111/papa.12189 . Supports the argument that calibration within groups is the only standard statistical criterion that is a genuine necessary condition of fairness, established via the two-rooms coin-flipping example in which a manifestly fair, optimal predictor violates the other criteria because the groups have different underlying distributions.
• Eva, “People are not coins: Morally distinct types of predictions necessitate different fairness constraints,” 2022. https://arxiv.org/abs/2204.10305 . Open-access corroboration of Hedden’s central claim, stating that Hedden (2021) “has argued that most of the group fairness constraints discussed in the machine learning literature are not necessary conditions for the fairness of predictions,” proven by discussing a special case.
• Hellman, “Measuring Algorithmic Fairness,” Virginia Law Review, vol. 106 (2020). https://www.virginialawreview.org/articles/measuring-algorithmic-fairness/ . Supports that predictive parity “relates to what we ought to believe about a particular scored individual” while the error-rate measure “relates instead to what we ought to do,” that equal predictive accuracy is therefore ill-suited as a measure of fairness, and that an error-ratio disparity “suggests that something is likely amiss” and that “the algorithm may be compounding a prior injustice,” making it a signal rather than proof of unfairness.