# EFX Orientations of Multigraphs

arXiv: https://arxiv.org/abs/2410.12039 · HTML: https://mlsanity.com/paper/2410.12039/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Oct 2024.

## Built on by (most cited first, 2 of 2)

- [On the existence of EFX allocations in multigraphs](https://mlsanity.com/paper/2502.09777/) (2025)
- [Polynomial-Time Algorithms for Fair Orientations of Chores](https://mlsanity.com/paper/2501.13481/) (2025)

## Abstract (arXiv)

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.