EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

$$\textsf {EFX}$$ allocations and orientations on bipartite multi-graphs: a complete picture

Mahyar Afshinmehr, Alireza Danaei, Mehrafarin Kazemi, Kurt Mehlhorn, Nidhi Rathi

Autonomous Agents and Multi-Agent Systems · 2026-12 · 40 (2)

DOI: 10.1007/s10458-026-09754-8 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Autonomous Agents and Multi-Agent Systems, online erschienen am 02.06.2026. Verfasst von Mahyar Afshinmehr und 4 weiteren Autor:innen. Die Arbeit nennt 48 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Afshinmehr, M., Danaei, A., Kazemi, M., Mehlhorn, K., & Rathi, N. (2026). $$\textsf {EFX}$$ allocations and orientations on bipartite multi-graphs: a complete picture. Autonomous Agents and Multi-Agent Systems, 40(2). https://doi.org/10.1007/s10458-026-09754-8

Vancouver

Afshinmehr M, Danaei A, Kazemi M, Mehlhorn K, Rathi N. $$\textsf {EFX}$$ allocations and orientations on bipartite multi-graphs: a complete picture. Autonomous Agents and Multi-Agent Systems. 2026;40(2). doi:10.1007/s10458-026-09754-8

BibTeX
@article{Afshinmehr2026,
  author = {Afshinmehr, Mahyar and Danaei, Alireza and Kazemi, Mehrafarin and Mehlhorn, Kurt and Rathi, Nidhi},
  title = {$$\textsf EFX$$ allocations and orientations on bipartite multi-graphs: a complete picture},
  journal = {Autonomous Agents and Multi-Agent Systems},
  year = {2026},
  volume = {40},
  number = {2},
  doi = {10.1007/s10458-026-09754-8}
}
Kostenlos starten →