# An EF2X Allocation Protocol for Restricted Additive Valuations

arXiv: https://arxiv.org/abs/2202.13676 · HTML: https://mlsanity.com/paper/2202.13676/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Feb 2022.

## Built on by (most cited first, 3 of 3)

- [Temporal Fair Division of Indivisible Items](https://mlsanity.com/paper/2410.14593/) (2024)
- [Pushing the Frontier on Approximate EFX Allocations](https://mlsanity.com/paper/2406.12413/) (2024)
- [Understanding EFX Allocations: Counting and Variants](https://mlsanity.com/paper/2504.03951/) (2025)

## Abstract (arXiv)

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.