Does envy-freeness up to any good (EFX) always exist for indivisible item allocation?
An allocation is EFX if no agent envies another agent after removing any single item from the other agent's bundle. This is a central open problem in fair division.
Known results: - EFX exists for 2 agents (trivial) - EFX exists for 3 agents (Chaudhury et al., 2020) - EFX exists when there are only 2 types of items - EFX exists for identical valuations - EFX exists for restricted additive valuations in various settings
The general case for n ≥ 4 agents with arbitrary monotone valuations remains open.
One idea is to use the Fano plane, where every size-2 subset of [7] appears in exactly one edge. Maybe there can be one player per node or edge, plus an "impostor" or two that acts a lot like one particular player. Maybe the items can be edges of the Fano plane. Because of the symmetry in the Fano plane, the 7 players must have symmetric bundles, but the impostor ruins the envy-freeness property.