EFX Allocation in (Multi)Hypergraphs
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.
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}
}
EUVIMED