Envy-freeness up to any item with high Nash welfare: The virtue of donating items

Ioannis Caragiannis, Nick Gravin, Xin Huang

Introduction

In the field of fair division, the allocation of indivisible items—such as heirlooms, tasks, or computing resources—presents a fundamental challenge. While Envy-Freeness (EF) is the gold standard, it is often mathematically impossible to achieve when items cannot be split. This paper addresses the "holy grail" of fair division: Envy-Freeness up to any item (EFX). The authors introduce a novel approach by allowing the donation of a small subset of items to charity, thereby guaranteeing an EFX allocation that maintains high economic efficiency.

The Challenge of EFX

Envy-Freeness (EF) requires that no agent prefers another's bundle over their own. With indivisible items, researchers typically settle for approximations like EF1 (envy-free up to one item). EFX is a significantly stronger property: an allocation is EFX if, for any two agents $i$ and $j$, agent $i$ does not envy agent $j$ after the removal of any single item from $j$'s bundle. While EF1 always exists, the existence of EFX for more than two agents remains one of the most prominent open problems in computational social choice.

Methodology: MNW and Iterative Donation

The authors propose a combinatorial algorithm that utilizes the Maximum Nash Welfare (MNW) allocation—the one that maximizes the geometric mean of agents' valuations—as its foundation. The process follows these steps:

  1. EFX Feasibility Graph: A bipartite graph is constructed between agents and bundles. An edge exists if a bundle is EFX-feasible for an agent and they do not strictly prefer their current bundle.
  2. Iterative Donation: If a perfect matching cannot be found, the algorithm identifies an agent's "robust demand" bundle (the bundle they would most prefer if their least-valued item were removed).
  3. Item Removal: The algorithm removes (donates) the least-valued item from that bundle and repeats the process until an EFX allocation is achieved.
Table 1: An example of additive valuations for three agents (Alice, Bob, Carol) over four items (c, r, p, n). Such instances often illustrate the difficulty of achieving EFX without item donation.

Key Insights and Ideas

Donation as a "Safety Valve"

The paper reframes the EFX existence problem. Instead of forcing a complete allocation of all items, it demonstrates that strategic donations can resolve the combinatorial deadlocks that typically prevent EFX allocations. This "safety valve" ensures that fairness can be achieved without sacrificing the core structure of the allocation.

MNW as a Powerful Seed

While MNW is known to be EF1 and Pareto-optimal, this research shows it is also an exceptional starting point for EFX. The final EFX bundles are always subsets of the initial MNW bundles, preserving much of the original efficiency.

The Large Market Effect

This work is the first to apply large market assumptions to EFX. In scenarios where the value of individual items is small relative to the total value (a "large market"), the efficiency loss from donating items effectively vanishes. As the maximum item value $\epsilon$ approaches zero, the efficiency approaches 1 (perfect efficiency).

Key Results

  • Existence & Efficiency: For $n$ agents with additive valuations, there always exists an EFX allocation of a subset of items with Nash welfare at least $2^{-(n-1)/n} \approx 0.5$ of the maximum possible.
  • Algorithmic Complexity: The proposed algorithm runs in polynomial time, provided it begins with an MNW (or a $\rho$-approximate MNW) allocation.
  • Tight Bounds: The authors provide specific instances proving that their efficiency guarantee is the best possible for any EFX allocation, regardless of whether items are donated.

Limitations and Future Work

While this paper provides a robust workaround, the fundamental question of whether EFX exists for all items remains open. Furthermore, the current proofs rely on additive valuations. Extending these guarantees to more complex valuation functions, such as submodular or general monotone functions, represents a significant hurdle for future research. The authors also conjecture a "monotonicity property"—that adding an item never decreases the maximum possible Nash welfare of an EFX allocation—which, if proven, would imply the universal existence of EFX.

Summary updated

Abstract

Several fairness concepts have been proposed recently in attempts to approximate envy-freeness in settings with indivisible goods. Among them, the concept of envy-freeness up to any item (EFX) is arguably the closest to envy-freeness. Unfortunately, EFX allocations are not known to exist except in a few special cases. We make significant progress in this direction. We show that for every instance with additive valuations, there is an EFX allocation of a subset of items with a Nash welfare that is at least half of the maximum possible Nash welfare for the original set of items. That is, after donating some items to a charity, one can distribute the remaining items in a fair way with high efficiency. This bound is proved to be best possible. Our proof is constructive and highlights the importance of maximum Nash welfare allocation. Starting with such an allocation, our algorithm decides which items to donate and redistributes the initial bundles to the agents, eventually obtaining an allocation with the claimed efficiency guarantee. The application of our algorithm to large markets, where the valuations of an agent for every item is relatively small, yields EFX with almost optimal Nash welfare. To the best of our knowledge, this is the first use of large market assumptions in the fair division literature. We also show that our algorithm can be modified to compute, in polynomial-time, EFX allocations that approximate optimal Nash welfare within a factor of at most $2ρ$, using a $ρ$-approximate allocation on input instead of the maximum Nash welfare one.
BibTeX
@inproceedings{caragiannis2019envy,
  author = {Ioannis Caragiannis and Nick Gravin and Xin Huang},
  title = {{Envy-freeness up to any item with high Nash welfare: The virtue of donating items}},
  booktitle = {EC},
  year = {2019},
  doi = {10.1145/3328526.3329574},
}
Figure