# The Pok'emon Theorem and other Fairness Impossibility Results

arXiv: https://arxiv.org/abs/2605.09221 · HTML: https://mlsanity.com/paper/2605.09221/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 51 references that are in the map.
- First posted on arXiv 9 May 2026.

## Builds on (most cited first, 23 of 23)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Fair prediction with disparate impact: A study of bias in recidivism prediction instruments](https://mlsanity.com/paper/1610.07524/) (2016)
- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [Inherent Trade-Offs in the Fair Determination of Risk Scores](https://mlsanity.com/paper/1609.05807/) (2016)
- [Retiring Adult: New Datasets for Fair Machine Learning](https://mlsanity.com/paper/2108.04884/) (2021)
- [On Fairness and Calibration](https://mlsanity.com/paper/1709.02012/) (2017)
- [Learning Adversarially Fair and Transferable Representations](https://mlsanity.com/paper/1802.06309/) (2018)
- [Empirical Risk Minimization under Fairness Constraints](https://mlsanity.com/paper/1802.08626/) (2018)
- [The Variational Fair Autoencoder](https://mlsanity.com/paper/1511.00830/) (2015)
- [Multiaccuracy: Black-Box Post-Processing for Fairness in Classification](https://mlsanity.com/paper/1805.12317/) (2018)
- [Censoring Representations with an Adversary](https://mlsanity.com/paper/1511.05897/) (2015)
- [Inherent Tradeoffs in Learning Fair Representations](https://mlsanity.com/paper/1906.08386/) (2019)
- [Sobolev Norm Learning Rates for Regularized Least-Squares Algorithm](https://mlsanity.com/paper/1702.07254/) (2017)
- [50 Years of Test (Un)fairness: Lessons for Machine Learning](https://mlsanity.com/paper/1811.10104/) (2018)
- [Fairlearn: Assessing and Improving Fairness of AI Systems](https://mlsanity.com/paper/2303.16626/) (2023)
- [Fair Kernel Learning](https://mlsanity.com/paper/1710.05578/) (2017)
- [The Fairness-Accuracy Pareto Front](https://mlsanity.com/paper/2008.10797/) (2020)
- [FARE: Provably Fair Representation Learning with Practical Certificates](https://mlsanity.com/paper/2210.07213/) (2022)
- [The Possibility of Fairness: Revisiting the Impossibility Theorem in Practice](https://mlsanity.com/paper/2302.06347/) (2023)
- [Impossibility results for fair representations](https://mlsanity.com/paper/2107.03483/) (2021)
- [Mean Parity Fair Regression in RKHS](https://mlsanity.com/paper/2302.10409/) (2023)

## Abstract (arXiv)

Fairness impossibility results often look like distinct scalar incompatibility statements. We show that several share one RKHS geometry: fairness criteria are linear constraints on conditional mean embeddings, and unequal base rates make the law of total expectation overdetermine those constraints. This view yields four results. The Kleinberg--Mullainathan--Raghavan dichotomy needs only group-conditional unbiasedness, not full calibration. The Pok'emon theorem shows that a distinct group pair satisfying any finite collection of linear mean-fairness criteria leaves a residual violation witnessed by the MMD, decaying at the Kolmogorov m-width rate under spectral regularity. The same tools prove an impossibility for fair feature learning: parity and class-conditional separation in representation space force class collapse under unequal base rates. The approximate relaxations yield signal and error frontiers, allowing a trade-off between real-world estimators and fairness goals. Experiments on standard fairness benchmarks are consistent with our bounds.