AAMAS Conference 2026 Conference Paper
EFX Allocations Exist on Triangle-Free Multi-Graphs
- Mahyar Afshinmehr
- Arash Ashuri
- Pouria Mahmoudkhan
- Kurt Mehlhorn
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 š¯‘– towards any agent š¯‘— vanishes upon the removal of any single good from š¯‘—ā€™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. [31] 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 [52] established existence whenever the shortest cycle with non-parallel edges has length at least six, while Afshinmehr et al. [3] 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.