EFX Allocations Exist on Triangle-Free Multi-Graphs
Preprint
Abstract
We study the fair allocation of indivisible goods among agents, with a focus on limiting envy. A central open question in this area is the existence of EFX allocations-allocations in which any envy of any agent i towards any agent j vanishes upon the removal of any single good from j's bundle. Establishing the existence of such allocations has proven notoriously difficult in general, but progress has been made for restricted valuation classes. Christodoulou et al. [2023] proved existence for graphical valuations, where goods correspond to edges in a graph, agents to nodes, and each agent values only incident edges. The graph was required to be simple, i.e., for any pair of agents, there could be at most one good that both agents value. The problem remained open, however, for multi-graph valuations, where for a pair of agents several goods may have value to both. In this setting, Sgouritsa and Sotiriou [2025] established existence whenever the shortest cycle with non-parallel edges has length at least six, while Afshinmehr et al. [2025] proved existence when the graph contains no odd cycles. In this paper, we strengthen these results by proving that EFX allocations always exist in multi-graphs that contain no cycle of length three. Assuming monotone valuations, we further provide a pseudo-polynomial time algorithm for computing such an allocation, which runs in polynomial time when agents have cancelable valuations, a strict superclass of additive valuation functions. Accordingly, our results stand as one of the only cases where EFX allocations exist for an arbitrary number of agents.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Existence of Fair and Efficient Allocation of Indivisible Chores2026
- Almost Envy-Free Allocation of Indivisible Goods: A Tale of Two Valuations2026
- Constant-Factor EFX Exists for Chores2025
- Extension of Additive Valuations to General Valuations on the Existence of EFXMathematics of Operations Research, 2024
- Approximately EFX allocations for indivisible choresArtificial Intelligence, 2023
- Fair division of indivisible goods: Recent progress and open questionsArtificial Intelligence, 2023
- The Unreasonable Fairness of Maximum Nash WelfareACM Transactions on Economics and Computation, 2019
- The Multi-unit Assignment Problem: Theory and Evidence from Course Allocation at HarvardAmerican Economic Review, 2012
- The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal IncomesJournal of Political Economy, 2011
- Spectrum sharing for unlicensed bandsIEEE Journal on Selected Areas in Communications, 2007