On the Existence of EFX Allocations in Multigraphs

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. Christodoulou et al. [19] 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 [19], and for multigraphs for restricted additive valuations [28]. 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 two conditions hold: either (a) each agent has at most ⌈ 𝑛 4 ⌉-1 neighbors, where 𝑛 is the total number of agents, or (b) the shortest cycle with non-parallel edges has length at least 6.