|
We study the problem of fairly allocating a set $S$ of $m$ indivisible items among a set $N$ of $n$ agents with individual preferences. The notion of fairness considered here is envy-freeness up to any item (EFX), a well-studied relaxation of envy-freeness. In spite of the considerable efforts over the past years, the existence of EFX solutions is wide open. In particular, the problem of finding EFX solutions has been resolved only in very restricted cases of negative additive valuations.
In this paper, we show that there always exists an EFX solution for at most seven items and four agents, each having one of two possible negative additive valuations. Our proof is algorithmic and so provides an efficient procedure that determines an EFX allocation.
Bibtex entry:
| AUTHOR | = | {B{\'e}rczi, Krist{\'o}f and Gedefa Tolessa, Fekadu}, |
| TITLE | = | {A note on the existence of EFX allocations for negative additive valuations}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2022}, |
| NUMBER | = | {QP-2022-01} |