Fairness criteria, impossibility boundaries, and limits

Let $\mathrm{\Sigma }$ and $\mathcal{B}$ be nonempty finite sets of feature types and score bins. For each group $t\in \{1,2\}$, let $N_t>0$ be its total mass and let $a_{t\sigma }\ge 0$ satisfy ${\sum }_{\sigma \in \mathrm{\Sigma }}{a}_{t\sigma }=1$. Let $p_{\sigma }\in [0,1]$ be the probability of the positive binary outcome $Y=1$ for feature type $\sigma$, with the same $p_{\sigma }$ in both groups. A randomized risk assignment consists of scores $v_b\in [0,1]$ for $b\in \mathcal{B}$ and a single matrix $X_{\sigma b}\ge 0$ with ${\sum }_{b\in \mathcal{B}}{X}_{\sigma b}=1$ for each $\sigma$; conditional on feature type $\sigma$, the assignment chooses bin $b$ with probability $X_{\sigma b}$, independently of group and outcome. Thus, for a group-$t$ individual chosen according to its feature distribution, ${\mathrm{Pr}}_t(\mathrm{\Sigma }=\sigma ,Y=1,B=b)=a_{t\sigma }{p}_{\sigma }{X}_{\sigma b}$ and ${\mathrm{Pr}}_t(\mathrm{\Sigma }=\sigma ,Y=0,B=b)=a_{t\sigma }(1-p_{\sigma })X_{\sigma b}$, and the assigned score is $S=v_B$. The expected positive mass is ${\mu }_t=N_t{\sum }_{\sigma }{a}_{t\sigma }{p}_{\sigma }$, and the group base rate is ${\rho }_t={\mu }_t\mathrm{/}{N}_t$.

The assignment is calibrated within group $t$ if for every $b\in \mathcal{B}$,

This cross-multiplied condition also covers bins with zero assigned mass. The instance permits perfect prediction when $p_{\sigma }\in \{0,1\}$ for every feature type with $a_{1\sigma }+a_{2\sigma }>0$, with the bin set and scores allowed to be chosen for this existence question. Assign the occupied types with $p_{\sigma }=0$ to a score-$0$ bin and those with $p_{\sigma }=1$ to a score-$1$ bin, omitting an unused outcome bin. For a prescribed $\mathcal{B}$, at least two bins are needed when both deterministic outcomes occur among occupied types; one bin suffices when only one occurs. A score assignment is perfectly predictive when $S=Y$ almost surely in each group.

Probability calibration and calibration error: within each group, full reliability of the binary forecast $(1-S,S)$ gives the calibration identity for each distinct score value. This is the per-bin identity above when every score value occurs in only one bin; if distinct bins share a score, full reliability gives only the aggregate identity across those bins.

Kleinberg, Mullainathan, and Raghavan, complete 23-page paper: §§1.1–1.2 define the finite feature-type, group, randomized-bin model and calibration within each group.

Applied Statistics: From Data to Decisions, full chapter: the section “The impossibility: you cannot satisfy them all” treats calibration within groups for real-valued scores and distinguishes the score theorem from its binary-classifier companion.

Let $\mathrm{\Sigma }$ and $\mathcal{B}$ be nonempty finite sets, and let $t\in \{1,2\}$ index two groups. In group $t$, feature type $\sigma$ has proportion $a_{t\sigma }\ge 0$, where ${\sum }_{\sigma }{a}_{t\sigma }=1$, and total mass $N_t>0$. The positive binary outcome $Y=1$ has probability $p_{\sigma }\in [0,1]$ for feature type $\sigma$, with the same $p_{\sigma }$ in both groups. A common randomized assignment sends feature type $\sigma$ to bin $b\in \mathcal{B}$ with probability $X_{\sigma b}\ge 0$, where ${\sum }_b{X}_{\sigma b}=1$, independently of group and outcome; bin $b$ has score $v_b\in [0,1]$. Set ${\rho }_t={\sum }_{\sigma }{a}_{t\sigma }{p}_{\sigma }$ and ${\mu }_t=N_t{\rho }_t$. Assume $0<{\mu }_t<N_t$ for each group, so both outcome classes have positive mass. Define the mean score among positive outcomes and among negative outcomes in group $t$ by

where the finite group law is ${\mathrm{Pr}}_t(\mathrm{\Sigma }=\sigma ,Y=1,B=b)=a_{t\sigma }{p}_{\sigma }{X}_{\sigma b}$ and ${\mathrm{Pr}}_t(\mathrm{\Sigma }=\sigma ,Y=0,B=b)=a_{t\sigma }(1-p_{\sigma })X_{\sigma b}$. The assignment is balanced for positive outcomes if ${\alpha }_1={\alpha }_2$, and balanced for negative outcomes if ${\beta }_1={\beta }_2$. These are class-conditioned mean-score criteria; they do not assert equal mean scores over whole groups or equal thresholded error rates.

KMR's finite group-conditioned risk-score assignment and calibration: fixes the finite joint law, the $[0,1]$ score, and the group base rate ${\rho }_t$. The nondegeneracy condition $0<{\mu }_t<N_t$ is imposed here.

Kleinberg, Mullainathan, and Raghavan, complete 23-page paper: §1.1 defines balance for the negative and positive classes as equality of the corresponding groupwise mean assigned scores.

Applied Statistics: From Data to Decisions, full chapter: the section “The impossibility: you cannot satisfy them all” states both score-balance criteria and distinguishes them from the binary-classifier theorem.

Fix a group $t\in \{1,2\}$ with a finite joint law ${\mathrm{Pr}}_t$ for a binary outcome $Y\in \{0,1\}$ and a score $S$ taking finitely many values in $[0,1]$, and assume ${\mathrm{Pr}}_t(Y=1)>0$ and ${\mathrm{Pr}}_t(Y=0)>0$. For each threshold $u\in [0,1]$, define the true-positive rate ${\mathrm{TPR}}_t(u)={\mathrm{Pr}}_t(S\ge u\mid Y=1)$ and the false-positive rate ${\mathrm{FPR}}_t(u)={\mathrm{Pr}}_t(S\ge u\mid Y=0)$. These are finite step functions and

The integrals are ordinary Riemann integrals of the finite step functions.

KMR's finite group-conditioned risk-score assignment and calibration: provides the finite group-conditional law and the finite $[0,1]$-valued score used in this statement.

Kleinberg, Mullainathan, and Raghavan, complete 23-page paper: §§1.1–2 define groupwise positive/negative score means and use these class-conditioned score distributions in Theorem 1.1.

The identity uses only finite support; no interchange theorem or choice principle is needed.

Let $\mathrm{\Sigma }$ and $\mathcal{B}$ be nonempty finite sets. In group $t\in \{1,2\}$, feature type $\sigma \in \mathrm{\Sigma }$ has proportion $a_{t\sigma }\ge 0$, where ${\sum }_{\sigma }{a}_{t\sigma }=1$, and total mass $N_t>0$. The positive binary outcome $Y=1$ has probability $p_{\sigma }\in [0,1]$ for feature type $\sigma$, with $p_{\sigma }$ the same in both groups. A common randomized assignment chooses bin $b\in \mathcal{B}$ from feature type $\sigma$ with probability $X_{\sigma b}\ge 0$, where ${\sum }_b{X}_{\sigma b}=1$; this choice is independent of group and outcome. Bin $b$ has score $v_b\in [0,1]$, and $S=v_B$. Define ${\rho }_t={\sum }_{\sigma }{a}_{t\sigma }{p}_{\sigma }$ and ${\mu }_t=N_t{\rho }_t$. Assume $0<{\mu }_t<N_t$ for both groups. Define the positive- and negative-outcome mean scores by

Suppose ${\alpha }_1={\alpha }_2$ and ${\beta }_1={\beta }_2$, and the assignment is calibrated within each group, meaning

for every group $t$ and bin $b$, and suppose the mean score among positive outcomes is equal across groups and the mean score among negative outcomes is equal across groups. Then either ${\rho }_1={\rho }_2$ or $S=Y$ almost surely under each group law. In the latter case, every feature type with positive mass in either group has $p_{\sigma }\in \{0,1\}$, so the instance permits perfect prediction.

Kleinberg, Mullainathan, and Raghavan, complete 23-page paper: Theorem 1.1 and the complete proof in §2 establish the equal-base-rate or perfect-prediction alternatives under these three named score criteria.

Applied Statistics: From Data to Decisions, full chapter: the section “The impossibility: you cannot satisfy them all” states the real-valued score theorem and distinguishes it from the separate binary-classifier theorem.

The proof is choice-free: it uses finite sums, finite conditional means, and algebra only. The theorem concerns the named calibration and class-conditioned score means; it does not assert a theorem about demographic parity, equalized odds, causal fairness, or all fairness criteria. The approximate result in KMR Theorem 1.2 is not asserted here; it requires its own exact approximation definitions and function $f(\epsilon )$.