🤖 machine learning

The Pokémon Theorem and other Fairness Impossibility Results

This paper unifies various fairness impossibility results under a shared RKHS geometry, demonstrating that unequal base rates cause linear fairness constraints to become overdetermined, which leads to new insights on the Kleinberg–Mullainathan–Raghavan dichotomy, a "Pokémon theorem" regarding residual violations measured by MMD, and fundamental limits on fair feature learning.

Original authors: Daniel Matsui Smola, Alex Smola

Published 2026-05-12

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Daniel Matsui Smola, Alex Smola

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Unfair" Math of Fairness

Imagine you are trying to build a machine that makes decisions (like approving loans or predicting if someone will re-offend) that are perfectly fair to two different groups of people, let's call them Group A and Group B.

For decades, researchers have argued about what "fair" actually means. Some say it means the machine makes the same number of mistakes for both groups. Others say it means the machine's predictions are equally accurate for both.

This paper argues that if Group A and Group B are fundamentally different in their real-world statistics (for example, if Group A has a higher rate of success than Group B naturally), you cannot satisfy all definitions of fairness at the same time. It's not just a bug in the code; it's a law of mathematics.

The authors use a fancy mathematical tool called RKHS (Reproducing Kernel Hilbert Space) to prove this. Think of RKHS as a giant, infinite-dimensional map where every possible way to measure "fairness" is a specific direction on the map.

1. The Stronger "KMR" Theorem: The "Average" Trap

The Old Idea: Previous research (Kleinberg, Mullainathan, Raghavan) showed that if you demand a machine be perfectly "calibrated" (its predictions match reality exactly) AND balanced across groups, you can't do it unless the groups are identical or the machine is a perfect crystal ball.

The New Insight: This paper says, "You don't even need perfect calibration to hit a wall."

The Analogy: Imagine you are a teacher grading two different classes. Class A has a natural average score of 80, and Class B has a natural average of 60.
The Rule: You promise that your grading system is "unbiased on average" (the average grade you give Class A matches their 80, and Class B matches their 60).
The Result: The paper proves that if you also demand that your grading system treats the "top students" and "bottom students" of both classes exactly the same way, your only option is to stop grading entirely and just guess the students' final scores based on who they are. You lose all ability to actually measure individual performance.
Takeaway: You can't have a system that is fair on average, treats subgroups equally, and still tells you anything useful about individuals, unless the groups are already identical.

2. The "Pokémon Theorem": You Can't Catch 'Em All

The Concept: This is the paper's most famous contribution. It addresses a common hope: "Maybe we just haven't checked enough fairness rules yet. If we check 10, or 100, or 1,000 rules, maybe we can prove the system is fair."

The Analogy: Imagine you are playing Pokémon. You have a list of "Fairness Checks" (like "Equal Error Rates," "Equal Approval Rates," etc.). You check your system against these rules.

The Catch: The paper proves that no matter how long your checklist is (even if it's 100 items), if Group A and Group B are different, there is always at least one more fairness rule you haven't checked that will fail.
The "MMD Witness": Think of the difference between the two groups as a hidden monster hiding in the shadows. Your checklist of 100 rules is like shining a flashlight in 100 different directions. If the monster is hiding in the 101st direction, your flashlight misses it.
The Decay: The paper calculates how fast this "hidden monster" gets smaller as you add more rules. It turns out that even with a huge number of rules, there is always a tiny, detectable "violation" left over. You can never fully "catch" the unfairness; you can only push it into a corner where it gets very small, but never zero.

3. The Impossibility of "Fair Feature Learning": The "Scrubbed" Signal

The Concept: Many modern AI researchers try to "fix" fairness by teaching the computer to forget the group identity (e.g., "Don't look at race or gender, just look at the skills"). They hope that if the computer doesn't see the group, it can't be biased.

The Analogy: Imagine you are trying to bake a cake (predict the outcome) using ingredients (features) that have been scrubbed clean of any "group flavor" (demographics).

The Problem: The paper proves that if the two groups have different natural success rates (different base rates), you cannot create a "scrubbed" version of the data that is:
1. Fair (looks the same for both groups).
2. Useful (still tells you who will succeed).
The Result: If you force the data to look identical for both groups, you accidentally erase the signal about who will succeed. The cake becomes flavorless. The computer learns that Group A and Group B are indistinguishable, so it stops being able to predict anything useful for anyone.
Takeaway: You can't have your cake and eat it too. If the groups are statistically different, trying to make the data "blind" to those differences destroys the ability to make accurate predictions.

4. The Trade-Off Frontier: The "Budget" of Fairness

The Concept: Since we can't achieve perfect fairness, what should we do? The paper suggests we treat fairness like a budget.

The Budget: The "budget" is the total amount of statistical difference between Group A and Group B.
Spending: Every time you enforce a fairness rule (like "Equal Error Rates"), you spend some of this budget.
The Frontier: The paper draws a line (a frontier) showing the trade-off. If you want to be very fair (spend a lot of the budget), your accuracy (error rate) must go up. If you want high accuracy, you must accept some unfairness.
The "Forbidden Corner": There is a specific area on the graph (low error + high fairness) that is mathematically impossible to reach. The paper shows that real-world experiments never enter this forbidden zone; they always stay on the "impossible" side of the line.

Summary

The paper uses advanced math to tell us a hard truth: If two groups of people are naturally different, no algorithm can be perfectly fair by every definition while still being useful.

You can't check enough rules to prove total fairness (Pokémon Theorem).
You can't scrub the data to hide the groups without destroying the useful information (Fair Feature Learning).
You have to choose a balance between how fair you want to be and how accurate you need to be (The Frontier).

The authors conclude that instead of hoping for a magic algorithm that fixes everything, we need to accept these mathematical limits and make policy decisions about which trade-offs are acceptable for society.

Technical Summary: The Pokémon Theorem and other Fairness Impossibility Results

Problem Statement

The paper addresses the fundamental limitations of algorithmic fairness, specifically investigating whether the known impossibility results (such as the Kleinberg–Mullainathan–Raghavan dichotomy) are artifacts of specific scalar criteria or inherent structural properties of distributions with unequal base rates. Two primary questions are posed:

Finite Checklist Limit: Can a finite collection of linear mean-fairness criteria (e.g., demographic parity, equalized odds) certify that two group distributions are identical, or will a residual violation always remain?
Representation Learning Limit: Can fair feature learning (learning an encoder that removes group information) circumvent these impossibilities by producing a representation where downstream predictors inherit fairness without sacrificing utility?

Existing literature often frames these impossibilities as conflicts between scalar statistics (e.g., calibration vs. error-rate balance). The authors argue that this scalar framing obscures the underlying geometric structure and leaves open whether "more" criteria could close the gap.

Methodology

The authors unify these fairness constraints using Reproducing Kernel Hilbert Spaces (RKHS) and mean embeddings.

RKHS Geometry: They model fairness criteria as linear constraints on conditional mean embeddings $\mu_{P} = \mathbb{E}[\phi(X)]$ within a Hilbert space $\mathcal{H}$ .
Characteristic Kernels: By using characteristic kernels, they ensure that distinct distributions map to distinct mean embeddings ( $\mu_P \neq \mu_Q \iff P \neq Q$ ).
Total Expectation Coupling: The core mechanism driving the impossibility results is the law of total expectation, which couples group-conditional expectations to the base-rate gap ( $\Delta p = p_a - p_b$ ).
Spectral Analysis: The paper employs spectral regularity assumptions (polynomial eigendecay of the pooled covariance operator and source conditions) to quantify the rate at which residual violations decay as the number of fairness criteria increases.

Key Contributions

1. Stronger KMR Theorem

The authors strengthen the classical Kleinberg–Mullainathan–Raghavan (KMR) impossibility result. They demonstrate that the contradiction between calibration and class-conditional balance holds even under the weaker condition of group-conditional unbiasedness ( $\mathbb{E}[S|G=g] = p_g$ ), rather than requiring full within-group calibration. This shows that miscalibrated scores that merely track the group average base rate are still subject to the impossibility.

2. The Pokémon Theorem

Named after the slogan "Gotta Catch 'Em All," this theorem addresses the finite checklist question.

Qualitative Result: For any distinct group pair ( $P_a \neq P_b$ ) and any finite set of linear mean-fairness criteria $\{v_1, \dots, v_m\}$ satisfied by the groups, there exists a residual violation in the orthogonal complement. This violation is witnessed by the Maximum Mean Discrepancy (MMD) witness vector $\delta / \|\delta\|_{\mathcal{H}}$ .
Quantitative Result: Under spectral regularity (polynomial eigendecay) and a source condition, the minimax residual violation decays at the Kolmogorov $m$ -width rate $\Theta(m^{-2\alpha r})$ . This implies that while adding more criteria reduces the worst-case violation, it never vanishes completely for a finite $m$ unless the distributions are identical.

3. Impossibility of Fair Feature Learning

The paper proves that fair representation learning cannot simultaneously achieve:

Distributional Parity: $\Phi(P_a) = \Phi(P_b)$ (the representation is group-invariant).
Class-Conditional Separation: The representation preserves distinct class-conditional distributions ( $\Phi(X) \perp\!\!\!\perp G | Y$ ).
Nontrivial Signal: The representation retains predictive power for the outcome $Y$ .

If base rates differ ( $p_a \neq p_b$ ), enforcing both distributional parity and class-conditional separation forces class collapse ( $\Phi(X) \perp\!\!\!\perp Y$ ), rendering the representation useless for prediction.

4. Approximate Fairness and the Pokémon–KMR Bridge

The authors derive quantitative bounds for approximate fairness:

Approximate Feature Learning: They establish a Pareto frontier where the usable downstream signal (class-conditional mean gap) is bounded by $(\epsilon + \rho) / |p_a - p_b|$ , where $\epsilon$ is the parity violation and $\rho$ is the separation violation.
Bridge to KMR: They show that as the number of audit criteria $m \to \infty$ and the residual violations vanish, the approximate conditions recover the exact KMR impossibility (perfect prediction is the only solution).

Experimental Results

The paper validates these theoretical bounds on standard fairness benchmarks (Adult Income, COMPAS, ACS PUMS):

Spectral Decay: Empirical plots of the residual MMD against the number of criteria $m$ confirm the polynomial decay rate predicted by the Pokémon theorem. The "budget" of MMD required to satisfy criteria varies by dataset (e.g., COMPAS concentrates faster due to lower dimensionality).
Pareto Frontiers: Empirical error vs. demographic parity gap plots for separation-enforcing classifiers align with the theoretical lower bound derived in Section 6.2.
Forbidden Region: Experiments with fair encoders (LFR, Fair-VAE, Adversarial Debiasing) show that no method successfully populates the "forbidden" upper-left region of the plot (low parity gap with high class-conditional signal), confirming the class collapse impossibility.

Significance and Claims

The paper claims to provide a unified geometric framework for fairness impossibility results.

Structural Insight: It reframes fairness impossibilities not as a conflict of specific scalar metrics, but as a structural consequence of the law of total expectation acting on distributions with unequal base rates.
Budget Allocation: It recasts fairness auditing as a budget-allocation problem where the total "budget" is the MMD between groups. Exact fairness requires exhausting this budget, which is impossible without sacrificing utility if base rates differ.
Practical Implication: The results suggest that when groups are distributionally distinct, algorithmic interventions alone cannot simultaneously achieve perfect fairness and utility. The paper implies that policy interventions or explicit treatment disparities may be necessary in such regimes, rather than relying solely on feature scrubbing or constraint optimization.

The authors maintain a modest stance, noting that their results are observational and do not propose new algorithms. Instead, they provide a theoretical "no-go" theorem that defines the boundaries of what is achievable in fair machine learning under unequal base rates.