Approximate Envy-Free Allocations up to any k Goods

We study the problem of finding approximate envy-free allocations up to any $k$ goods ($\alpha$-EFkX), when agents have additive values over goods in a bundle. As our main result, we show that for any $k>2$, $\frac{k+1}{k+2}$-EFkX allocations exist for any number of agents, and can be computed in polynomial time, via an appropriate generalization of the 3PA algorithm of (Amanatidis et al., 2024). An immediate corollary of this result is that $3/4$-EF2X allocations exist for any number of agents; in contrast, $2/3$-EFX allocations are only known to exist for up to 7 agents. We improve this latter result by devising an algorithm that achieves $2/3$-EFX for 8 agents. We also consider EFkX graph orientations; we prove that such orientations do not always exist, and that deciding their existence is NP-complete, thereby generalizing the corresponding result of (Christodoulou et al., 2023) for $k=1$.