# Pushing the Frontier on Approximate EFX Allocations

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 40 references that are in the map.
- First posted on arXiv 18 Jun 2024.

## Builds on (most cited first, 15 of 15)

- [Almost Envy-Freeness with General Valuations](https://mlsanity.com/paper/1707.04769/) (2017)
- [Fair Division of Indivisible Goods: Recent Progress and Open Questions](https://mlsanity.com/paper/2208.08782/) (2022)
- [EFX Exists for Three Agents](https://mlsanity.com/paper/2002.05119/) (2020)
- [Maximum Nash Welfare and Other Stories About EFX](https://mlsanity.com/paper/2001.09838/) (2020)
- [Fair and Truthful Mechanisms for Dichotomous Valuations](https://mlsanity.com/paper/2002.10704/) (2020)
- [A Little Charity Guarantees Almost Envy-Freeness](https://mlsanity.com/paper/1907.04596/) (2019)
- [Envy-freeness up to any item with high Nash welfare: The virtue of donating items](https://mlsanity.com/paper/1902.04319/) (2019)
- [Multiple Birds with One Stone: Beating 1/2 for EFX and GMMS via Envy Cycle Elimination](https://mlsanity.com/paper/1909.07650/) (2019)
- [Improving EFX Guarantees through Rainbow Cycle Number](https://mlsanity.com/paper/2103.01628/) (2021)
- [Approximately EFX Allocations for Indivisible Chores](https://mlsanity.com/paper/2109.07313/) (2021)
- [An EF2X Allocation Protocol for Restricted Additive Valuations](https://mlsanity.com/paper/2202.13676/) (2022)
- [Improved EFX Approximation Guarantees under Ordinal-based Assumptions](https://mlsanity.com/paper/2308.04860/) (2023)
- [On The Pursuit of EFX for Chores: Non-Existence and Approximations](https://mlsanity.com/paper/2406.10752/) (2024)
- [Almost Envy-freeness, Envy-rank, and Nash Social Welfare Matchings](https://mlsanity.com/paper/2007.07027/) (2020)
- [Maximin-Aware Allocations of Indivisible Goods](https://mlsanity.com/paper/1905.09969/) (2019)

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

- [Online Fair Division for Personalized 2-Value Instances](https://mlsanity.com/paper/2505.22174/) (2025)
- [On the existence of EFX allocations in multigraphs](https://mlsanity.com/paper/2502.09777/) (2025)
- [Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division](https://mlsanity.com/paper/2507.14957/) (2025)
- [EFX Allocation In (Multi)Hypergraphs](https://mlsanity.com/paper/2608.03171/) (2026)

## Abstract (arXiv)

We study the problem of allocating a set of indivisible goods to a set of agents with additive valuation functions, aiming to achieve approximate envy-freeness up to any good (α-EFX). The state-of-the-art results on the problem include that (exact) EFX allocations exist when (a) there are at most three agents, or (b) the agents' valuation functions can take at most two values, or (c) the agents' valuation functions can be represented via a graph. For α-EFX, it is known that a 0.618-EFX allocation exists for any number of agents with additive valuation functions. In this paper, we show that 2/3-EFX allocations exist when (a) there are at most seven agents, (b) the agents' valuation functions can take at most three values, or (c) the agents' valuation functions can be represented via a multigraph. Our results can be interpreted in two ways. First, by relaxing the notion of EFX to 2/3-EFX, we obtain existence results for strict generalizations of the settings for which exact EFX allocations are known to exist. Secondly, by imposing restrictions on the setting, we manage to beat the barrier of 0.618 and achieve an approximation guarantee of 2/3. Therefore, our results push the frontier of existence and computation of approximate EFX allocations, and provide insights into the challenges of settling the existence of exact EFX allocations.