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:
- 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.
- 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).
- Item Removal: The algorithm removes (donates) the least-valued item from that bundle and repeats the process until an EFX allocation is achieved.
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