The Pokémon Theorem and other Fairness Impossibility Results

• URL: http://arxiv.org/abs/2605.09221v1
• Date: Sat, 09 May 2026 23:37:10 GMT
• Title: The Pokémon Theorem and other Fairness Impossibility Results
• Abstract summary: We show that fairness criteria are linear constraints on conditional mean embeddings.<n>We also show that unequal base rates make the law of total expectation overdetermine those constraints.
• Score: 6.291388054687868
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 \emph{Pokémon 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.

Related papers

• No-Free-Fairness: Fundamental Limits and Trade-offs in Learning Systems [3.2356128177594363]
  We show that when a task exhibits irreducible cost on a subgroup, any decision rule must trade off overall performance with disparity.<n>We show that even in ideal, noise-free settings where a perfectly fair and accurate solution exists, finite-sample learning alone induces nontrivial subgroup disparity.
  arXiv  Detail & Related papers  (2026-06-16T11:37:52Z)
• The Attribution Impossibility: No Feature Ranking Is Faithful, Stable, and Complete Under Collinearity [0.0]
  No feature ranking can be simultaneously faithful, stable, and complete when features are collinear.<n>We prove this impossibility, quantify it for four model classes, resolve it via ensemble averaging (DASH), and machine-verify it with 305 Lean 4 theorems.<n>The design space theorem, diagnostics, and impossibility are mechanically verified in Lean 4 (305 theorems from 16 axioms, 0 sorry) -- to our knowledge, the first formally verified impossibility in explainable AI.
  arXiv  Detail & Related papers  (2026-04-08T10:11:45Z)
• Unregularized Linear Convergence in Zero-Sum Game from Preference Feedback [50.89125374999765]
  We provide the first convergence guarantee for Optimistic Multiplicative Weights Update ($mathtOMWU$) in NLHF.<n>Our analysis identifies a novel marginal convergence behavior, where the probability of rarely played actions grows exponentially from exponentially small values.
  arXiv  Detail & Related papers  (2025-12-31T12:08:29Z)
• Equal Opportunity of Coverage in Fair Regression [50.76908018786335]
  We study fair machine learning (ML) under predictive uncertainty to enable reliable and trustworthy decision-making. We propose Equal Opportunity of Coverage (EOC) that aims to achieve two properties: (1) coverage rates for different groups with similar outcomes are close, and (2) the coverage rate for the entire population remains at a predetermined level.
  arXiv  Detail & Related papers  (2023-11-03T21:19:59Z)
• Doubly Constrained Fair Clustering [11.11449872883085]
  Group Fairness (GF) and Diversity in Center Selection (DS) are two most prominent demographic representation fairness notions in clustering. We show that given a constant approximation algorithm for one constraint (GF or DS only) we can obtain a constant approximation solution that satisfies both constraints simultaneously. We show that both GF and DS are incompatible with a collection of other distance-based fairness notions.
  arXiv  Detail & Related papers  (2023-05-31T01:04:55Z)
• The Possibility of Fairness: Revisiting the Impossibility Theorem in Practice [5.175941513195566]
  We show that it is possible to identify a large set of models that satisfy seemingly incompatible fairness constraints. We offer tools and guidance for practitioners to understand when -- and to what degree -- fairness along multiple criteria can be achieved.
  arXiv  Detail & Related papers  (2023-02-13T13:29:24Z)
• Is the Moon there if nobody looks: A reply to Gill and Lambare [0.0]
  In a recent preprint Gill and Lambare criticize our paper published in Frontiers in Physics. They define a probabilistic coupling, in which BI-CHSH hold for all finite samples. A joint probability distribution of these random variables does not exist and may not be used to derive inequalities.
  arXiv  Detail & Related papers  (2022-09-16T14:59:24Z)
• Bounding and Approximating Intersectional Fairness through Marginal Fairness [7.954748673441148]
  Discrimination in machine learning often arises along multiple dimensions. It is desirable to ensure emphintersectional fairness -- i.e., that no subgroup is discriminated against.
  arXiv  Detail & Related papers  (2022-06-12T19:53:34Z)
• Distribution of Classification Margins: Are All Data Equal? [61.16681488656473]
  We motivate theoretically and show empirically that the area under the curve of the margin distribution on the training set is in fact a good measure of generalization. The resulting subset of "high capacity" features is not consistent across different training runs.
  arXiv  Detail & Related papers  (2021-07-21T16:41:57Z)
• GroupifyVAE: from Group-based Definition to VAE-based Unsupervised Representation Disentanglement [91.9003001845855]
  VAE-based unsupervised disentanglement can not be achieved without introducing other inductive bias. We address VAE-based unsupervised disentanglement by leveraging the constraints derived from the Group Theory based definition as the non-probabilistic inductive bias. We train 1800 models covering the most prominent VAE-based models on five datasets to verify the effectiveness of our method.
  arXiv  Detail & Related papers  (2021-02-20T09:49:51Z)
• A Unified Joint Maximum Mean Discrepancy for Domain Adaptation [73.44809425486767]
  This paper theoretically derives a unified form of JMMD that is easy to optimize. From the revealed unified JMMD, we illustrate that JMMD degrades the feature-label dependence that benefits to classification. We propose a novel MMD matrix to promote the dependence, and devise a novel label kernel that is robust to label distribution shift.
  arXiv  Detail & Related papers  (2021-01-25T09:46:14Z)
• A Weaker Faithfulness Assumption based on Triple Interactions [89.59955143854556]
  We propose a weaker assumption that we call $2$-adjacency faithfulness. We propose a sound orientation rule for causal discovery that applies under weaker assumptions.
  arXiv  Detail & Related papers  (2020-10-27T13:04:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.