Introduction
In the domain of fair division, researchers strive to balance individual fairness with global efficiency. Two primary metrics define this landscape: Envy-Freeness up to any item (EFX) and Maximum Nash Welfare (MNW). While EFX ensures that no agent envies another after the hypothetical removal of any single item, MNW seeks to maximize the geometric mean of agent utilities, balancing total welfare with equity. This paper provides a complete characterization of the Pareto frontier between these two often-conflicting goals.
The Universal Tradeoff Formula
The central contribution of this work is the discovery of a mathematically tight tradeoff: for any fairness level $\alpha$ (where an allocation is $\alpha$-EFX), one can guarantee a fraction $\beta$ of the maximum Nash welfare, defined by:
$$\beta = \frac{1}{\alpha + 1}$$
This formula implies that if a system requires 50% EFX ($\alpha = 0.5$), it can still maintain at least 66.7% of the optimal Nash Welfare. The authors demonstrate that this bound is "tight," meaning no algorithm can guarantee a higher efficiency for a given level of fairness across all possible instances.
Algorithmic Framework
The authors achieve these bounds through a constructive algorithmic approach involving several key innovations:
- The Shrinking Approach: For additive valuations, the process begins with an MNW allocation. Bundles are iteratively "shrunk" by removing items that cause envy and reassigning them to unmatched agents until the desired $\alpha$-EFX property is satisfied.
- Envy-Cycle Elimination: To transition from partial to complete allocations (where all items are assigned), the authors utilize a modified envy-cycle procedure.
- $\gamma$-separation: A novel technical condition ensuring that bundle values remain significantly higher than unallocated items, allowing the completion of allocations without violating fairness or efficiency constraints.
Valuation Classes and Completeness
The applicability of the $1/(\alpha+1)$ tradeoff varies depending on the nature of agent preferences and the requirement for complete allocations.
As shown in Figure 3, for additive valuations, complete allocations achieving the optimal tradeoff are guaranteed for $\alpha \le \varphi - 1 \approx 0.618$. Beyond this threshold, the efficiency guarantee still holds, but some items may remain unallocated (partial allocations). For the broader class of subadditive valuations, the tradeoff holds for complete allocations up to $\alpha = 1/2$.
Conclusion and Future Work
While this research closes the question for additive valuations, several avenues remain open. Most notably, a "gap" exists for subadditive valuations when $\alpha > 1/2$, where it is currently unknown if the $1/(\alpha+1)$ bound persists or if a different tradeoff emerges. Additionally, while the algorithms are polynomial-time, they require an MNW allocation as a starting point—a problem that is itself NP-hard. Future research may focus on bridging these gaps and exploring the tradeoff under approximate MNW inputs.
Summary updated