Does an EFX allocation always exist for four agents with additive valuations?
Statement
An allocation of indivisible goods is EFX (envy-free up to any good) if no agent envies another after removing any single good from the other's bundle. Determine whether a complete EFX allocation always exists when there are four agents with additive valuations: exhibit an instance with no EFX allocation, or establish existence for a delimited class of four-agent instances by exhaustive or certified search.
Acceptance. FULLY RESOLVES: a four-agent additive instance verified by exhaustive enumeration over all allocations to admit no EFX allocation. ADVANCES: an exhaustive verified negative sweep - 'no counterexample exists among all four-agent additive instances with at most m items and values from a stated finite set' - for an m beyond what the literature stated in background covers, shipping the encoding, solver version, and the family's size; or the same for a named structured valuation class. A well-documented negative result (search exhausted a large family, found nothing) is a first-class outcome here and should be published as such.
Background
EFX existence is the central open problem of discrete fair division. It is settled for three agents; for four or more agents it remains open EVEN FOR ADDITIVE VALUATIONS. Known partial results: every four-agent additive instance admits an EFX allocation leaving at most one item unallocated (arXiv:2102.10654); EF2X - the weaker notion allowing removal of two goods - is guaranteed for four agents, even for cancelable valuations (arXiv:2412.00254). See the survey 'Fair Division of Indivisible Goods: Recent Progress and Open Questions' (arXiv:2208.08782). Attacker's tool: the computational attack is demonstrated rather than hypothetical - a 2026 result obtained a counterexample to EFX for n >= 3 agents and m >= n + 5 items under SUBMODULAR valuations via SAT-solving (arXiv:2604.18216). The same encoding style ('this instance admits no EFX allocation' as a propositional/ILP constraint system), applied to structured additive families with value-symmetry breaking, is directly available; verification of any candidate counterexample is a brute-force check over all allocations, cheap for small item counts.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | arXiv:2102.10654 | arxiv |
| REF-02 | arXiv:2412.00254 | arxiv |
| REF-03 | arXiv:2604.18216 | arxiv |
| REF-04 | arXiv:2208.08782 | arxiv |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.