This NeurIPS 2019 paper by Paul Gölz, Anson Kahng, and Ariel D. Procaccia explores the intersection of machine learning fairness and classical economics. It investigates whether the popular "equalized odds" fairness metric can play nice with the common-sense rules of fair resource allocation when resources are limited.
The Problem: Fairness Under Constraints
Most machine learning fairness research assumes we are just "labeling" people (e.g., is this person a credit risk?). However, in the real world, we often face a cardinality constraint: we only have $k$ loans to give, $k$ spots in a university, or $k$ units of a specific resource.
When resources are limited, we enter the realm of Fair Division, a subfield of economics. Fair division relies on "axioms"—logical rules designed to prevent paradoxes. For example, if a school suddenly gets more funding to admit more students, no previously qualified student should suddenly lose their spot. This principle is called "Resource Monotonicity."
The authors ask a critical question: If we insist on Equalized Odds (ensuring true positive and false positive rates are the same across different demographic groups), do we run into "paradoxes" where these basic economic axioms are violated?
Methods: A Geometric Approach
The authors model the problem as the allocation of a divisible good (like financial aid or probability of admission) to agents partitioned into groups. They use a geometric interpretation of equalized odds to analyze the problem:
- Signatures: Every allocation has a "signature," which is a point in a 2D plane representing the True Positive Rate versus the False Positive Rate.
- The Maximum Curve: They characterize the set of all possible fair signatures and identify a "maximum curve." This curve represents the most efficient (highest true positive) allocations for any given resource level.
- Axiomatic Testing: They mathematically test if the optimal "equalized odds" allocation can satisfy three relational axioms:
- Resource Monotonicity: Increasing the total resource $k$ shouldn't decrease anyone's individual allocation.
- Consistency: If some people leave with their allocated share, the rule should give the remaining people the same amount they were originally promised.
- Population Monotonicity: If a new person joins the pool, existing people shouldn't suddenly get more (since the resource is fixed).
Key Insights: Axioms vs. Equalized Odds
- The "Free" Axiom: Surprisingly, Resource Monotonicity is "free." The authors provide a recursive algorithm that reorders allocation segments to ensure that as you increase the number of loans available, no one's chance of getting a loan decreases, all while maintaining maximum efficiency and equalized odds.
- The Consistency Trap: Consistency is a deal-breaker. The authors prove that the only allocation rule that satisfies both equalized odds and consistency is "uniform allocation" (giving everyone the same chance regardless of their merit or score). This is a strikingly negative result because uniform allocation is highly inefficient.
- The Population Paradox: Population Monotonicity is also highly restrictive. If you want to ensure that a student's financial aid doesn't drop just because another student declined their admission (a common-sense requirement), you have to sacrifice a massive amount of accuracy and efficiency.
Empirical Results
The authors evaluate their findings using the FICO credit score dataset, which includes 174,047 individuals across four racial groups (White, Black, Hispanic, Asian), with the task of predicting credit delinquency.
- Efficiency Cost: Enforcing equalized odds and resource monotonicity results in only a small efficiency penalty—less than 3.5% compared to a totally "unfair" profit-maximizing algorithm.
- The Price of Monotonicity: However, trying to satisfy population monotonicity forces the algorithm to behave almost like a uniform allocator. In the FICO case, this leads to an efficiency loss of up to 30%.
- Theoretical Proofs: The paper provides formal proofs showing that equalized odds is mathematically incompatible with the core relational axioms used in social choice theory.
Limitations and Future Work
- Calibration Assumption: The model assumes the starting point is a "calibrated" classifier (one where a 70% score actually means a 70% chance of success). In reality, many classifiers are uncalibrated.
- Divisible vs. Indivisible: While the paper treats the resource as divisible (like money), many real-world decisions are binary (Yes/No). Although the Birkhoff-von Neumann theorem allows this to be viewed as a lottery, the psychological impact of "lottery fairness" versus "deterministic fairness" is quite different.
- The "Tenable Standard" Question: The authors conclude that these paradoxes strengthen the case against equalized odds as a universal standard for fair ML, suggesting we may need different metrics for resource-constrained settings.
Summary updated