Afshinmehr et al. Prove EFX Allocations Exist for Multi-Graphs

The paper tackles a central open question in algorithmic fair division: the existence of EFX allocations for indivisible goods when agents value goods according to a multigraph. In graphical valuation settings, agents are nodes and goods are edges; each edge is valued only by its two endpoint agents. Prior work by Christodoulou et al. (2023) proved EFX exists for simple graphs (at most one good per pair), but multigraphs—where multiple goods can connect the same agent pair—resisted a full existence proof. Partial approximations (2/3 and √2/2 EFX) were known, but the true existence remained elusive.

The new proof, submitted to arXiv on June 17, 2026, shows that EFX allocations always exist for multigraph instances under cancelable valuations, which include additive valuations as a special case. The authors provide an algorithmic construction that computes such an allocation in polynomial time. This result joins a very small set of EFX existence theorems that apply to an arbitrary number of agents, marking a significant theoretical leap. The algorithmic nature also suggests practical potential for resource allocation in networks with repeated interactions—e.g., cloud computing, spectrum sharing, or multi-agent task assignment.