EFX allocations always exist for general monotone valuations in bipartite multigraphs, in multigraphs where each agent has at most ceil(n/4)-1 neighbors, and in multigraphs whose shortest non-parallel cycle has length at least 6.
Title resolution pending
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We study the problem of finding fair allocations -- EF1 and EFX -- of indivisible goods with orientations. In an orientation, every agent gets items from their own predetermined set. For EF1, we show that EF1 orientations always exist when agents have monotone valuations, via a pseudopolynomial-time algorithm. This surprisingly positive result is the main contribution of our paper. We complement this result with a comprehensive set of scenarios where our algorithm, or a slight modification of it, finds an EF1 orientation in polynomial time. For EFX, we focus on the recently proposed graph instances, where every agent corresponds to a vertex on a graph and their allowed set of items consists of the edges incident to their vertex. It was shown that finding an EFX orientation is NP-complete in general. We prove that it remains intractable even when the graph has a vertex cover of size 8, or when we have a multigraph with only 10 vertices. We essentially match these strong negative results with a fixed-parameter tractable algorithm that is virtually the best someone could hope for.
citation-role summary
background 1
citation-polarity summary
fields
cs.GT 1years
2025 1verdicts
CONDITIONAL 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
On the existence of EFX allocations in multigraphs
EFX allocations always exist for general monotone valuations in bipartite multigraphs, in multigraphs where each agent has at most ceil(n/4)-1 neighbors, and in multigraphs whose shortest non-parallel cycle has length at least 6.