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

The existence of textsfEFX allocations stands as one of the main challenges in discrete fair division.In this paper, we present symmetrical results on the existence of textsfEFX and its approximate variations for two distinct valuations: restricted additive valuations and (p,q)-bounded valuations introduced by Christodoulou etal citechristodoulou2023fair. In a (p,q)-bounded instance, each good has relevance for at most p agents, and any pair of agents shares at most q common relevant goods. We show that instances with (∞,1)-bounded valuations admit textsfEF2X allocations and textsfEFX allocations with at most lfloor n/2 rfloor - 1 discarded goods, mirroring results for the restricted additive setting citeakrami2022ef2x. We also present (√2/2)textsf-EFX algorithms for both restricted additive and (∞,1)-bounded subadditive settings. The symmetry of these results suggests these valuations share symmetric structures. Building on this, we propose an textsfEFX allocation for restricted additive valuations when p=2 and q=∞. To achieve these results, we further develop the rank concept introduced by Farhadi etal citefarhadi2021almost and introduce several new concepts such as virtual value, rankpath, and root, which advance the overall understanding of textsfEFX allocations. In addition, we suggest an updating rule based on the virtual values which we believe will lead to broader and more generalized results on textsfEFX.