Source-linked AI summary
Envy-freeness up to any item with high Nash welfare: The virtue of donating items
Ioannis Caragiannis, Nick Gravin, Xin Huang
TL;DR
With indivisible goods, EFX existence is unresolved in general. This paper uses item donations starting from a maximum-Nash-welfare allocation to obtain EFX allocations, showing a tight half-optimum welfare guarantee for additive valuations.
Problem
EFX is a compelling fairness notion for indivisible goods, but its existence is unknown in general.
Source: §1 · pp. 1–2Method
Starting from a maximum-Nash-welfare allocation, the algorithm donates items and returns an EFX allocation of the remaining items.
Source: §1 · pp. 2–3Results
At least half the optimal Nash welfare for the original items is attainable by an EFX allocation of a subset, and this bound is best possible.
Source: §1 · p. 3Takeaways & Limitations
Item donations can preserve exact EFX while retaining a substantial welfare guarantee for the allocated items.
Source: §1 · pp. 2–3Whether EFX allocations of all items always exist remains open.
Source: §7 · p. 18
Abstract
from arXiv · showhide
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\rho$, using a $\rho$-approximate allocation on input instead of the maximum Nash welfare one.
1 INTRODUCTION
With indivisible goods, envy-freeness may be unattainable, and EFX allocations are not known to always exist. The paper asks whether donating items can yield EFX while preserving high Nash welfare, and proposes an algorithm starting from a maximum-Nash-welfare allocation.
1 INTRODUCTION
- The algorithm donates items from a maximum-Nash-welfare allocation to produce an EFX allocation with at least half the original optimum welfare; this bound is best possible.The remaining bundles are subsets of the agents’ initial bundles, and large markets yield almost optimal welfare.Source: §1 · pp. 2–3
- The algorithm removes items without reallocating them between initial bundles, seeking a complete EFX matching while ensuring the matching never shrinks.The authors contrast this combinatorial approach with convex programming, rounding, duality, and item-price techniques.Source: §1 · p. 3
- Donating items preserves the precise EFX definition while approximating efficiency, unlike approaches that approximate EFX itself.The authors suggest item donations may also help study other fairness-efficiency trade-offs.Source: §1 · p. 3
1.1 Related work
- EF1 allocations are always achievable, but the existence of EFX allocations remains open beyond a few special cases.Prior work establishes EFX in two-agent and identical-valuation settings, while other work studies approximate EFX notions.Source: §1 · pp. 1–2, §1.1 · p. 4
- Nash welfare balances fairness and efficiency, but maximizing it for indivisible goods is APX-hard and has motivated constant-factor approximation algorithms.In the divisible setting, convex programming can maximize Nash welfare and yield envy-free allocations.Source: §1 · p. 2, §1.1 · p. 4
1.2 Roadmap
- The paper proceeds from formal definitions and a lower bound to its main algorithm, extensions to suboptimal input and large markets, then open problems.The authors also position their results as a price-of-fairness analysis.Source: §1.2 · p. 4, §1.1 · p. 4
2 PRELIMINARIES
The preliminaries specify additive valuations, allocation and fairness concepts, and the Nash-welfare objective. They also define large-market conditions used to qualify later results.
2 PRELIMINARIES
- Valuations are additive, and an allocation assigns each agent a bundle in a partition of the allocated items.The paper uses the geometric mean of agents’ bundle values as Nash welfare and compares it with the optimum over the original item set.Source: §2 · p. 5
- EFX requires each agent to value their own bundle at least as highly as the other agent’s bundle after removal of any one item.EF1 instead requires that condition after removing some item.Source: §2 · p. 5
- The goal is an EFX allocation with high Nash welfare, measured against the optimum for the original item set.An allocation is α-efficient when α times its Nash welfare is at least that optimum.Source: §2 · p. 5
- A large-market condition bounds each item’s value to an agent by a small fraction of that agent’s total value for all items.The paper also uses a weaker condition relative to each agent’s bundle in an optimal Nash-welfare allocation.Source: §2 · p. 5
3 A LOWER BOUND ON THE NASH WELFARE OF EFX ALLOCATIONS
This section establishes a lower bound on the Nash welfare attainable by EFX allocations, even when items may be donated. Its construction makes EFX constrain how agents can bundle large-valued items.
3 A LOWER BOUND ON THE NASH WELFARE OF EFX ALLOCATIONS
- For some instances, every EFX allocation of any subset of items sacrifices almost half the optimal Nash welfare.The text presents this as a lower bound applying whether or not items are donated.Source: §3 · p. 6
- The construction uses n agents and 2n−1 items, with valuations distinguishing large-valued items from others.The valuation specification assigns value 1 to items in {1, ..., n−1}, while other values depend on the agent and item.Source: §3 · p. 6
- Under EFX, an agent receiving a large item cannot bundle it with another item, and the resulting allocation has Nash welfare at most 1.The proof combines this constraint with an upper bound on the instance’s optimal Nash welfare.Source: §3 · p. 6
4 MAIN ALGORITHM
Starting from a maximum Nash welfare allocation, the algorithm repeatedly removes items and matches the remaining bundles to agents. It returns an EFX allocation with at least half the original optimum Nash welfare, using only subsets of the initial bundles.
4 MAIN ALGORITHM
- At least half the original optimum Nash welfare is retained in the returned EFX allocation.The algorithm runs in polynomial time.Source: §4 · pp. 7, 11
- The algorithm starts from a maximum Nash welfare allocation and only removes items, so each agent's final bundle is a subset of their initial bundle.The algorithm does not reallocate items between initial bundles.Source: §4 · pp. 7, 11
- Each round matches bundles to agents in an EFX-feasibility graph, prioritizing touched bundles, original assignments, and then matching size.An edge represents an agent-bundle assignment that is EFX feasible and, for a different bundle, gives the agent greater value than their own current bundle.Source: §4 · p. 7
- When the matching is incomplete, the algorithm selects an unmatched agent's robust-demand bundle and removes that agent's least-valued item from it.The resulting bundle is EFX feasible for that agent in the next round.Source: §4 · pp. 7–8
- The algorithm terminates with a complete matching, which yields an EFX allocation, and it runs in polynomial time.It removes at most one item per iteration and uses weighted matching to implement its matching priorities.Source: §4 · pp. 7–9
- The final allocation is Pareto optimal: restoring each agent's removed items would turn any Pareto improvement into one of the initial maximum-welfare allocation.Source: §4 · p. 11
5 SUBOPTIMAL INPUT ALLOCATION
The modified algorithm uses an efficient input allocation to produce an EFX allocation or a higher-welfare allocation for another iteration. Repetition yields a polynomial-time 2ρ-efficient EFX allocation from a ρ-efficient starting allocation.
5 SUBOPTIMAL INPUT ALLOCATION
- Each round seeks a matching in the EFX-feasibility graph, removes items from robust-demand bundles, and may alter the matching along an augmenting path.When the selected bundle's value falls below the specified threshold relative to its initial bundle, the algorithm returns an improved allocation instead.Source: §5 · p. 12
- The modified algorithm preserves matching properties by checking that the replacement edge remains in the EFX-feasibility graph.The change swaps a matching edge along the augmenting path before removing an item from the selected bundle.Source: §5 · pp. 12–13
- An EFX output Y satisfies (2+δ1)^(1−1/n) · NW(Y) ≥ NW(X), where X is the current input allocation.At least one bundle remains untouched and retains its value from X.Source: §5 · pp. 13–14
- If the algorithm instead returns bX, its Nash welfare is at least (1+δ)^(1/n)·NW(X), enabling another iteration with improved input.The algorithm stops when it returns an EFX allocation; repeated improvements take polynomial time.Source: §5 · pp. 12, 14
- A ρ-efficient input yields a 2ρ-efficient EFX allocation after at most O(n^2) executions of Algorithm 2.The guarantee applies when the input allocation is efficient, not necessarily optimal.Source: §5 · pp. 12, 14
6 LARGE MARKETS
Under the large-market condition, Algorithm 1 returns an EFX allocation with a Nash-welfare guarantee approaching optimality as ε decreases. Its proof uses greedy transfers between consecutive bundles to balance agents' valuations.
6 LARGE MARKETS
- A large-market input satisfying the condition with parameter ε yields a (1+8√ε)-efficient EFX allocation.The guarantee is stated for the Nash-welfare-maximizing initial allocation.Source: §6 · p. 14
- For large markets, Algorithm 1 outputs an EFX allocation Y satisfying (1 + 8√ε)NW(Y) ≥ (1 + 8√ε)NW(Z) ≥ NW(X) = opt(M).Source: §6 · p. 17
- Greedy transfers move an initial segment of items from one bundle to the preceding bundle, with relative value gain exceeding the neighboring agent's relative loss.The analysis considers simultaneous transfers across consecutive agent pairs to improve Nash welfare.Source: §6 · p. 15
- The feasible transfer amounts have gaps of at most 2ε, allowing reallocations to bring bundle-value imbalances closer together.The proof uses this granularity to construct reallocations that improve the Nash-welfare comparison.Source: §6 · p. 16
7 DISCUSSION AND OPEN PROBLEMS
The discussion proposes combining Algorithm 2 with a local-search procedure to reallocate removed items, and identifies all-item EFX existence as an open problem. The authors conjecture a monotonicity property that would imply existence and a welfare guarantee for all-item EFX allocations.
7 DISCUSSION AND OPEN PROBLEMS
- Applying Lipton et al.'s local-search algorithm to items removed by Algorithm 2 could yield an EF1 allocation of all items.The authors present this as a possible use of their techniques.Source: §7 · pp. 17–18
- Whether EFX allocations of all items always exist remains open.The authors conjecture that adding an item to a problem with an EFX allocation preserves an EFX allocation with at least as high Nash welfare.Source: §7 · p. 18
- If that conjectured monotonicity holds, Theorem 2 would imply that the best all-item EFX allocation is 2^(1−1/n)-efficient.Source: §7 · p. 18