@online{VH2410.13580,
TITLE = {{EFX} Exists for Three Types of Agents},
AUTHOR = {H V, Vishwa Prakash and Ghosal, Pratik and Nimbhorkar, Prajakta and Varma, Nithin},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2410.13580},
EPRINT = {2410.13580},
EPRINTTYPE = {arXiv},
YEAR = {2024},
MARGINALMARK = {$\bullet$},
ABSTRACT = {In this paper, we study the problem of finding an envy-free allocation of<br>indivisible goods among multiple agents. EFX, which stands for envy-freeness up<br>to any good, is a well-studied relaxation of the envy-free allocation problem<br>and has been shown to exist for specific scenarios. For instance, EFX is known<br>to exist when there are only three agents [Chaudhury et al, EC 2020], and for<br>any number of agents when there are only two types of valuations [Mahara,<br>Discret. Appl. Math 2023].<br> We show that EFX allocations exist for any number of agents when there are at<br>most three types of additive valuations.<br>},
}