Abstract
In resource allocation, a fundamental tension exists between maximizing total utility (efficiency) and ensuring fairness, often measured by envy-freeness. This paper introduces a novel framework that models this trade-off as a variant of semi-discrete Optimal Transport (OT). By introducing a "budget" for envy, the authors enable a continuous trade-off between social welfare and fairness. We present a practical stochastic algorithm with rigorous statistical guarantees and demonstrate its effectiveness on both artificial data and a real-world blood donation matching simulator.
Introduction
Planners in domains ranging from healthcare (blood donor matching) to digital advertising (ad placement) must balance efficiency with fairness. Envy-freeness—the condition where no recipient prefers another's allocation—is a gold standard for fairness but often incurs a significant "Price of Fairness" in terms of lost efficiency. This work bridges the gap between zero-fairness and perfect envy-freeness by allowing planners to specify a tolerated level of envy, optimizing for the highest possible efficiency within that constraint.
A Geometric Approach to Fairness
The authors formulate the allocation problem through the lens of semi-discrete Optimal Transport. They prove that the optimal allocation policy follows a geometric structure known as Laguerre cells. In this framework, the space of item valuations is partitioned by hyperplanes. An item is assigned to a recipient based on a "greedy" selection after adjusting their valuation by dual variables. These variables act as "shadow prices," accounting for both the target distribution and the envy budget.
As the envy constraint becomes stricter, these decision boundaries "tilt." This shift forces the system to split "good" items—those highly valued by multiple parties—more evenly, even if one party values them slightly more than the other.
Learning the Optimal Policy
To find the optimal dual variables, the authors propose a Projected Stochastic Gradient Descent (SGD) algorithm. This approach is particularly robust because it only requires single samples from the valuation distribution, avoiding the need for complex integration over unknown distributions. The algorithm has a provable convergence rate of $O(1/\sqrt{T})$.
Theoretical analysis using the fat-shattering dimension (a generalization of VC dimension) shows that the sample complexity scales linearly with the number of recipients ($n$), specifically $\tilde{O}(n/\epsilon^2)$. This ensures that the policy can be learned efficiently even in high-dimensional settings.
Empirical Performance
The framework was evaluated using artificial two-recipient data and a high-fidelity blood donation matching simulator for San Francisco involving five blood banks.
A key finding is the existence of a "knee" in the efficiency-envy curve: in artificial tests, paying only 50% of the efficiency cost required for perfect fairness reduced envy by 65%. This suggests that a small compromise in efficiency can lead to a large gain in perceived fairness. In the blood donation simulator, the welfare gap remained remarkably small even under strict envy-freeness constraints, suggesting that real-world distributions may naturally support fairer outcomes without drastic efficiency losses.
Conclusion and Future Work
This work demonstrates that Optimal Transport provides a powerful mathematical language for navigating the efficiency-fairness trade-off. While the current model assumes the central planner knows recipient valuations, future work will explore "incentive-compatible" OT for settings where recipients might misreport preferences. Additionally, extending this to dynamic, non-stationary environments remains an open challenge. Nevertheless, this framework offers a practical and theoretically grounded tool for central planners to implement nuanced fairness policies.
Summary updated