Fair Decisions from Calibrated Scores: Achieving Optimal Classification While Satisfying Sufficiency

AI summary

Overview

Research area: Algorithmic fairness in machine learning, specifically binary classification under the fairness criterion known as sufficiency (also called predictive parity or group-calibration).

Technical level: Advanced. The paper is a theory contribution built on convex geometry, linear programming (fractional knapsack), and measure-theoretic probability notation.

Scope in one sentence: The paper gives an exact geometric characterization of which (positive predictive value, false omission rate) pairs are attainable by randomized binary classifiers built from finite-valued group-calibrated scores, and derives a post-processing algorithm that attains the optimal sufficient classifier.

Paper metadata (as given): Etam Benger and Katrina Ligett, School of Computer Science and Engineering, The Hebrew University of Jerusalem, Israel (Ligett also at The Federmann Center for the Study of Rationality). arXiv:2602.07285v2 [cs.LG], 28 May 2026; published 2026-02-07. License CC BY 4.0. Keywords listed: Algorithmic Fairness, Sufficiency, Predictive Parity, Classification, Machine Learning, ICML. Code is stated to be made available at https://github.com/etambenger/fair-decisions-from-calibrated-scores.

What This Paper Is About

In many high-stakes decisions, a system produces a probability score (for example, a risk score) and then converts it into a yes/no decision. The standard way to do this is to pick a single threshold on the score. That is optimal when nothing else is constrained, but it usually breaks fairness requirements across protected groups. For two of the three standard fairness criteria — independence (statistical parity) and separation (equalized odds, equal opportunity) — a single threshold is safe if the score already satisfies the criterion. The paper's core problem is that this convenient property fails for the third criterion, sufficiency: even a perfectly group-calibrated score, including the true class probability, produces decisions that violate predictive parity once you threshold it. The goal is to characterize exactly which decisions are achievable under sufficiency and to construct the best one.

Key Contributions

1. Exact characterization of the feasible region under sufficiency. For finite-valued, group-calibrated scores, the authors characterize the set of (PPV, FOR) pairs attainable by any randomized classifier that depends on the score alone, showing the region is star-convex with center (π, π), giving an explicit piecewise formula for its nontrivial boundary, and showing the boundary consists of two straight segments plus hyperbolic arcs (when m > 2).

2. Characterization of the multi-group feasible region and its boundary. Sufficiency in a two-group setting is equivalent to requiring a common (p, q) pair to lie in the intersection of the two subgroup-feasible regions; the authors show the intersection's boundary is the pointwise maximum of the two group boundaries and give a way to trace it efficiently, including handling crossings between the two curves.

3. A post-processing algorithm. Algorithm 1 ("Boundary Trace") iterates over the boundary of the intersection while tracking the active group and indices, evaluating an objective function along the way. It uses only group-calibrated scores and group membership as input, and it constructs the optimal sufficient classifier for a wide class of objectives, including loss minimization.

4. A sufficient classifier that minimizes deviation from separation. Because sufficiency and separation are generally incompatible, the authors identify the classifier that minimizes the deviation from separation subject to sufficiency, show this objective can also be optimized inside the same geometric framework, and report that it often achieves performance comparable to the loss-optimal solution.

Main Findings

• Thresholding breaks sufficiency even with perfect group-calibration. Unlike independence and separation, sufficiency is not preserved by post-processing a score that already satisfies it; even the true conditional probability P(Y=1|X, A) produces decisions violating predictive parity after thresholding. The paper cites the COMPAS recidivism risk score, which takes values between 1 and 10 and is used for binary decisions such as bail decisions, as a central case study.

• The feasible region is star-convex, not convex. For any fixed selection rate μ = P(R=1), the base rate satisfies π = μp + (1−μ)q, so all pairs feasible with that μ lie on a line of slope −μ/(1−μ) through (π, π). Mixing a classifier with an independent Bernoulli(μ) variable yields PPV = ηp + (1−η)π and FOR = ηq + (1−η)π for η in [0,1], giving star-convexity with center (π, π). The region itself is typically not convex.

• The extremal classifiers are soft thresholds, and hard thresholds are the breakpoints. For fixed μ, maximizing PPV reduces to a linear program equivalent to a fractional knapsack problem. Its greedy solution is a classifier that deterministically predicts 1 for score bins above s_{k*}, 0 below, and possibly randomizes on bin k*, where k*(μ) = min{k : Σ_{i≤k} P(s_i) ≥ μ}. It becomes a purely deterministic ("hard") threshold exactly at the values μ_k = Σ_{i≤k} P(s_i).

• Explicit boundary formula. On the interval I_k, p*(μ) = s_k + c_k/μ with c_k = Σ_{i<k} P(s_i)(s_i − s_k). Since c_1 = 0, p*(μ) is constant and equal to s_max on I_1; for k > 1, c_k > 0 so p*(μ) is strictly decreasing in μ on each such interval. Reparametrizing by p gives μ(p) = c_k/(p − s_k) and q(p) = ((π − c_k)p − s_k π)/(p − s_k − c_k).

• Shape of the boundary. The closure of the nontrivial boundary is a continuous nondecreasing curve defined piecewise by the q(p) formula, together with a vertical segment at (s_max, q) for q in [q(s_max⁻), π]. It consists of two straight segments at q = s_min and p = s_max, and, if m > 2, a sequence of hyperbolic arcs. Breakpoints p_k = p*(μ_k) = (1/μ_k) Σ_{i≤k} s_i P(s_i) correspond exactly to the hard threshold classifiers.

• Global bounds. For any feasible (p, q) ≠ (π, π) with 0 < μ < 1: s_min ≤ q*(μ) ≤ q < π < p ≤ p*(μ) ≤ s_max. In the two-group case (assuming π⁰ ≤ π¹), max{π⁰, π¹} < p ≤ min{s_max⁰, s_max¹} and max{s_min⁰, s_min¹} ≤ q < min{π⁰, π¹}.

• Sufficiency means a common (p, q) in the intersection. Since sufficiency requires p⁰ = p¹ = p and q⁰ = q¹ = q, the object of interest is 𝒞⁰ ∩ 𝒞¹, whose boundary is q(p) = max{q⁰(p), q¹(p)}, possibly including a vertical segment at p = min{s_max⁰, s_max¹}.

• The intersection's boundary often excludes any deterministic threshold. Every boundary point of the intersection lies on the boundary of at least one subgroup region, but not necessarily both, so in a typical case almost all boundary points are interior points of one group's region. The boundary may contain no point corresponding to a deterministic threshold in either subgroup — Figure 2 (right) illustrates this, where the group-wise boundaries intersect twice.

• Loss optimum and separation-deviation minimum can differ. In Figure 2, with P(A=1) = 1/2, the point maximizing overall accuracy (minimizing 0–1 loss) is marked with a black cross and the point minimizing the deviation from separation, Δ_sep(R), with a black circle. In the left example (group-wise boundaries intersecting four times) the two optima coincide; in the right example they occur at distinct locations along the boundary.

• Algorithmic machinery for tracing the boundary. The effective domain is p in J = [π¹, p_max], where p_max = min{s_max⁰, p_max¹} and p_max¹ = max{p ≤ s_max¹ : q¹(p) ≤ π⁰}. The interval is partitioned into J_{k,l} = J ∩ J⁰_k ∩ J¹_l; the relative ordering of the two curves is determined by a quadratic Φ_{k,l}(p) that has at most two real roots in J_{k,l}, so each subinterval splits into at most three pieces J_{k,l,i} on which the active boundary is fixed. Where sufficiency and separation are incompatible, degenerate classifiers that are constant on one or both subgroups are handled in an appendix.

• Reported but not detailed in the available content. The text states that the algorithm constructs the optimal sufficient classifier for a wide class of objectives including loss minimization (Section 5), and that the deviation-from-separation objective yields classifiers often achieving performance comparable to the optimum (Section 6). The body of Sections 5 and 6 is not included in the available content, so their specific algorithms, theorems, and any numerical results are not reported here. No datasets, benchmark names, or experimental numbers appear in the available content.

Methodology in Plain English

The authors work entirely at the level of probability distributions rather than experiments. They assume the score takes finitely many values and is calibrated within each group, so that the score value equals the probability of a positive label for that group. They then ask which combinations of two quantities a decision rule could possibly produce: PPV (of those who get a positive decision, what fraction truly are positive) and FOR (of those who get a negative decision, what fraction truly are positive).

Their key move is a change of variables. Instead of describing a classifier by the probability it selects each score value, they describe it by three numbers: the selection rate μ, the PPV p, and the FOR q. A basic accounting identity, π = μp + (1−μ)q, forces these onto a line. Maximizing p for a fixed μ then becomes a linear program that is exactly a fractional knapsack problem, whose greedy solution is a threshold-like rule. Mixing any such rule with a coin flip centered at (π, π) shows the feasible set is star-shaped around (π, π), so the whole region is determined by its outer curve.

To pin down that curve, they divide the range of μ into pieces. On each piece, the classifier randomizes on one particular score bin, and p as a function of μ takes a simple closed form. Inverting that relation swaps μ for p as the parameter and yields a closed-form curve q(p) for each piece. When a protected attribute is added, feasibility is inherited group by group, sufficiency means both groups must land on the same (p, q) point, and the boundary of the common feasible set is simply the higher of the two group curves at every p. Because the two group curves are each made of simple algebraic pieces, the algorithm just walks along them, finds where they cross (the roots of a quadratic), and evaluates the user's objective on each constant-form stretch.

Why This Matters

Impact on research. The paper closes a gap described in its own related-work section: prior work either allowed the classifier to abstain on some instances (Canetti et al., 2019), or achieved sufficiency without abstentions only under strong assumptions of continuity and full support on the score distribution (Baumann et al., 2022), assumptions that do not hold for the discrete, finite-valued scores used by many practical systems. Other related work relaxes to approximate sufficiency (Celis et al., 2019; Delaney et al., 2024) or enforces the condition only for positive decisions (Zeng et al., 2022). This work instead gives an exact solution for finite sets of group-calibrated scores, and it explains geometrically why single-threshold decisions cannot satisfy sufficiency — a fact previously highlighted in theoretical and empirical work (Chouldechova, 2017; Canetti et al., 2019).

Real-world applications (domains the paper names or that fit its stated examples):

• College admissions, where Y may indicate whether an individual completes a college degree, S an admission test score, and A a protected demographic attribute such as gender.
• Lending and credit decisions based on risk scores.
• Hiring pipelines that screen candidates using predicted probabilities.
• Healthcare resource allocation, and criminal justice decisions such as bail, where the COMPAS recidivism risk score (values 1 to 10) is the paper's running example.

Industry relevance. The algorithm's inputs are exactly the artifacts a deployed system already has: group-calibrated scores, group membership, and group probabilities. It is a post-processing method, so it can be layered on an existing score without retraining, and the paper reports that the code will be released publicly. The practical risk it addresses is concrete: a team that validates a score for calibration within each group may still ship a thresholded decision rule that silently violates predictive parity.

Future Directions

• Completing the loss-minimization analysis. The available content introduces Section 5 (loss minimization under sufficiency) but does not include its theorems, its precise statement of which objective classes the algorithm handles, or any performance guarantees.
• Quantifying the separation-versus-sufficiency trade-off. The paper says the deviation-from-separation minimizer "often" achieves performance comparable to the optimum; an open question is characterizing exactly when that holds and when it does not, given the Figure 2 example in which the loss optimum and the deviation minimum differ.
• Extending beyond the two-group, finite-score setting. The paper states that the extension from a binary A to arbitrary finite support is straightforward, but the multi-group boundary tracing (and the degenerate cases deferred to an appendix) are natural places for further work.
• Empirical validation. No datasets, benchmarks, or numerical experiments appear in the available content, so evaluating the algorithm on real discrete score systems such as COMPAS-style risk scores is an obvious next step.

Target Audience

Researchers and graduate students in algorithmic fairness and statistical machine learning who work on post-processing methods and the incompatibility of fairness criteria, and who are comfortable with convex geometry and linear programming arguments. It is also aimed at practitioners who deploy score-based decision systems and need an exact, assumption-light procedure for making thresholded decisions satisfy sufficiency — particularly those working with discrete scores, where the continuity assumptions of earlier approaches do not hold. Readers looking for empirical benchmarks or datasets will not find them in this paper's available content.

Authors’ abstract

Binary classification based on predicted probabilities (scores) is a fundamental task in supervised machine learning. While thresholding scores is Bayes-optimal in the unconstrained setting, using a single threshold generally violates statistical group fairness constraints. Under independence (statistical parity) and separation (equalized odds), such thresholding suffices when the scores already satisfy the corresponding criterion. However, this does not extend to sufficiency: even perfectly group-calibrated scores -- including true class probabilities -- violate predictive parity after thresholding. In this work, we present an exact solution for optimal binary (randomized) classification under sufficiency, assuming finite sets of group-calibrated scores. We provide a geometric characterization of the feasible pairs of positive predictive value (PPV) and false omission rate (FOR) achievable by such classifiers, and use it to derive a simple post-processing algorithm that attains the optimal classifier using only group-calibrated scores and group membership. Finally, since sufficiency and separation are generally incompatible, we identify the classifier that minimizes deviation from separation subject to sufficiency, and show that it can also be obtained by our algorithm, often achieving performance comparable to the optimum.