TL;DR
Automated screening tools often rely on calibrated classifiers to select optimal candidate shortlists, but this paper reveals a hidden trap: calibrated models frequently suffer from "within-group unfairness," mistakenly rejecting highly qualified individuals while shortlisting less qualified peers from the same demographic group. To resolve this, the authors introduce the concept of within-group monotonicity and provide an efficient dynamic programming algorithm that eliminates these unfair ranking reversals with minimal impact on prediction accuracy and shortlist size.
What Problem Does This Paper Address?
In high-stakes selection processes like hiring, university admissions, and medical triage, algorithms are widely used to filter down thousands of applicants into a manageable shortlist. Recent machine learning literature suggests that as long as a screening classifier is calibrated (meaning its predicted probability matches the true empirical probability of qualification), decision-makers can use a simple threshold rule to generate the smallest, most efficient shortlist possible.
However, this paper identifies a critical flaw in relying solely on calibration. The authors demonstrate that calibrated classifiers can suffer from within-group unfairness. Due to a statistical phenomenon akin to Simpson's Paradox, a calibrated model can invert the true qualification rankings within a specific demographic subgroup. As a result, an applicant from a minority group who is highly likely to be qualified might be rejected, while a less qualified applicant from the exact same group is shortlisted.
This happens when group membership acts as a confounding factor that influences both the features and the target label. The paper aims to formalize this problem and design a method to fix it without destroying the predictive power of the model.
Methods
To eliminate these unfair ranking flips, the authors introduce a new fairness property called within-group monotonicity. This property ensures that for any two candidates within the same demographic group, the candidate with the higher model score must also have a higher (or equal) true probability of being qualified.
To enforce this property on an existing calibrated classifier, the authors propose a post-processing framework that groups the model's predictions into discrete bins and strategically merges bins that cause monotonicity violations. They approach this from two angles:
- Hardness Analysis: They first prove that finding the absolute largest partition (to preserve the model's fine-grained accuracy) across arbitrary bin combinations is NP-hard.
- Contiguous Partitions & Dynamic Programming: To make the problem tractable, they restrict the search to contiguous partitions—meaning they only merge adjacent score bins. This restriction guarantees that the modified classifier maintains the original model's overall ranking direction.
While this resembles a classic isotonic regression problem, the authors show that the standard Pool Adjacent Violators (PAV) algorithm fails to find even locally optimal solutions in this setting. Instead, they develop a novel Dynamic Programming (DP) algorithm that is guaranteed to find the optimal contiguous partition in polynomial time ($O(n^3 \times |Z|)$, where $n$ is the number of bins and $|Z|$ is the number of demographic groups).
Datasets
The authors evaluated their framework using real-world survey data:
- US Census Dataset ("Retiring Adult"): A dataset containing approximately 3.2 million individuals, each represented by 16 features.
- Task & Groups: The target label was employment status (acting as a proxy for qualification). The demographic groups of interest ($Z$) were defined using four distinct features across different experimental runs: US citizenship status, race, gender, and disability record.
Key Insights and Ideas
- Calibration $\neq$ Fairness: Perfect calibration at the population level does not guarantee fair or even accurate rankings within demographic subgroups.
- The Accuracy-Fairness Tension: Finer-grained, more accurate classifiers (those with more prediction bins) are statistically more susceptible to within-group unfairness than coarser models. High resolution gives the model more opportunities to introduce subtle, confounding-driven ranking flips.
- Monotonicity vs. Calibration: While ensuring perfect calibration within each group also fixes the ranking problem, doing so is often mathematically impossible or forces the model to become overly coarse. Within-group monotonicity serves as a more practical, achievable objective that protects candidate rankings without over-correcting.
Key Results
- High Prevalence of Unfairness: In baseline calibrated models, minority individuals faced a substantial risk of within-group unfairness. For instance, when binning the model into 15 scores, the probability of a non-US citizen experiencing a ranking violation exceeded 30%.
- Algorithm Superiority: The proposed DP algorithm consistently outperformed the modified PAV algorithm and within-group $\epsilon$-calibration methods, preserving significantly more prediction granularity (larger partition sizes).
- Low Cost of Fairness: Enforcing within-group monotonicity incurred only a minor penalty in shortlist efficiency. The size of the shortlists generated by the fair model was only marginally larger than those generated by the unconstrained, unfair model.
Limitations and Future Work
- Prediction-Only Access: The current post-processing framework assumes perfect knowledge of the true underlying group-conditional probabilities to perform bin merging. In practice, these must be estimated from finite data. The authors note that adapting the methodology to a sample access model (accounting for statistical estimation errors) is an important next step.
- Interactions with Group Fairness: The paper focuses entirely on fairness within groups. How within-group monotonicity interacts with traditional across-group fairness metrics (such as demographic parity or equalized odds) remains an open question for future research.
Summary updated