On the existence of EFX under picky or non-differentiative agents

In this paper, we consider the fair division of indivisible goods under arguably the strongest envy-based fairness notion of envy-free up to any item (EFX). Extending the long line of work on special cases of additive valuations, we show existence of EFX for the following two cases: (𝑖) instances where agents are very picky, i.e., each agent likes at most four items positively. (𝑖𝑖) ternary instances where the value of an agent for an item is 0, 𝑎, or 𝑏 for 0 < 𝑎 < 𝑏 ≤ 2𝑎. In both cases, the existence is shown by designing an efficient algorithm to find an EFX allocation.