# EFX Allocation In (Multi)Hypergraphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 39 references that are in the map.
- First posted on arXiv 4 Aug 2026.

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

- [Almost Envy-Freeness with General Valuations](https://mlsanity.com/paper/1707.04769/) (2017)
- [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)
- [Improving EFX Guarantees through Rainbow Cycle Number](https://mlsanity.com/paper/2103.01628/) (2021)
- [A Discrete and Bounded Envy-free Cake Cutting Protocol for Four Agents](https://mlsanity.com/paper/1508.05143/) (2015)
- [Pushing the Frontier on Approximate EFX Allocations](https://mlsanity.com/paper/2406.12413/) (2024)
- [Rainbow Cycle Number and EFX Allocations: (Almost) Closing the Gap](https://mlsanity.com/paper/2212.09482/) (2022)
- [EFX Exists for Three Types of Agents](https://mlsanity.com/paper/2410.13580/) (2024)
- [Almost Envy-free Allocation of Indivisible Goods: A Tale of Two Valuations](https://mlsanity.com/paper/2407.05139/) (2024)
- [Exact and approximate maximin share allocations in multi-graphs](https://mlsanity.com/paper/2506.20317/) (2025)
- [On the structure of EFX orientations on graphs](https://mlsanity.com/paper/2404.13527/) (2024)
- [On the existence of EFX allocations in multigraphs](https://mlsanity.com/paper/2502.09777/) (2025)
- [Improved Approximate EFX Guarantees for Multigraphs](https://mlsanity.com/paper/2506.09288/) (2025)
- [From multi-allocations to allocations, with subadditive valuations](https://mlsanity.com/paper/2506.21493/) (2025)
- [EFX Allocations Exist on Triangle-Free Multi-Graphs](https://mlsanity.com/paper/2512.21644/) (2025)
- [EF(X) Orientations: A Parameterized Complexity Perspective](https://mlsanity.com/paper/2512.25033/) (2025)
- [EFX Allocations Exist on Multi-Graphs](https://mlsanity.com/paper/2606.18665/) (2026)

## Abstract (arXiv)

We study fair allocations of indivisible goods among agents with heterogeneous monotone valuations. As fair we consider the allocations that are envy-free-up-to-any-good (EFX). Finding if EFX alloca- tions always exist, even for agents with additive valuations, is a major open problem in Fair Division. Christodoulou et al. (2023) introduced the (multi-hyper)graph setting, where agents and goods are represented by vertices and edges of a graph, respectively, and only the endpoints of an edge may have non-zero marginal value for it. We show that for hypergraphs with girth at least 4 and agents with general monotone valuations there always exists an EFX allocation and can be constructed in polynomial time. We generalize our approach to also show that multi-hypergraphs with girth (on the simple hypergraph) at least 4 always admit an EFX allocation, as long as there exists a single vertex whose incident edges have multiplicity at most the size of that edge minus 2; our construction in this case needs pseudo-polynomial time.