Almost Envy-free Allocation of Indivisible Goods: A Tale of Two Valuations

The existence of EFX allocations stands as one of the main challenges in discrete fair division. In this paper, we present a collection of symmetrical results on the existence of EFX notion and its approximate variations. These results pertain to two seemingly distinct valuation settings: the restricted additive valuations and $(p,q)$-bounded valuations recently introduced by Christodoulou et al. {christodoulou2023fair}. In a $(p,q)$-bonuded instance, each good holds relevance (i.e., has a non-zero marginal value) for at most p agents, and any pair of agents share at most q common relevant goods. The only known guarantees on $(p,q)$-bounded valuations is that $(2,1)$-bounded instances always admit EFX allocations (EC'22) {christodoulou2023fair}. Here we show that instances with (∞,1)-bounded valuations always admit EF2X allocations, and EFX allocations with at most n/2 - 1 discarded goods. These results mirror the existing results for the restricted additive setting {akrami2023efx}. Moreover, we present (√2/2)-EFX allocation algorithms for both the restricted additive and (∞,1)-bounded settings. The symmetry of these results suggests that these valuations exhibit symmetric structures. Building on this observation, we conjectured that the (2,∞)-bounded and restricted additive setting might admit EFX guarantee. Intriguingly, our investigation confirms this conjecture. We propose a rather complex EFX allocation algorithm for restricted additive valuations when $p=2$ and q=∞.