Abstract
We consider settings in which the right notion of fairness is not captured by simple mathematical definitions (such as equality of error rates across groups), but might be more complex and nuanced and thus require elicitation from individual or collective stakeholders. We introduce a framework in which pairs of individuals can be identified as requiring (approximately) equal treatment under a learned model, or requiring ordered treatment such as "applicant Alice should be at least as likely to receive a loan as applicant Bob". We provide a provably convergent and oracle efficient algorithm for learning the most accurate model subject to the elicited fairness constraints, and prove generalization bounds for both accuracy and fairness. This algorithm can also combine the elicited constraints with traditional statistical fairness notions, thus "correcting" or modifying the latter by the former. We report preliminary findings of a behavioral study of our framework using human-subject fairness constraints elicited on the COMPAS criminal recidivism dataset.
Introduction
Most research in algorithmic fairness relies on "analytic" definitions—mathematical formulas like statistical parity or equalized odds. While these metrics are computationally convenient, they are often criticized for being too blunt to capture the nuanced, context-dependent nature of human fairness. Furthermore, these definitions are typically selected by researchers or engineers rather than the stakeholders actually affected by the algorithmic decisions. This creates a gap in both complexity and agency.
This paper addresses these gaps by proposing a framework for fairness elicitation. Instead of imposing a top-down mathematical rule, the framework allows stakeholders to define fairness through simple, intuitive pairwise comparisons. By moving the definition of fairness from a global formula to a set of local, subjective constraints, the authors provide a method to incorporate human values directly into the machine learning pipeline.
The Fairness Elicitation Framework
The core of the proposed framework is the elicitation of constraints from non-technical stakeholders. Rather than asking a user to define a general rule, the system presents pairs of individuals and asks for a judgment on their relative treatment. For any two individuals A and B, a stakeholder can choose from four options:
- Treat Same: Both individuals must receive the same classification.
- A ≥ B: Individual A should be at least as likely as B to receive a favorable outcome.
- B ≥ A: Individual B should be at least as likely as A to receive a favorable outcome.
- No Constraint: The model is free to treat the individuals as it sees fit based on other criteria.
This approach draws a sharp distinction between fairness and justice. In this framework, "fairness" is viewed as a measure of relative outcomes (equality or ordering), while "justice" is treated as absolute correctness (optimizing for ground-truth labels). By allowing humans to handle the relative ordering, the algorithm can focus on the optimization task of minimizing error subject to those human-defined constraints.
The Fair ERM Algorithm
To implement this framework, the authors frame the learning problem as a zero-sum game between two players:
- The Primal Player: This player attempts to find a model that minimizes classification error.
- The Dual Player (The Auditor): This player attempts to identify where the current model violates the elicited fairness constraints.
The authors prove that this process is oracle-efficient, meaning it reduces the complex constrained optimization problem into a series of standard weighted classification tasks. To handle the inherent noise in human judgment, the algorithm includes two relaxation parameters:
- γ (Gamma): A buffer for individual violations, allowing for a specific amount of "slack" per pair.
- η (Eta): A budget for the total expected violation across the entire population.
Theoretical and Empirical Results
A major theoretical contribution of this work is the proof that fairness generalizes. Using VC-dimension and ε-net arguments, the authors demonstrate that if a model is fair on a small sample of pairs provided by a stakeholder, it will remain fair on the broader population with high probability. This ensures that the subjective notions elicited from a limited interaction can be reliably applied to unseen data.
Behavioral Study on COMPAS
The authors conducted a behavioral study using the COMPAS criminal recidivism dataset to test the framework. They collected fairness constraints from 43 human subjects (undergraduates) via a web application. Each subject was presented with 50 random pairs of individuals and asked to provide judgments based on features such as age, race, and criminal history.
Key findings from the study include:
- Subject Variability: There was significant variation in how difficult it was to satisfy different subjects. Some subjects' constraints led to nearly linear trade-offs between accuracy and fairness, while others allowed for significant fairness gains with minimal accuracy loss.
- The Pareto Frontier: By varying the relaxation parameters, the authors plotted the trade-off between accuracy and specific subjective views of fairness. This revealed that some fairness notions are "cheaper" to implement than others in terms of predictive performance.
- The "Few Bad Apples" Effect: The difficulty in balancing accuracy and fairness was often driven by a small fraction (roughly 25%) of the collective constraints. Removing or relaxing these specific constraints often allowed the model to satisfy the majority of the stakeholder's preferences without a major drop in accuracy.
- Alignment with Standard Metrics: Interestingly, subjective fairness elicited from humans correlated well with reducing the False Positive Rate (FPR) gap between Black and White defendants, suggesting that human intuition often aligns with certain analytic metrics even when those metrics are not explicitly invoked.
Conclusion and Future Work
While the framework provides a robust method for eliciting and enforcing subjective fairness, several challenges remain. The current study relied on a proxy group (undergraduates) rather than actual stakeholders like judges or community members. Future work is needed to explore how to aggregate conflicting fairness notions from a diverse panel of stakeholders into a single, cohesive model. Additionally, determining the most efficient way to select pairs for querying remains an open research question. Nonetheless, this framework represents a significant step toward making algorithmic fairness more participatory and context-aware.
Summary updated