Skip to content

The Pokémon Theorem and other Fairness Impossibility Results

Conference: NeurIPS 2026
arXiv: 2605.09221
Area: Safety Keywords: Algorithmic Fairness, Reproducing Kernel Hilbert Space (RKHS), Maximum Mean Discrepancy (MMD), Impossibility Theorem, Fair Representation Learning

TL;DR

This paper unifies classic algorithmic fairness impossibility theorems within the geometric framework of conditional mean embeddings in Reproducing Kernel Hilbert Spaces (RKHS), establishes the Pokémon Theorem showing that any finite set of linear fairness criteria inevitably leaves residual MMD violations in the orthogonal complement, and theoretically establishes the impossibility of fair feature learning due to class collapse under unequal base rates.

Background & Motivation

Fairness definitions in algorithmic decision-making have undergone intense debates over the past half-century. From early formalizations aimed at eliminating bias in educational and employment testing to modern machine learning trade-offs among calibration, demographic parity, and equalized odds, researchers have introduced several well-known impossibility theorems. Prominent classical results, such as the Kleinberg-Mullainathan-Raghavan (KMR) theorem and Chouldechova's dichotomy, indicate that when base rates differ across demographic groups, within-group calibration and class-conditional balance (matching false positive and false negative error rates) cannot be simultaneously satisfied by non-trivial predictors. However, these classical proofs rely almost entirely on algebraic manipulations of scalar statistical metrics, leaving two fundamental questions unresolved in practice: first, are these impossibilities mere artifacts of the specific chosen scalar metrics, or do they hold for any arbitrary finite checklist of linear fairness audits? Second, can fair representation learning—which attempts to strip sensitive demographic attributes via learned encoders—allow downstream tasks to inherit fairness for free and bypass these impossibilities?

The key limitation of scalar perspectives is their inability to capture the constraint geometry in infinite-dimensional function spaces. While existing fair representation methods attempt to hide group labels through adversarial debiasing or distribution alignment, they often incur severe, uncharacterized utility loss when facing intrinsic prior differences across groups. This paper tackles the problem by leveraging mean embeddings and characteristic kernels in Reproducing Kernel Hilbert Spaces (RKHS) to express all linear mean fairness criteria as inner-product constraints on conditional mean embedding vectors. This perspective exposes the overdetermination caused by the law of total probability as an intrinsic geometric contradiction in orthogonal complement subspaces. Core idea: Formalize fairness criteria as linear functionals over conditional mean embeddings in an RKHS, proving that inter-group distributional differences constitute a fixed MMD budget where no finite linear audit can eliminate all discrepancies (the Pokémon Theorem), and that enforcing distributional parity alongside class separation under unequal base rates inevitably triggers complete class collapse in the representation space.

Method

Overall Architecture

Rather than proposing an empirical training algorithm, the paper establishes a unified geometric analysis framework in an RKHS to interpret impossibilities in both scalar and representation fairness. Starting from conditional mean embeddings of individual features \(X\), binary labels \(Y\), and group attributes \(G \in \{a,b\}\), fairness auditing for scoring functions \(S(X) = \langle w, \phi(X) \rangle\) is formulated as inner-product constraints. This formulation derives four progressive theoretical findings: the strengthened KMR theorem, qualitative and quantitative Pokémon theorems, the impossibility of fair feature learning, and approximate fairness Pareto frontiers (the continuous Pokémon–KMR bridge).

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Individual Feature Distribution (X, Y, G)"] --> B["RKHS Conditional Mean Embeddings & Difference Vector<br/>δ = μ_a - μ_b"]
    B --> C["Strengthened KMR Dichotomy<br/>Triggered by First-Order Group Unbiasedness Alone"]
    B --> D["Pokémon Theorem & Spectral Decay<br/>Finite Audits Leave MMD Witness Residuals"]
    B --> E["Impossibility of Fair Feature Learning<br/>Parity + Separation Induces Class Collapse"]
    D --> F["Approximate Fairness Relaxation & Signal Bounds<br/>Pokémon–KMR Continuous Convergence Bridge"]
    E --> F

Key Designs

1. Strengthened KMR Theorem: Relaxing Full Calibration to First-Order Mean Unbiasedness The classic KMR theorem requires strict pointwise within-group calibration \(\mathbb{E}[Y \mid S=s, G=g] = s\), which is a high-order distributional condition. This paper proves that the impossibility holds under a substantially weaker first-order moment requirement—group-conditional mean unbiasedness \(\mathbb{E}[S \mid G=g] = p_g\), where \(p_g = \Pr[Y=1 \mid G=g]\). When the scoring function simultaneously satisfies positive-class balance and negative-class balance, defining \(\mu^+ = \mathbb{E}[S \mid Y=1, G=g]\) and \(\mu^- = \mathbb{E}[S \mid Y=0, G=g]\), the law of total expectation yields: $\(p_g = p_g \mu^+ + (1 - p_g) \mu^- \quad \Longrightarrow \quad (p_a - p_b)(1 - (\mu^+ - \mu^-)) = 0\)$ Assuming unequal base rates (\(p_a \neq p_b\)), it necessarily follows that \(\mu^+ - \mu^- = 1\). Combined with the boundedness of scores \(S \in [0,1]\), Markov's inequality directly implies that \(S=Y\) holds almost surely. This establishes that even if a model's predicted probabilities are poorly calibrated pointwise, it cannot escape the KMR deadlock as long as its aggregate group-level predictions match the true base rates.

2. The Pokémon Theorem: Finite Linear Audits Cannot Exhaust Distributional Discrepancies Addressing industrial practices that stack multiple fairness checklists (such as demographic parity and equalized odds) to eliminate bias, the Pokémon Theorem (playing on the franchise slogan "Gotta Catch 'Em All" by proving that one cannot catch them all) shows that whenever the kernel is characteristic and underlying group distributions differ (\(P_a \neq P_b\)), the group difference vector \(\delta = \mu_a - \mu_b \neq 0\). Any system conforming to \(m\) linear mean fairness criteria \(\{v_1, \ldots, v_m\}\) effectively confines \(\delta\) to the orthogonal complement of the audit subspace \(V = \mathrm{span}\{v_1, \ldots, v_m\}\). The normalized difference vector \(v_{m+1} = \delta / \|\delta\|_\mathcal{H}\) acts as an MMD witness function that is strictly orthogonal to the audited \(m\) directions and uncovers residual violations: $\(\langle v_{m+1}, \delta \rangle = \|\delta\|_\mathcal{H} = \mathrm{MMD}(P_a, P_b) > 0\)$ In its quantitative formulation, assuming the mixture covariance operator \(\Sigma\) exhibits polynomial eigenvalue decay \(\lambda_j \asymp j^{-\alpha}\) (\(\alpha > 1\)) and \(\delta\) satisfies an integral source condition \(\delta = \Sigma^r u\) (\(\|u\|_\mathcal{H} \le R\)), the minimax residual for an audit budget of \(m\) exactly matches the Kolmogorov \(m\)-width rate of the Hilbert ellipsoid: $\(\inf_{\dim V \le m} \sup_{\delta \in B_r(R)} \|P_{V^\perp} \delta\|_\mathcal{H}^2 = R^2 \lambda_{m+1}^{2r} = \Theta(R^2 (m+1)^{-2\alpha r})\)$ This demonstrates that the top \(m\) principal eigenspaces form the optimal audit budget allocation, yet for any finite \(m\), the worst-case residual violation remains strictly positive.

3. Impossibility of Fair Feature Learning: Distributional Parity and Class Separation Cause Class Collapse Representation learning widely aims to construct measurable encoders \(\Phi: \mathcal{X} \to \mathcal{Z}\) such that latent representations \(Z=\Phi(X)\) achieve demographic parity \(\Phi(P_a) = \Phi(P_b)\) while preserving class separation for downstream tasks \(\mu_{\Phi, y, a} = \mu_{\Phi, y, b}\). The paper proves that when \(p_a \neq p_b\), the law of total expectation forces the Bochner integrals of mean embeddings in the representation space to collapse: $\(\mu_{\Phi, a} - \mu_{\Phi, b} = (p_a - p_b)(\mu_{\Phi, 1} - \mu_{\Phi, 0}) = 0 \quad \Longrightarrow \quad \mu_{\Phi, 1} = \mu_{\Phi, 0}\)$ Under an injective characteristic kernel mapping, this implies complete independence at the distribution level, \(\Phi(X) \perp\!\!\!\perp Y\). Consequently, no measurable downstream predictor can retain any mean discriminative signal regarding the true class label \(Y\). Feature learning fails to circumvent KMR and instead leads to the total extinction of downstream predictive utility.

4. Approximate Fairness Pareto Frontier & The Pokémon–KMR Continuous Convergence Bridge To guide practical algorithmic design with tolerance margins, the paper derives an approximate fairness relaxation theorem. Under \(\varepsilon\)-approximate parity and \(\rho\)-approximate class separation assumptions, the maximum class-mean discriminative signal available within groups is strictly bounded: $\(\|\mu_{\Phi, 1, g} - \mu_{\Phi, 0, g}\|_{\mathcal{H}_\mathcal{Z}} \le \frac{\varepsilon + \rho}{|p_a - p_b|}, \quad \forall g \in \{a,b\}\)$ For binary classifiers \(\hat{Y}\), this geometric bound reduces to an explicit error lower bound: \(\mathrm{error}(\hat{Y}) \ge \min(p, 1-p)(1 - \mathrm{DP\_gap}/|p_a - p_b|)\). Furthermore, by introducing \(m\)-dimensional class-balance audit constraints into the kernel space and employing source-condition decay, the tail residual translates into a continuous bounded probability: $\(\Pr[|S - Y| > t] \le \frac{W \rho_m}{|\Delta p| t} = O(W R (m+1)^{-\alpha r} / (|\Delta p| t))\)$ As the audit dimension \(m \to \infty\), this bound converges to zero at a polynomial rate, bridging finite-dimensional audit approximations with classic KMR's \(S=Y\) almost surely.

Key Experimental Results

Main Results

The theoretical claims were evaluated at the population level across three benchmark fairness datasets: Adult Income (\(n \approx 45\text{K}\), gender as sensitive attribute), COMPAS (\(n \approx 5.3\text{K}\), race as sensitive attribute), and ACS PUMS California 2018 (\(n = 20\text{K}\), income prediction). The kernel was fixed to a Gaussian RBF kernel with median bandwidth, with statistical significance established via 1,000 bootstrap resamples and 999 permutation tests.

| Dataset | Sample Size (\(n\)) | Sensitive Attribute (\(G\)) | Base Rate Gap (\(|\Delta \hat{p}|\)) | Sensitive Group Ratio (\(\Pr[G=a]\)) | Criteria for 99% MMD Capture (\(k_{99}\)) | Top-3 Spectral Variance Ratio | |---|---|---|---|---|---|---| | Adult Income | \(\approx 45,000\) | Gender (Male vs Female) | \(0.20\) (\(0.306\) vs \(0.109\)) | \(0.675\) | \(35\) | \(41\%\) | | COMPAS | \(\approx 5,300\) | Race (Black vs White) | \(0.13\) (\(0.52\) vs \(0.39\)) | \(0.60\) | \(4\) | \(98\%\) | | ACS PUMS | \(20,000\) | Race/Gender Compound | \(0.085\) (\(0.44\) vs \(0.36\)) | \(0.62\) | \(8\) | \(61\%\) |

Ablation Study

The table below assesses empirical violation tests against theoretical lower bounds for near-separation classifiers (Hardt equalized odds post-processing and ExpGrad-EO, gated by \(\mathrm{EO\_gap} \le \tau\)) and inspects fair representation models along forbidden boundary regimes.

Evaluation Setting & Configuration Gating Threshold (\(\tau\)) Total Evaluation Points Raw Lower-Bound Violations Bootstrap 95% CI Statistical Violations Theoretical Consistency
Separation Pareto Bound (Relaxed Gating) \(\mathrm{EO\_gap} \le 0.05\) 46 (Adult 12, COMPAS 11, ACS 23) 7 (Adult 0, COMPAS 5, ACS 2) 1 (marginal ACS point, margin 0.0035) 97.8% (CI perspective)
Separation Pareto Bound (Strict Gating) \(\mathrm{EO\_gap} \le 0.02\) 17 (Adult 2, COMPAS 3, ACS 12) 3 (Adult 0, COMPAS 2, ACS 1) 0 100.0%
Forbidden Corner Test (Fair-VAE) \(\rho = 0.15\) Sweeps over \(\lambda_{\mathrm{MMD}} \in [0, 10]\) 0 0 100.0% (no violations)
Forbidden Corner Test (Adv-Debias) \(\rho = 0.15\) Sweeps over \(\lambda_{\mathrm{adv}} \in [0, 10]\) 0 0 100.0% (no violations)
Forbidden Corner Test (LFR) \(\rho = 0.15\) Sweeps over \(A_z \in [0.1, 100]\) 0 0 100.0% (no violations)

Key Findings

  • Audit decay rates are governed by intrinsic data support dimensionality: For COMPAS, which has low feature dimensionality (8 one-hot encoded features) and an extremely compact covariance spectrum, the top 3 eigenvectors capture 98% of the difference vector norm; only \(k_{99}=4\) criteria are needed to reduce residual violation below 1%. In contrast, Adult Income possesses higher dimensionality and rich continuous features, requiring 35 directions to capture 99%, strictly conforming to Kolmogorov \(m\)-width polynomial decay on log-log scales.
  • Empirical classifier Pareto frontiers closely trace theoretical lower bounds: Across all near-separation classifier configurations, empirical error points lie strictly above the lower-bound curve \(y = \min(p, 1-p)(1 - x/|\Delta p|)\). Under strict gating (\(\tau = 0.02\)), none of the 17 classifiers across all datasets violate the theoretical boundary. The single marginal violation under relaxed gating exceeded the bound by only 0.0035, well within test-set sampling noise.
  • Representation learning exhibits an absolute void in the "high discriminability, high fairness" corner: For Fair-VAE, Adversarial Debiasing, and LFR, as representation parity \(\varepsilon \to 0\), intra-group class signal experiences linear compression governed by slope \(1/|\Delta p|\). The upper-left quadrant (low \(\varepsilon\) and high signal) is entirely empty across all models and random seeds, empirically validating the class collapse mechanism proven in Theorem 5.1 and Theorem 6.1.

Highlights & Insights

  • Unifying discrete fairness metrics under continuous operator geometry: A primary highlight is unifying discrete distributional properties into a single inner-product operator via RKHS conditional mean embeddings. This collapses previously disparate impossibility proofs (KMR, Chouldechova, and Barocas' mutually incompatible trinity) into a unified overdetermined structure driven by the law of total expectation.
  • Reframing fairness audits as spectral budget allocation: Traditional compliance testing treats fairness as a binary pass/fail audit. The Pokémon Theorem reframes this as an MMD budget allocation problem where group distributional differences form a fixed physical budget. Principal operator eigenfunctions provide optimal auditing priorities, delivering a principled minimax spectral truncation criterion under finite budgets.
  • Pinpointing the fundamental limits of fair representation learning: The paper demarcates the theoretical ceiling of feature filtering. When base rates diverge, hoping that deep encoders can costlessly eliminate bias while preserving complete predictive power is mathematically impossible; aggressively filtering sensitive information inevitably collapses class-discriminative signals.

Limitations & Future Work

  • Theoretical assumptions on problem scope: The core theorems currently assume binary protected attributes, binary output labels, and scalar score predictions. While the authors outline natural extensions to \(K\) groups (via vector norms), multiclass outputs, and vector scoring rules, analyzing more complex multi-way interaction structures remains an open direction.
  • Scope restricted to observational fairness: The operator geometry operates strictly on observational distributions, without encompassing counterfactual fairness or causal intervention frameworks defined on causal DAGs.
  • Policy and engineering implications: When demographic groups exhibit significant underlying statistical disparities, optimizing algorithmic loss penalties or learning unbiased representations cannot fundamentally resolve the trade-off. Explicit, policy-level interventions (such as group-specific score baseline adjustments or institutional affirmative remedies) are necessary and compliant mechanisms.
  • vs KMR Theorem (Kleinberg et al., 2017): While KMR relies on full within-group calibration as a strong distributional requirement, this work proves that first-order mean unbiasedness suffices to trigger the same perfect prediction dichotomy, markedly expanding the applicability of the impossibility.
  • vs Mutually Incompatible Trinity (Barocas et al., 2023): Classic literature focuses on pairwise mutual exclusivity among independence, separation, and sufficiency. This work reveals varying sensitivities of these criteria between mean formulations and full-distribution forms, explaining why independence and sufficiency cannot establish geometric equivalence via first moments alone in the way KMR does.
  • vs Fair Representation Learning (Zemel et al., 2013; Louizos et al., 2016): Prior works attempt to learn representations independent of sensitive attributes using adversarial or generative models. This paper presents an explicit geometric impossibility theorem demonstrating that under base rate disparity, pursuing exact distributional parity inevitably wipes out all predictive signal.

Rating

  • Novelty: ⭐⭐⭐⭐⭐ Elegant unification of fairness impossibilities using RKHS mean embeddings, geometric orthogonal complements, and Kolmogorov widths.
  • Theoretical Thoroughness: ⭐⭐⭐⭐⭐ Rigorous and self-contained proofs establishing an end-to-end theoretical progression from exact impossibilities and spectral decay rates to continuous approximate convergence bounds.
  • Experimental Thoroughness: ⭐⭐⭐⭐ Empirical experiments rigorously validate the three main theoretical predictions with disciplined statistical testing and bootstrap confidence intervals.
  • Value: ⭐⭐⭐⭐⭐ Clarifies the fundamental theoretical limits of representation debiasing and fairness checklists, offering pivotal guidance for algorithmic fairness design.