Fairness in Limited Resources Settings

1. Problem Statement

The paper addresses the challenge of fairness in machine learning decisions where resources are strictly limited. In many critical societal domains (e.g., medical triage, educational scholarships, grant funding), algorithms must allocate a fixed capacity $c$ to individuals based on predicted risk or utility.

The core problem arises when there are information gaps between different demographic groups (e.g., Group $S_1$ has high-quality data, while Group $S_2$ has sparse or noisy data).

• The Conflict: A purely utility-maximizing algorithm (maximizing True Positives) will naturally allocate almost all resources to the group with better information ($S_1$) because it can identify high-risk individuals more accurately.
• The Risk: Standard fairness definitions, when applied to this constrained setting, may lead to extreme inefficiencies. The authors demonstrate that enforcing strict fairness (like Equal Opportunity or Max-Min Fairness) in the presence of information gaps can force the algorithm to allocate the majority of resources to the less informed group ($S_2$), causing the total utility (True Positive Count) to drop drastically or even approach zero. This phenomenon is termed an unbounded "Price of Fairness."

2. Methodology and Framework

The authors formalize the problem using a two-step decision process:

1. Prediction: A predictor $p: \mathcal{X} \to [0, 1]$ estimates the probability of a positive outcome ($y=1$).
2. Allocation: A post-processing function (specifically a randomized group threshold function $\tau$) converts predictions into allocations $f(x) \in [0, 1]$ subject to a global capacity constraint $c$.

Key Definitions and Adaptations:

• Utility: Defined as the True Positive Count ($E[f(x)y]$), representing the total number of successful resource allocations.
• Tail Dominance: A formalization of information gaps where one group ($S_1$) has a "heavier tail" in its prediction distribution than another ($S_2$), meaning $S_1$ has more high-confidence predictions.
• Adapted Resource Allocation Definitions: The authors adapt classical economic fairness definitions to the prediction setting by treating demographic groups as "agents" with utility functions based on their group's True Positive Count.
  • Max-Min Fairness: Maximizes the minimum True Positive Count across groups.
  • Proportional Fairness: Maximizes the weighted sum of log-utilities (normalized by group size).

3. Key Contributions

A. Theoretical Connections

The paper establishes rigorous connections between algorithmic fairness definitions and resource allocation theory:

• Equal Opportunity vs. Max-Min: Under conditions of equal base rates and non-degenerate settings, satisfying Equal Opportunity is equivalent to satisfying Max-Min Fairness.
• Proportional Fairness as Regularization: The authors prove that maximizing Proportional Fairness is mathematically equivalent to maximizing a specific objective function:
  $$\text{Prop} \approx -D_{KL}(Q_S, Q_f) + \log(\text{True Positive Count})$$
  Where $D_{KL}$ is the Kullback-Leibler divergence between the group distribution and the allocation distribution. This reveals that Proportional Fairness acts as a multiplicative regularization term that balances fairness (distance from Max-Min) and utility (log of total True Positives).

B. Analysis of the "Price of Fairness"

The authors quantify the cost of enforcing fairness constraints:

• Unbounded Price for Equal Opportunity/Max-Min: They prove that in settings with information gaps (tail dominance), enforcing Equal Opportunity or Max-Min Fairness can force the allocation to the group with less information. In extreme cases, this causes the True Positive Count to vanish, resulting in an unbounded price of fairness.
• Bounded Price for Proportional Fairness: In contrast, they show that Proportional Fairness guarantees a bounded price of fairness. Specifically, the utility achieved is at least half of the optimal utility (in equal-sized groups), ensuring that resources are never wasted entirely on low-probability candidates.

C. New Fairness Definitions

To resolve the trade-off between fairness and utility, the authors propose new definitions:

1. Achievable Equal Opportunity: Instead of equalizing the True Positive Rate for all individuals with $y=1$, this definition equalizes the rate only for the "achievable set"—the subset of positive individuals that could be reached if all resources were allocated to that specific group.
   • Result: This definition admits a bounded price of fairness (specifically, the utility is at least $1/m$ of the optimal, where $m$ is the number of groups).
2. Generalized Proportional Fairness: A variant of proportional fairness adapted to the achievable set, also guaranteeing bounded efficiency loss.

4. Key Results and Findings

• Simulation Evidence: The authors provide simulations (Figures 1-3) demonstrating that:
  • Standard Max-Min/Equal Opportunity allocations in high-variance gaps result in allocating >75% of resources to the poorly informed group, drastically reducing total success rates.
  • Proportional Fairness acts as a "middle ground," allocating resources more evenly while maintaining a significant portion of the total utility.
• Theoretical Bounds:
  • Theorem 5.1 & 5.3: Prove that under tail dominance, Max-Min and Equal Opportunity allocate resources inversely to information quality.
  • Theorem 5.5: Proves that Proportional Fairness ensures $E[\text{TP}_{\text{prop}}] \geq \frac{1}{2} E[\text{TP}_{\text{opt}}] - \alpha$.
  • Claim 6.4: Proves that Achievable Equal Opportunity ensures $E[\text{TP}_{\text{ach}}] \geq \frac{1}{m} E[\text{TP}_{\text{opt}}]$.

5. Significance and Implications

• Contextualizing Fairness: The paper highlights that fairness definitions developed for unconstrained settings (like standard Equal Opportunity) can be detrimental in limited-resource scenarios. Blindly applying them can lead to "fair" but useless outcomes where no one is helped.
• Design of Robust Algorithms: The work suggests that Proportional Fairness and Achievable Equal Opportunity are superior choices for resource allocation problems. They provide a theoretical guarantee that fairness enforcement will not completely destroy the utility of the system.
• Multiplicative Regularization: The identification of proportional fairness as a multiplicative regularizer offers a new perspective for machine learning practitioners, suggesting that fairness constraints should be integrated into the loss function in a way that scales with utility, rather than as a hard additive constraint.

In summary, this paper provides a critical theoretical framework for designing fair machine learning systems in resource-constrained environments, proving that while some standard fairness metrics fail catastrophically under information asymmetry, adapted definitions like Proportional Fairness and Achievable Equal Opportunity offer robust, bounded trade-offs.