# On the existence of EFX allocations in multigraphs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 39 references that are in the map.
- First posted on arXiv 13 Feb 2025.

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

- [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)
- [A Discrete and Bounded Envy-free Cake Cutting Protocol for Four Agents](https://mlsanity.com/paper/1508.05143/) (2015)
- [Fair and Efficient Allocations under Lexicographic Preferences](https://mlsanity.com/paper/2012.07680/) (2020)
- [Pushing the Frontier on Approximate EFX Allocations](https://mlsanity.com/paper/2406.12413/) (2024)
- [Extension of Additive Valuations to General Valuations on the Existence of EFX](https://mlsanity.com/paper/2107.09901/) (2021)
- [Rainbow Cycle Number and EFX Allocations: (Almost) Closing the Gap](https://mlsanity.com/paper/2212.09482/) (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-free Allocation of Indivisible Goods: A Tale of Two Valuations](https://mlsanity.com/paper/2407.05139/) (2024)
- [A Complete Landscape of EFX Allocations on Graphs: Goods, Chores and Mixed Manna](https://mlsanity.com/paper/2409.03594/) (2024)
- [EFX Orientations of Multigraphs](https://mlsanity.com/paper/2410.12039/) (2024)
- [EFX Allocations on Some Multi-graph Classes](https://mlsanity.com/paper/2412.06513/) (2024)
- [The Frontier of Intractability for EFX with Two Agents](https://mlsanity.com/paper/2301.10354/) (2023)

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

- [EFX Allocation In (Multi)Hypergraphs](https://mlsanity.com/paper/2608.03171/) (2026)

## Abstract (arXiv)

We study the problem of "fairly" dividing indivisible goods to several agents that have valuation set functions over the sets of goods. As fair we consider the allocations that are envy-free up to any good (EFX), i.e., no agent envies any proper subset of the goods given to any other agent. The existence or not of EFX allocations is a major open problem in Fair Division, and there are only positive results for special cases. [George Christodoulou, Amos Fiat, Elias Koutsoupias, Alkmini Sgouritsa 2023] introduced a restriction on the agents' valuations according to a graph structure: the vertices correspond to agents and the edges to goods, and each vertex/agent has zero marginal value (or in other words, they are indifferent) for the edges/goods that are not adjacent to them. The existence of EFX allocations has been shown for simple graphs with general monotone valuations [George Christodoulou, Amos Fiat, Elias Koutsoupias, Alkmini Sgouritsa 2023], and for multigraphs for restricted additive valuations [Alireza Kaviani, Masoud Seddighin, Amir Mohammad Shahrezaei 2024]. In this work, we push the state-of-the-art further, and show that the EFX allocations always exists in multigraphs and general monotone valuations if any of the following three conditions hold: either (a) the multigraph is bipartite, or (b) each agent has at most lceil fracn4 rceil -1 neighbors, where n is the total number of agents, or (c) the shortest cycle with non-parallel edges has length at least 6.