Source-linked AI summary
EFX Exists for Three Agents
Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn
TL;DR
The paper tackles the unresolved existence of EFX allocations for three agents with additive valuations. It develops a constructive, algorithmic proof and shows that a partial EFX allocation can have higher Nash welfare than any complete EFX allocation, falsifying a prior conjecture. The results establish existence in the three-agent additive setting while exposing limits on efficiency guarantees and on extending the approach beyond additive valuations.
Problem
Whether EFX allocations always exist remained open beyond two agents, despite known results for identical valuations and two-agent instances.
Method
The paper gives a constructive algorithm that starts from an empty EFX allocation and repeatedly finds dominating allocations until reaching a complete EFX allocation.
Results
EFX allocations always exist for three agents with additive valuations, while a partial EFX allocation can have higher Nash welfare than every complete EFX allocation.
Takeaways & Limitations
The proof advances the existence question for three agents and identifies barriers to obtaining efficient complete EFX allocations through iterative improvement.
Takeaways & Limitations
The proofs crucially use additivity and do not work for more general valuations such as submodular or subadditive valuations.
Abstract
from arXiv · showhide
We study the problem of distributing a set of indivisible items among agents with additive valuations in a $\mathit{fair}$ manner. The fairness notion under consideration is Envy-freeness up to any item (EFX). Despite significant efforts by many researchers for several years, the existence of EFX allocations has not been settled beyond the simple case of two agents. In this paper, we show constructively that an EFX allocation always exists for three agents. Furthermore, we falsify the conjecture by Caragiannis et al. by showing an instance with three agents for which there is a partial EFX allocation (some items are not allocated) with higher Nash welfare than that of any complete EFX allocation.
1 Introduction
The paper addresses the unresolved existence of EFX allocations for three agents with additive valuations and establishes existence constructively. It also shows that complete EFX allocations can be less efficient than partial ones under Nash welfare.
- Fairness notions: EFX requires envy to disappear after removing any item from another agent’s bundle, making it stricter than EF1.Every EFX allocation is EF1, but the converse need not hold.
- Open problem: EFX existence was known for identical valuations and two agents, but remained open for three agents with additive valuations.Prior work described the three-agent case as highly non-trivial.
- Main contribution: Theorem: EFX allocations always exist for three agents with additive valuations.The proof is constructive and algorithmic, yielding a pseudo-polynomial algorithm.
- Efficiency: The paper disproves Caragiannis et al.’s conjecture that adding an item preserves an EFX allocation with at least as high Nash welfare.That conjecture would have implied an efficient complete EFX allocation.
- Efficiency: A partial EFX allocation can have higher Nash welfare than every complete EFX allocation, limiting iterative approaches that improve allocations through Pareto domination or welfare.The authors identify this as a barrier for existing techniques toward complete EFX allocations.
- Technical perspective: The technical discussion highlights splitting bundles as a prior strategy that works for identical valuations but relies crucially on that assumption.The strategy repeatedly moves an item from an envied bundle to the lowest-valued bundle.
2 Preliminaries and Technical Overview
The technical framework represents three-agent additive fair-division instances through envy relations and carefully chosen dominance-improving reallocations. It uses perturbation, most-envious agents, champion graphs, and structural cases to reach a complete EFX allocation.
- Instance model: The analysis assumes three agents, indivisible goods, and additive valuation functions, with non-degenerate instances handled through a perturbation argument.The perturbation preserves the relevant EFX implication for the original instance.
- Envy measurement: A most-envious agent is one needing the smallest cardinality subset of an envied bundle to prefer it to their own bundle.Smaller κX(i,S) indicates greater envy.
- Champions and champion graph: For any unallocated good g, every bundle Xi ∪ g has at least one most-envious agent, and the resulting champion graph is cyclic.The graph contains an edge when an agent is most envious of another agent’s bundle augmented by g.
- Champion structure: When an agent champions another agent, additive valuations identify a largest removable subset Gij while preserving the champion’s envy.This subset can be found by removing the least valuable goods for the champion until the maximum removable cardinality is reached.
- Dominating updates: If the envy graph has a single source or the champion graph has a 1-cycle, an EFX allocation exists that Pareto dominates the current allocation and strictly improves the source agent.These are the first structural cases used to make progress toward completion.
3 Existence of EFX: Three sources in EX
When the envy graph has three sources, the proof transforms a partial EFX allocation into an EFX allocation that dominates it. The transformations handle champion-graph configurations through swaps, cyclic shifts, and reallocations.
- 2-cycle in MX: When the champion graph has a 2-cycle, swapping upper-half bundles and reallocating an unallocated good can produce an EFX allocation Pareto dominating X.The construction preserves or improves agents’ valuations while eliminating strong envy involving the modified bundle.
- No 2-cycle in MX: With no 2-cycle, the champion graph is a 3-cycle, and the proof first cyclically shifts upper-half bundles so every agent receives a favorite upper-half bundle.The resulting allocation makes all agents strictly better off before further adjustments to establish EFX.
- Three strong envy edges: A cyclic shift of bundles yields an EFX allocation Pareto dominating X when the envy graph has three strong envy edges.
- No 2-cycle in MX: Replacing a lower-half bundle by the unallocated good can preserve EFX while making the relevant agent strictly better off.The proof uses the ordering of upper- and lower-half bundles to exclude remaining strong envy edges.
- Conclusion: For every partial EFX allocation with three sources in EX, there exists an EFX allocation Y that Pareto dominates it.
4 Existence of EFX: Two sources in EX
When the envy graph has two sources, the proof analyzes the remaining champion-graph configurations and constructs dominating EFX allocations. These case analyses support the paper’s constructive existence theorem for three additive agents.
- Initial configurations: If the third agent champions one of the other agents, existing observations directly give a Pareto dominating EFX allocation.
- Champion-graph cases: When the third agent champions neither other agent, the two-source envy graph reduces to three possible champion-graph configurations.These configurations depend on whether agent 1, agent 2, or both agents champion agent 3.
- Case constructions: The proof modifies allocations by moving agents’ bundles or subsets so that selected agents improve while strong envy edges are eliminated.For example, in one case every agent becomes better off before EFX is verified through the remaining possible envy edges.
- Case constructions: For each remaining case, the constructed allocation dominates the current allocation and is shown to be EFX.The argument includes separate treatments depending on agent a and on the value of the auxiliary bundle Z.
- Conclusion: The resulting lemmas establish that a partial EFX allocation with an unallocated good can be extended through dominating EFX allocations, culminating in existence for three additive agents.
5 Barriers in Current Techniques
The section presents two three-agent examples showing that existing iterative approaches toward complete EFX allocations can fail to preserve Pareto or Nash-welfare progress. These barriers motivate a more flexible search approach while establishing that partial EFX allocations may outperform every complete EFX allocation on relevant efficiency measures.
- Pareto barriers: A seven-good instance has a partial EFX allocation for six goods that no complete EFX allocation Pareto dominates.The allocation gives bundles {g2, g3, g4}, {g1, g5}, and {g6}; adding the remaining good to any bundle creates an EFX violation.
- Pareto barriers: Adding the seventh good to any existing bundle causes strong envy by one of the other agents.The three cases produce envy by a2, a3, or a1, respectively.
- Nash-welfare barriers: A partial EFX allocation for the first six goods has higher Nash welfare than every complete EFX allocation for the seven-good instance.The paper’s theorem explicitly falsifies the conjecture that adding an item preserves an EFX allocation with at least as high Nash welfare.
- Nash-welfare barriers: The proof restricts maximum-Nash-welfare complete EFX allocations by requiring goods g3, g5, and g6 to go to distinct agents.It further constrains which of these goods agents a2 and a3 can receive, enabling a case analysis of complete allocations.
- Nash-welfare barriers: In the analyzed cases, every complete EFX allocation has lower Nash welfare than the partial allocation X.One case directly yields NSW(X′)/NSW(X) < 1, while another shows that both a1 and a2 decrease and a3 does not increase.
6 Conclusion
The paper proves constructively that EFX allocations always exist for three agents with additive valuations, while identifying boundaries for valuation generality and efficiency guarantees.
- EFX allocations always exist for three agents with additive valuations, and the proof yields a pseudo-polynomial algorithm.The authors describe the result as constructive and identify novel techniques used to overcome barriers in existing approaches.
- The proofs crucially rely on additivity and do not extend to submodular or subadditive valuations.The authors propose studying three-agent EFX under more general valuations as a next step.
- The efficiency of complete EFX allocations remains unclear despite efficient approximate EFX allocations and efficient EFX allocations with bounded charity.The open issue is the trade-off between efficiency and guaranteeing fairness for complete allocations.