TL;DR
Rather than forcing machine learning models to adhere to rigid, top-down statistical fairness definitions, this paper introduces a framework to elicit nuanced fairness preferences directly from human stakeholders as pairwise comparisons. The authors develop a provably convergent, oracle-efficient learning algorithm with formal generalization guarantees and demonstrate its viability through a behavioral study on criminal recidivism risk prediction.
What Problem Does This Paper Address?
Algorithmic fairness research has largely relied on simple mathematical criteria, such as equalizing false positive rates or acceptance rates across demographic groups. However, these analytical definitions suffer from two core shortcomings:
- Lack of nuance: They cannot express context-specific or complex moral intuitions.
- Exclusion of stakeholders: Algorithm designers dictate the definition of "fair," disconnecting the criteria from the people actually impacted by high-stakes automated decisions.
While asking non-technical stakeholders to write global mathematical fairness constraints is impractical, people naturally recognize fairness when evaluating concrete examples. Borrowing from philosophical notions of moral perception, the authors ask: Can we learn accurate models constrained directly by how stakeholders judge pairs of individuals?
Methods
The authors model stakeholder input as a set of directed pairwise constraints. For any pair of individuals $(A, B)$, a stakeholder can indicate:
- $A$ and $B$ must be treated similarly (assigned similar probabilities of a favorable outcome).
- $A$ must be treated at least as well as $B$.
- $B$ must be treated at least as well as $A$.
- No constraint / treat differently.
Crucially, this elicits relative fairness (how individuals are treated relative to each other) rather than absolute outcomes, leaving the learning algorithm to optimize for correctness.
Algorithmic Reductions and Relaxations
To accommodate real-world noise, conflicting preferences, and feasibility, the authors introduce two relaxation parameters:
- $\gamma$ (the $\ell_\infty$ buffer): The allowable difference in positive classification probabilities between a constrained pair before penalizing the model.
- $\eta$ (the $\ell_1$ budget): The total allowable average excess violation across all stakeholder constraints.
The resulting constrained empirical risk minimization (Fair ERM) problem is framed as a two-player zero-sum game over a Lagrangian:
- Dual player: Updates Lagrange multipliers ($\lambda$ for pairwise constraints and $\tau$ for total budget violations) using no-regret online learning (Exponentiated Gradient Descent and Online Gradient Descent).
- Primal player: Computes the best-response classifier using a standard Cost-Sensitive Classification (CSC) oracle, alongside optimal violation slack assignments $\alpha$.
The authors prove that this algorithm converges in a polynomial number of oracle calls, and they establish out-of-sample generalization bounds for fairness loss using an $\epsilon$-net discretization and Sauer’s lemma.
Datasets
- ProPublica COMPAS Recidivism Dataset: 5,829 criminal defendant records from Broward County, Florida (2013–2014) with features including age, sex, race, juvenile charges, prior criminal record, and charge severity, predicting two-year recidivism (46% base rate).
- Subjective Elicitation User Study: A newly collected dataset of fairness judgments from 43 undergraduate students. Each participant evaluated 50 randomly sampled pairs of defendants (showing features only, withholding recidivism labels), yielding 1,432 unique pairwise constraints.
Key Insights and Ideas
- No transitivity or consistency assumptions required: Stakeholders do not need to follow strict metric properties (like the triangle inequality) or agree with each other. The dual optimization naturally arbitrates conflicts.
- Pareto variability is driven by constraint nature, not quantity: The trade-off between accuracy and fairness varied wildly among human participants. Surprisingly, this variation was weakly correlated with the number of constraints or whether the pair had opposing true labels. Instead, the specific relationships between individual feature vectors drove the difficulty.
- A minority of constraints drive most error trade-offs: When pooling all 1,432 elicited constraints, allowing an average violation budget ($\eta$) revealed that the algorithm could achieve the unconstrained optimal classification error while satisfying roughly 75% of the constraints—demonstrating that difficulty is heavily concentrated in a small fraction of conflicting pairs.
Key Results
- Fast Convergence: Using a linear threshold heuristic as the CSC oracle, the algorithm consistently converged to optimal constrained error trajectories within 1,000 iterations.
- Diversity of Stakeholder Pareto Curves: When sweeping $\gamma$ from $0.0$ (strict parity) to $1.0$ (unconstrained), some participants produced near-linear worst-case trade-off curves, while others allowed large fairness gains with negligible accuracy penalties.
- Emergent Group Fairness: Enforcing individual subjective constraints naturally reduced group-level disparities: subjective fairness strongly correlated with a reduced false positive rate (FPR) gap between African-American and Caucasian defendants, though correlations were significantly weaker across other racial pairings.
Limitations and Future Work
- Subjectivity vs. Bias: If human annotators hold explicit or implicit prejudices, the learned classifier will operationalize those biases under the guise of "fairness." The authors emphasize that defining fairness subjectively shifts the burden to who is consulted and how queries are framed.
- Non-Representative Participant Pool: The empirical demonstration relied on university undergraduates rather than domain experts (e.g., legal scholars, judges) or directly impacted stakeholders (e.g., defendants and inmates).
- Scalability of Pairwise Queries: Because pairwise comparisons scale quadratically ($O(n^2)$), future work must investigate active query selection to identify the most informative pairs without placing undue cognitive burden on stakeholders.
Summary updated