EUVIMEDEUVIMED entdecken
Crossref

EFX Allocation in (Multi)Hypergraphs

Thanasis Lianeas, Alkmini Sgouritsa, Minas Marios Sotiriou

Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (20) · 17102-17110

DOI: 10.1609/aaai.v40i20.38759 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Thanasis Lianeas und 2 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study fair allocations of indivisible goods among agents with heterogeneous monotone valuations. As fair we consider the allocations that are envy-free-up-to-any-good (EFX). Finding if EFX allocations always exist, even for agents with additive valuations, is a major open problem in Fair Division. Christodoulou et al. (2023) introduced the (multi-hyper)graph setting, where agents and goods are represented by vertices and edges of a graph, respectively, and only the endpoints of an edge may have non-zero marginal value for it. We show that for hypergraphs with girth at least 4 and agents with general monotone valuations there always exists an EFX allocation and can be constructed in polynomial time. We generalize our approach to also show that multi-hypergraphs with girth (on the simple hypergraph) at least 4 always admit an EFX allocation, as long as there exists a single vertex whose adjacent edges have multiplicity at most the size of that edge minus 2; our construction in this case needs pseudo-polynomial time.

Zitieren

APA

Lianeas, T., Sgouritsa, A., & Sotiriou, M. M. (2026). EFX Allocation in (Multi)Hypergraphs. Proceedings of the AAAI Conference on Artificial Intelligence, 40(20), 17102-17110. https://doi.org/10.1609/aaai.v40i20.38759

Vancouver

Lianeas T, Sgouritsa A, Sotiriou MM. EFX Allocation in (Multi)Hypergraphs. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(20):17102-17110. doi:10.1609/aaai.v40i20.38759

BibTeX
@article{Lianeas2026,
  author = {Lianeas, Thanasis and Sgouritsa, Alkmini and Sotiriou, Minas Marios},
  title = {EFX Allocation in (Multi)Hypergraphs},
  journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
  year = {2026},
  volume = {40},
  number = {20},
  pages = {17102--17110},
  doi = {10.1609/aaai.v40i20.38759}
}
Kostenlos starten →