Help Privacy Policy Disclaimer
  Advanced SearchBrowse





An EF2X Allocation Protocol for Restricted Additive Valuations


Akrami,  Hannaneh
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 356KB

Supplementary Material (public)
There is no public supplementary material available

Akrami, H., Rezvan, R., & Seddighin, M. (2022). An EF2X Allocation Protocol for Restricted Additive Valuations. Retrieved from https://arxiv.org/abs/2202.13676.

Cite as: https://hdl.handle.net/21.11116/0000-000C-1FF3-0
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$.