An EF2X Allocation Protocol for Restricted Additive Valuations

We study the problem of fairly allocating a set of m indivisible goods to a set of n agents. Envy-freeness up to any good (EFX) criteria -- which requires that no agent prefers the bundle of another agent after removal of any single good -- is known to be a remarkable analogous of envy-freeness when the resource is a set of indivisible goods. In this paper, we investigate EFX notion for the restricted additive valuations, that is, every good has some non-negative value, and every agent is interested in only some of the goods. We introduce a natural relaxation of EFX called EFkX which requires that no agent envies another agent after removal of any k goods. Our main contribution is an algorithm that finds a complete (i.e., no good is discarded) EF2X allocation for the restricted additive valuations. In our algorithm we devise new concepts, namely "configuration" and "envy-elimination" that might be of independent interest. We also use our new tools to find an EFX allocation for restricted additive valuations that discards at most lfloor n/2 rfloor -1 goods. This improves the state of the art for the restricted additive valuations by a factor of 2.