Impossibility Theorem
Also known as: Fairness Impossibility Result, Fairness Trade-Off Theorem, Impossibility of Fairness
- Impossibility Theorem
- A mathematical proof that three group-fairness criteria — calibration, balance for the positive class, and balance for the negative class — cannot all be satisfied simultaneously unless the predictor is perfect or base rates are equal across groups.
The impossibility theorem proves that no algorithm can satisfy calibration, balance for the positive class, and balance for the negative class at the same time — unless predictions are perfect or group base rates are equal.
What It Is
When you run a bias audit on an ML model, one of the first things you discover is that fairness isn’t a single number. Multiple definitions of fairness exist, and the impossibility theorem explains why you can’t have all of them at once. This is the mathematical reason bias auditing requires deliberate choices, not just running a toolkit.
Think of it like a budget with three line items that always exceeds your total. No matter how you redistribute, you can’t fund all three at their full amount. The impossibility theorem says the same thing about fairness metrics: calibration (your risk scores mean what they say across all groups), balance for the positive class (truly positive individuals get similar scores regardless of group), and balance for the negative class (truly negative individuals also get similar scores across groups). You can’t satisfy all three at the same time.
According to Kleinberg et al., these three criteria can only coexist in two narrow scenarios: when the predictor has zero error, or when the base rates — the actual frequency of the outcome — are identical across groups. In practice, neither condition holds. Loan default rates differ across demographic groups, and recidivism rates vary by race and geography. The math doesn’t bend to good intentions.
Formalized in 2016 by Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan — with Chouldechova arriving at the same conclusion independently in 2017 — this result sets a hard boundary on what automated systems can achieve and directly shapes how practitioners use AI Fairness 360, Fairlearn, and the What-If Tool during bias audits.
How It’s Used in Practice
When auditing an ML model with tools like AI Fairness 360 or Fairlearn, the impossibility theorem is the reason the dashboard shows you multiple fairness metrics rather than one. Practitioners select which metric to prioritize based on domain and stakes. In hiring, you might prioritize demographic parity to ensure equal selection rates. In criminal justice, equalized odds might matter more because false positives carry severe consequences. The theorem tells you this choice is unavoidable, not a limitation of the tool.
Most audit workflows start by measuring several fairness criteria side by side, then documenting which were chosen and why. This documentation step isn’t bureaucracy — it’s a direct consequence of the impossibility theorem. If someone asks “why didn’t you optimize for all fairness metrics?”, the answer is mathematical: you can’t.
Pro Tip: When presenting audit results to stakeholders, lead with the impossibility theorem as context. It reframes the conversation from “our model is biased” to “we chose a fairness definition that fits our use case.” That shift makes the audit actionable instead of alarming.
When to Use / When Not
| Scenario | Use | Avoid |
|---|---|---|
| Choosing between competing fairness metrics during a bias audit | ✅ | |
| Explaining to stakeholders why a model can’t score perfectly on every metric | ✅ | |
| Deciding whether to prioritize calibration or equal error rates | ✅ | |
| Justifying trade-off documentation in compliance reviews | ✅ | |
| Building a model where groups have identical base rates | ❌ | |
| Evaluating individual-level fairness such as counterfactual fairness | ❌ |
Common Misconception
Myth: The impossibility theorem proves that fair AI is impossible, so there’s no point trying. Reality: The theorem proves you can’t satisfy every group-fairness definition at once. It doesn’t say fairness is unachievable — it says you must choose which definition of fairness fits your context. According to FAccT 2023, recent research even shows the theorem’s constraints may not bind in many practical settings, giving practitioners more room than the pure theory suggests.
One Sentence to Remember
The impossibility theorem doesn’t end the fairness conversation — it starts it, by forcing you to decide which version of fairness actually matters for your specific use case and then optimize for that deliberately.
FAQ
Q: Does the impossibility theorem apply to all machine learning models? A: It applies to any risk scoring system where groups have different base rates. Since most real-world datasets show unequal base rates across demographic groups, the theorem is relevant to nearly all practical bias audits.
Q: Can I still use multiple fairness metrics in an audit? A: Yes. Measure several metrics to understand the trade-offs, then document which one you prioritized and why. The theorem means you can’t perfectly satisfy all of them, but tracking multiple metrics reveals where the tensions lie.
Q: What’s the relationship between the impossibility theorem and tools like AI Fairness 360? A: These tools surface the theorem’s consequences by showing multiple fairness metrics side by side. They don’t resolve the trade-off — they make it visible so you can make an informed decision about which criteria to prioritize.
Sources
- Kleinberg et al.: Inherent Trade-Offs in the Fair Determination of Risk Scores - The foundational 2016 paper proving that calibration and balance cannot coexist when base rates differ
- FAccT 2023: The Possibility of Fairness: Revisiting the Impossibility Theorem in Practice - Recent research showing the theorem’s constraints may not apply in many practical settings
Expert Takes
The impossibility theorem is a clean mathematical result: three fairness properties, proven incompatible under mild assumptions. The proof structure shows that calibration plus equal false positive and false negative rates across groups requires either identical base rates or perfect classification. Neither holds in practice. For practitioners, this isn’t a conjecture or a heuristic. It’s a theorem. The constraint is structural, not something better data or larger models can overcome.
When you configure a bias audit in AI Fairness 360 or Fairlearn, the impossibility theorem is why the tool gives you a menu of metrics rather than a single score. The practical workflow: measure all three families of criteria, identify where they diverge, then lock in the one that matches your deployment context. Document that choice in your audit report. Every team that skips this step revisits it when a stakeholder asks why one metric looks bad.
The impossibility theorem is the reason fairness auditing is a strategic decision, not a technical checkbox. Organizations that treat bias audits as pass-fail exercises are missing the point. The real value is in the trade-off analysis — picking the right fairness definition for your market, your regulatory environment, and your risk tolerance. Teams that understand this move faster through compliance reviews because they can defend their choices with mathematical backing.
The impossibility theorem raises a question that math alone cannot answer: who decides which version of fairness a system optimizes for? The proof tells us a trade-off is inescapable, but it says nothing about whose values shape that trade-off. When a company chooses calibration over equal error rates, that’s not a neutral technical decision. It shifts risk from one group to another. The audit process should make that shift visible, not hide it behind metric names.