An EF2X Allocation Protocol for Restricted Additive Valuations
Hannaneh Akrami, Rojin Rezvan, Masoud Seddighin
Abstract
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.
BibTeX
@inproceedings{ijcai2022p3,
title = {An EF2X Allocation Protocol for Restricted Additive Valuations},
author = {Akrami, Hannaneh and Rezvan, Rojin and Seddighin, Masoud},
booktitle = {Proceedings of the Thirty-First International Joint Conference on
Artificial Intelligence, {IJCAI-22}},
publisher = {International Joint Conferences on Artificial Intelligence Organization},
editor = {Lud De Raedt},
pages = {17--23},
year = {2022},
month = {7},
note = {Main Track},
doi = {10.24963/ijcai.2022/3},
url = {https://doi.org/10.24963/ijcai.2022/3},
}