# Item

ITEM ACTIONSEXPORT

Released

Paper

#### An EF2X Allocation Protocol for Restricted Additive Valuations

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:2202.13676.pdf

(Preprint), 356KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

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

##### Abstract

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$.

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$.