2022/02/28 by Hannaneh Akrami, Akrami, Hannaneh, Rojin Rezvan +3 · 3 citations
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Voting Systems #Logic, Reasoning, and Knowledge
paper · pdf · doi:10.48550/arxiv.2202.13676
openalex publication_date 2022/02/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.