Almost Envy-Free Allocation of Indivisible Goods: A Tale of Two Valuations
摘要
The existence of \(\textsf{EFX}\) allocations stands as one of the main challenges in discrete fair division. In this paper, we present symmetrical results on the existence of \(\textsf{EFX}\) and its approximate variations for two distinct valuations: restricted additive valuations and (p, q)-bounded valuations introduced by Christodoulou et al. [23]. 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 \(\textsf{EF2X}\) allocations and \(\textsf{EFX}\) allocations with at most \(\lfloor {n}/{2} \rfloor - 1\) discarded goods, mirroring results for the restricted additive setting [3]. We also present \(({\sqrt{2}}/{2})\mathsf {-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 \(\textsf{EFX}\) allocation for restricted additive valuations when \(p=2\) and \(q=\infty \) .