EFX Orientations of Multigraphs

We study the fair division of multigraphs with self-loops. In this setting, vertices represent agents and edges represent goods, and a good provides positive utility to an agent only if it is incident with the agent. Whereas previous research has so far only considered simple graphs, we consider the general setting of multigraphs, specifically focusing on the case in which each edge has equal utility to both incident agents, and edges have one of two possible utilities $\alpha > \beta \geq 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 multiplicity $q \geq 2$ admits an EFX orientation is NP-complete even if $G$ is bipartite, $\alpha > q\beta$, and $G$ contains a structure called a non-trivial odd multitree. Moreover, we show that non-trivial odd multitrees are a forbidden structure in the sense that even very simple non-trivial odd multitrees can fail to admit EFX orientations, and multigraphs that do not contain non-trivial odd multitrees always admit EFX orientations.
Comment: 14 pages