Source-linked AI summary
Inherent Trade-Offs in the Fair Determination of Risk Scores
Jon Kleinberg, Sendhil Mullainathan, Manish Raghavan
TL;DR
The paper asks how competing fairness requirements for probabilistic risk assignments can be satisfied across groups. It formalizes three conditions and proves that they are jointly achievable only in highly constrained cases, with a corresponding approximate result. The findings establish method-independent trade-offs while leaving the choice among conflicting fairness definitions open.
Problem
Competing notions of fairness for probabilistic classifications raise the question of whether groupwise calibration and balance requirements can hold simultaneously.
Method
The paper formalizes risk assignments as feature-vector-based, possibly randomized assignments to score bins and analyzes three fairness conditions within this model.
Results
The three fairness conditions are jointly satisfiable only with perfect prediction or equal base rates, and approximate satisfaction requires an approximate version of one of these cases.
Takeaways & Limitations
The results establish unavoidable trade-offs among natural fairness definitions independently of the method used to compute risk scores.
Takeaways & Limitations
It remains open whether a polynomial-time algorithm can find a minimum-loss fair assignment or determine whether a non-trivial fair solution exists.
Abstract
from arXiv · showhide
Recent discussion in the public sphere about algorithmic classification has involved tension between competing notions of what it means for a probabilistic classification to be fair to different groups. We formalize three fairness conditions that lie at the heart of these debates, and we prove that except in highly constrained special cases, there is no method that can satisfy these three conditions simultaneously. Moreover, even satisfying all three conditions approximately requires that the data lie in an approximate version of one of the constrained special cases identified by our theorem. These results suggest some of the ways in which key notions of fairness are incompatible with each other, and hence provide a framework for thinking about the trade-offs between them.
1 Introduction
The paper examines competing fairness guarantees for probabilistic risk assignments across groups and proves that calibration and balance conditions are generally incompatible except in highly constrained cases. It formalizes risk assignments, characterizes the exact and approximate feasible cases, and frames the resulting trade-offs without recommending which fairness definition to prioritize.
- Motivation: Risk scores are used across criminal justice, advertising, and medical testing to estimate whether people possess relevant properties.These estimates often serve as inputs to larger human or algorithmic decision systems.
- Fairness conditions: The paper distinguishes groupwise calibration from balance for positive and negative classes, which compare score effectiveness after conditioning on the correct class.These balance conditions are distinct from global statistical parity.
- Main result: The three fairness conditions are generally incompatible and can be simultaneously satisfied only in highly constrained cases.The same incompatibility applies to approximate versions of the conditions.
- Characterization theorem: Perfect prediction and equal base rates are the two cases in which all three fairness guarantees can be achieved simultaneously.Perfect prediction assigns scores 0 or 1, whereas equal base rates permits assigning everyone a common score equal to the shared positive-class average.
- Approximate characterization: Approximately satisfying all three conditions requires the instance to approximately resemble perfect prediction or equal base rates.The theorem expresses this through a continuous function f with f(ε) approaching 0 as ε approaches 0.
- Scope and implications: The authors establish unavoidable trade-offs regardless of how risk scores are computed, but do not recommend how conflicts among fairness definitions should be handled.They also do not analyze which definitions are violated in particular applications or datasets.
2 The Characterization Theorems
The proof models risk assignments with feature vectors, groups, bins, and allocation matrices, then shows that calibration and class-balance conditions force either perfect prediction or equal base rates.
- Informal overview: If base rates differ, the two fairness equations intersect only at (x, y) = (0, 1), implying perfect prediction.If base rates are equal, the equations coincide instead, so the theorem permits the equal-base-rate case.
- Definitions and notation: The proof represents each risk assignment using feature-vector distributions, group counts, positive-class rates, bin scores, and allocation matrix X.X specifies the fraction of people with feature vector σ assigned to each bin; fractional allocations imply randomization within indistinguishable feature vectors.
- Calibration within groups: Calibration equates each group’s expected score in every bin with its expected number of positive-class members assigned to that bin.Summing across bins makes the total expected score for group t equal to µt, its number of positive-class members.
- Fairness to the positive and negative classes: Balance requires the average scores assigned to positive-class members and negative-class members to be the same across the two groups.The proof denotes these shared class-specific averages by y for the positive class and x for the negative class.
- Characterization theorem: The theorem’s algebra yields only two simultaneous-feasibility cases: perfect prediction or equal base rates.The proof identifies these alternatives through γ = 1 or µ1/N1 = µ2/N2.
- Statistical parity: When base rates differ, statistical parity is inconsistent with calibration and with the conjunction of the two class-balance conditions.Equal base rates permit the constant-score assignment to satisfy statistical parity together with all three conditions.
3 The Approximate Theorem
The approximate theorem formalizes ε-versions of the fairness conditions and proves that substantial base-rate differences force near-perfect predictive behavior.
- Approximate fairness conditions: The approximate analysis defines ε-fairness conditions and approximate versions of perfect prediction and equal base rates through a function f(ε) that tends to 0 with ε.The proof begins by deriving an approximate form of the calibration equation.
- Proof overview: The proof first shows that each group’s total expected score is approximately µt, its positive-class count.This approximate total-score relation supports approximate versions of the equations used in the exact theorem.
- Positive-class scores: Approximate balance for the positive class implies that γ1 and γ2 are approximately equal.Here γt is the average expected score assigned to positive-class members in group t.
- Relationship between the base rates: If the base rates are separated beyond the permitted additive f(ε) range, ε-fairness forces γ1 ≥ 1 − f(ε) and γ2 ≥ 1 − f(ε).The theorem therefore links approximate fairness with near-perfect prediction when base rates are sufficiently different.
4 Reducing Loss with Equal Base Rates
The paper studies accuracy and feasible fair assignments when groups have equal base rates, finding that nontrivial fairness can improve over the constant assignment but generally trades off against minimum loss and may be computationally hard.
- Loss: The loss assigns v to a negative-class person receiving score v and 1 − v to a positive-class person, then sums these individual losses by group.Total loss is the weighted sum of the group losses.
- Reducing loss with equal base rates: With equal base rates, a fair assignment exists, and its loss is strictly below the trivial one-bin assignment exactly when a multi-bin fair assignment exists.The constant assignment is calibrated and satisfies all three conditions, but is not particularly informative.
- Performance and fairness: The identity assignment, which gives each feature vector its own score pσ, minimizes loss but may violate the two balance conditions.Unless it is itself fair, every fair assignment has strictly larger loss, creating a performance–fairness tradeoff.
- Characterization of well-calibrated solutions: For equal base rates, fairness differences achievable by nontrivial well-calibrated assignments form an interval.Convex combinations of assignments construct intermediate fairness differences.
- Characterization of well-calibrated solutions: A nontrivial fair assignment exists exactly when nontrivial well-calibrated assignments can weakly favor group 1 and weakly favor group 2.The interval property supplies an assignment with fairness difference zero between those two cases.
- Open computational questions: Whether a polynomial-time algorithm can find a minimum-loss fair assignment or decide whether a nontrivial fair solution exists remains open.This is stated as an open computational question for the fair-assignment problem.
- NP-completeness of non-trivial integral fair risk assignments: Determining whether a nontrivial integral fair assignment exists is NP-complete when the two groups have equal base rates.Integral assignments require all people sharing feature vector σ to use the same bin; the proof reduces from Subset Sum.
5 Conclusion
The paper formalizes three proposed fairness conditions and shows that they generally cannot all hold simultaneously, even approximately. These trade-offs arise from differing group base rates and are independent of the method used to compute risk assignments.
- Three proposed fairness conditions for individual risk assignments are formalized as competing guarantees of fairness.
- Any risk assignment satisfying all three conditions must fall into a highly constrained case, such as perfect prediction or equal base rates.
- When group base rates differ, at least one group may receive systematically skewed estimates, higher average risk among healthy people, or higher average risk among carriers.
- The trade-off holds regardless of how risk assignments are computed, so it is not specific to medical testing.
- Future work includes studying broader fairness families and settings with unequal error costs or unresolved computational questions.
Appendix: NP-Completeness of Non-Trivial Integral Fair Risk Assignments
The appendix proves NP-completeness for deciding whether a non-trivial integral fair risk assignment exists in the equal-base-rate case. The proof reduces Subset Sum to the integral assignment problem and establishes an equivalence between solutions.
- The reduction constructs an integral assignment instance from a Subset Sum instance with numbers w1, . . . , wm and target T.
- The construction encodes the target through fairness by ensuring that the group-2 positive-class average must equal the controlled group-1 average.
- The constructed assignment has a solution if and only if the original Subset Sum instance has a solution.
- A fair partition can contain either singleton elements or paired elements {2i − 1, 2i}; only paired elements contribute to the fairness expression.
- A subset S solving the Subset Sum instance yields a fair partition Q by pairing exactly the indices in S and separating the remaining elements.
- The integral assignment problem is NP-complete because it is NP-hard and candidate assignments can be verified in polynomial time.