On Optimal Tradeoffs between EFX and Nash Welfare

Michal Feldman, Simon Mauras, Tomasz Ponitka

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.

Comparison of tradeoffs for additive and subadditive valuations. The plots illustrate the regions where complete allocations are guaranteed and highlight the open question for subadditive valuations when $\alpha > 1/2$.

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

Abstract

A major problem in fair division is how to allocate a set of indivisible resources among agents fairly and efficiently. The goal of this work is to characterize the tradeoffs between two well-studied measures of fairness and efficiency --- envy freeness up to any item (EFX) for fairness, and Nash welfare for efficiency --- by saying, for given constants α and β, whether there exists an α-EFX allocation that guarantees a β-fraction of the maximum Nash welfare (β-MNW). For additive valuations, we show that for any α ∈ [0,1], there exists a partial allocation that is α-EFX and 1/(α+1)-MNW. This tradeoff turns out to be tight (for every α) as demonstrated by an impossibility result that we give. We also show that for α ∈ [0, φ-1 ≃ 0.618] these partial allocations can be turned into complete allocations where all items are assigned. Furthermore, for any α ∈ [0, 1/2], we show that the tight tradeoff of α-EFX and 1/(α+1)-MNW with complete allocations holds for the more general setting of subadditive valuations. Our results improve upon the current state of the art, for both additive and subadditive valuations, and match the best-known approximations of EFX under complete allocations, regardless of Nash welfare guarantees. Notably, our constructions for additive valuations also provide EF1 and constant approximations for maximin share guarantees.
BibTeX
@inproceedings{feldman2024optimal,
  author = {Michal Feldman and Simon Mauras and Tomasz Ponitka},
  title = {{On Optimal Tradeoffs between EFX and Nash Welfare}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i9.28826},
}
Figure