Autonomous Agents and Multi-Agent Systems Искусственный интеллект
$$\textsf {EFX}$$ allocations and orientations on bipartite multi-graphs: a complete picture
Аннотация
Abstract 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 ( $$\textsf {EFX}$$ ) allocation. This model has recently been introduced by [22] where they show that $$\textsf {EFX}$$ 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 $$\textsf {EFX}$$ allocations on bipartite multi-graphs for monotone valuations and on multi-cycles for $$\textsf {MMS}$$ -feasible valuations. We also present pseudo-polynomial time algorithms to compute $$\textsf {EFX}$$ allocations for the above settings. Furthermore, we show that for bipartite multi-graphs with cancelable valuations, $$\textsf {EFX}$$ allocations can be computed in polynomial time. We thus deepen the understanding of $$\textsf {EFX}$$ allocations by expanding the spectrum of settings in which they are guaranteed to exist for an arbitrary number of agents. Next, we study $$\textsf {EFX}$$ 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 $$\textsf {NP}$$ -complete to determine whether a given fair division instance on a bipartite multi-graph admits an $$\textsf {EFX}$$ orientation, even with a constant number of agents.