@online{Akrami2202.13676,
TITLE = {An {EF2X} Allocation Protocol for Restricted Additive Valuations},
AUTHOR = {Akrami, Hannaneh and Rezvan, Rojin and Seddighin, Masoud},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2202.13676},
EPRINT = {2202.13676},
EPRINTTYPE = {arXiv},
YEAR = {2022},
ABSTRACT = {We study the problem of fairly allocating a set of $m$ indivisible goods to a<br>set of $n$ agents. Envy-freeness up to any good (EFX) criteria -- which<br>requires that no agent prefers the bundle of another agent after removal of any<br>single good -- is known to be a remarkable analogous of envy-freeness when the<br>resource is a set of indivisible goods. In this paper, we investigate EFX<br>notion for the restricted additive valuations, that is, every good has some<br>non-negative value, and every agent is interested in only some of the goods.<br> We introduce a natural relaxation of EFX called EFkX which requires that no<br>agent envies another agent after removal of any $k$ goods. Our main<br>contribution is an algorithm that finds a complete (i.e., no good is discarded)<br>EF2X allocation for the restricted additive valuations. In our algorithm we<br>devise new concepts, namely "configuration" and "envy-elimination" that might<br>be of independent interest.<br> We also use our new tools to find an EFX allocation for restricted additive<br>valuations that discards at most $\lfloor n/2 \rfloor -1$ goods. This improves<br>the state of the art for the restricted additive valuations by a factor of $2$.<br>},
}