One Item of Slack: Separating EF1 from EFX under Noisy Observations

Envy-freeness up to one item (EF1) asks that an agent's envy of another bundle vanish once *some* single item is dropped from it; EFX asks this for *every* item. We study what that quantifier costs when valuations are learned from noisy observations rather than given. Our setting repairs envy in a fixed allocation from a pool of spare goods, with standard fair division the case in which nothing is allocated in advance and every good must be handed out. In it we exhibit two agents with coverage valuations, a standard submodular class, over $m$ pool goods and two fixed items, on which one fixed extension, consulting nothing at all, is $\epsilon$-EF1, while $\epsilon$-EFX and $\epsilon$-EF need $\Omega (m^2)$ observations for every $\epsilon \le 1/128$. For $\epsilon$-EFX the exponent is tight: $O(m^2)$ observations suffice on the same family. Every instance admits an exactly envy-free extension, so the cost is not infeasibility in disguise. Neither ingredient forces the quadratic cost alone. Letting the algorithm split the two fixed items makes $\epsilon$-EFX free on these valuations, and with no fixed allocation two agents reach $\epsilon$-EFX from $\tilde{O}(m/{\epsilon }^3)$ observations under arbitrary monotone valuations, where $\tilde{O}$ hides logarithmic factors; exact EFX there still takes exponentially many queries. A transfer principle turns any deterministic oracle algorithm tolerating small errors into a learning algorithm, giving $\tilde{O}(nm/{\epsilon }^2)$ there for $\epsilon$-EF1 with $n$ agents. One item of slack lets an allocation stop tracking valuations at the scale of single items. A fixed pair that cannot be reallocated separately puts that scale back.