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

Abstract

The existence of $\text{EFX}$ allocations stands as one of the main challenges in discrete fair division.In this paper, we present symmetrical results on the existence of $\text{EFX}$ and its approximate variations for two distinct valuations: restricted additive valuations and $(p,q)$-bounded valuations introduced by Christodoulou \etal \cite{christodoulou2023fair}. 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 $(\infty ,1)$-bounded valuations admit $\text{EF2X}$ allocations and $\text{EFX}$ allocations with at most $\lfloor n/2\rfloor -1$ discarded goods, mirroring results for the restricted additive setting \cite{akrami2022ef2x}. We also present $(\sqrt{2}/2)\text{-EFX}$ algorithms for both restricted additive and $(\infty ,1)$-bounded subadditive settings. The symmetry of these results suggests these valuations share symmetric structures. Building on this, we propose an $\text{EFX}$ allocation for restricted additive valuations when $p=2$ and $q=\infty$. To achieve these results, we further develop the rank concept introduced by Farhadi \etal \cite{farhadi2021almost} and introduce several new concepts such as virtual value, rankpath, and root, which advance the overall understanding of $\text{EFX}$ 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 $\text{EFX}$.