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=.