allocations and orientations on bipartite multi-graphs: a complete picture

Journal article

We consider the fundamental problem of fairly allocating a set of indivisible items among agents having valuations that are represented by a multi-graph – here, agents appear as vertices and items as edges between them and each vertex (agent) only values the set of its incident edges (items). The goal is to find a fair, i.e., envy-free up to any item () allocation. This model has recently been introduced by [22] where they show that allocations always exist on simple graphs for monotone valuations, i.e., where any two agents can share at most one edge (item). A natural question arises as to what happens when we go beyond simple graphs and study various classes of multi-graphs? We answer the above question affirmatively for the valuation class of bipartite multi-graphs and multi-cycles. The main contribution of this work is to establish the existence of allocations on bipartite multi-graphs for monotone valuations and on multi-cycles for -feasible valuations. We also present pseudo-polynomial time algorithms to compute allocations for the above settings. Furthermore, we show that for bipartite multi-graphs with cancelable valuations, allocations can be computed in polynomial time. We thus deepen the understanding of allocations by expanding the spectrum of settings in which they are guaranteed to exist for an arbitrary number of agents. Next, we study orientations (allocations where every item is assigned to one of its two endpoint agents) and provide a complete characterization of their existence on bipartite multi-graphs in terms of two key parameters—the number of edges shared between any two agents and the diameter of the graph. Finally, we prove that it is -complete to determine whether a given fair division instance on a bipartite multi-graph admits an orientation, even with a constant number of agents.

Authors: Afshinmehr, M; Danaei, A; Kazemi, M; Mehlhorn, K; Rathi, N

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Springer
• Journal: Autonomous Agents and Multi-Agent Systems
• Volume: 40
• Issue: 2
• Article number: 32
• Publication date: 2026-06-02
• Acceptance date: 2026-05-04
• DOI: 10.1007/s10458-026-09754-8
• EISSN: 1573-7454
• ISSN: 1387-2532
• Language: English