Envy-Freeness Up to Any Item with High Nash Welfare: The Virtue of Donating Items

Ioannis Caragiannis, Nick Gravin, Xin Huang

TL;DR

This paper tackles the "holy grail" of fair division—Envy-Freeness up to any item (EFX)—by introducing a clever compromise: donating a small subset of items to charity. The authors prove that for any instance with additive valuations, one can always find an EFX allocation of the remaining items that preserves at least half of the maximum possible Nash welfare.

What Problem Does This Paper Address?

In the world of fair division, we often try to allocate indivisible items (like jewelry in an inheritance or tasks in a project) among agents with different preferences. The gold standard for fairness is Envy-Freeness (EF), where no agent prefers someone else's bundle over their own. Unfortunately, with indivisible items, EF is often impossible (e.g., two people, one car).

Researchers have turned to approximations. EF1 (envy-free up to one item) is well-understood and always exists. However, EFX (envy-free up to any item) is a much stronger and more desirable property, but its existence for more than two agents remains one of the biggest open problems in the field. This paper asks: If we can't guarantee EFX for all items, can we achieve it by "donating" a few items to a third party (like a charity) while still maintaining high economic efficiency?

Methods

The authors propose a purely combinatorial algorithm that uses Maximum Nash Welfare (MNW)—the allocation that maximizes the geometric mean of agents' valuations—as a starting point.

  1. The EFX Feasibility Graph: They construct a bipartite graph between agents and bundles. An edge exists if a bundle is "EFX-feasible" for an agent and they don't strictly prefer their original bundle.
  2. Iterative Donation: If a perfect matching isn't found, the algorithm identifies an agent's "robust demand" bundle (the bundle they'd like most 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.
  4. Efficiency Guarantee: By leveraging the mathematical properties of MNW allocations, they prove that the "loss" from these donations is bounded.

Datasets

Not discussed in the paper. As a theoretical work in computational social choice, the authors rely on mathematical proofs and a constructed counter-example rather than empirical datasets.

Key Insights and Ideas

  • Donation as a "Safety Valve": The paper reframes the EFX existence problem. Instead of forcing a complete allocation, it shows that "smart" donations can resolve the combinatorial deadlocks that usually make EFX so difficult to find.
  • MNW is a Powerful Seed: While MNW is known to be EF1 and Pareto-optimal, this paper demonstrates it is also an excellent starting point for EFX. The bundles in the final EFX allocation are always subsets of the initial MNW bundles.
  • The "Large Market" Effect: This is the first paper to apply large market assumptions to EFX. They show that as the value of individual items becomes small relative to the total (a "large market"), the efficiency loss from donating items vanishes, leading to near-optimal Nash welfare.
  • Tight Bounds: The authors provide a specific instance proving that their efficiency guarantee ($2^{-(n-1)/n}$, or roughly 1/2 for many agents) is the best possible for any EFX allocation, whether items are donated or not.

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 starts with an MNW (or a $\rho$-approximate MNW) allocation.
  • Large Market Performance: In markets where the maximum item value is at most an $\epsilon$ fraction of an agent's total value, the algorithm achieves an efficiency of $1 + 8\sqrt{\epsilon}$, which approaches 1 (perfect efficiency) as $\epsilon \to 0$.

Limitations and Future Work

  • The Existence Mystery: The paper bypasses the question of whether EFX exists for all items by allowing donations. The "big" question of EFX existence remains open.
  • Additive Valuations: The proofs rely on agents having additive valuations (where the value of a bundle is the sum of the values of its items). Extending this to more complex valuation functions (like submodular or general monotone) is a significant hurdle.
  • Monotonicity Conjecture: The authors suspect a "monotonicity property" exists—that adding an item to a problem never decreases the maximum possible Nash welfare of an EFX allocation. If proven, this would imply that EFX always exists for the full set of items.

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},
}

Loading related content...

Figure