EFX Orientations of Multigraphs

We study EFX orientations of multigraphs with self-loops. In this setting, vertices represent agents, edges represent goods, and a good provides positive utility to an agent only if it is incident to the agent. We focus on the bi-valued symmetric case in which each edge has equal utility to both incident agents, and edges have one of two possible utilities α > β ≥ 0. In contrast with the case of simple graphs for which bipartiteness implies the existence of an EFX orientation, we show that deciding whether a symmetric multigraph G of any multiplicity q ≥ 2 has an EFX orientation is NP-complete even if G is bipartite, α > qβ, and G contains a structure called a non-trivial odd multitree (NTOM). Moreover, we show that NTOMs are a problematic structure in the sense that even very simple NTOMs can fail to have EFX orientations, and multigraphs that do not contain NTOMs always have EFX orientations that can be found in polynomial-time.