An EF2X Allocation Protocol for Restricted Additive Valuations
An EF2X Allocation Protocol for Restricted Additive Valuations
Hannaneh Akrami, Rojin Rezvan, Masoud Seddighin
Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
Main Track. Pages 17-23.
https://doi.org/10.24963/ijcai.2022/3
We study the problem of fairly allocating a set of indivisible goods to a set of n agents. Envy-freeness up to any good (EFX) criterion (which
requires that no agent prefers the bundle of another agent after the removal of any single good) is known to be a remarkable analogue of envy-freeness when the resource is a set of indivisible goods.
In this paper, we investigate EFX for restricted additive valuations, that is, every good has a 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 the removal of any k goods. Our main contribution is an algorithm that finds a complete (i.e., no good is discarded) EF2X allocation for 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 n/2 -1 goods.
Keywords:
Agent-based and Multi-agent Systems: Algorithmic Game Theory
AI Ethics, Trust, Fairness: Fairness & Diversity