Non-Monotonicity in Fair Division of Graphs
Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (20) · 17059-17066
DOI: 10.1609/aaai.v40i20.38754 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Hadi Hosseini und 2 weiteren Autor:innen.
Abstract (Originalsprache)
We consider the problem of fairly allocating the vertices of a graph among n agents, where the value of a bundle is determined by its cut value---the number of edges with exactly one endpoint in the bundle. This model naturally captures applications such as team formation and network partitioning, where valuations are inherently non-monotonic: the marginal values may be positive, negative, or zero depending on the composition of the bundle. We focus on the fairness notion of envy-freeness up to one item (EF1) and explore its compatibility with several efficiency concepts such as Transfer Stability (TS) that prohibits any transfer of item that benefit one agent at another's expense. For general graphs, our results uncover a non-monotonic relationship between the number of agents n and the existence of allocations satisfying EF1 and transfer stability (TS): such allocations always exist for n=2, may fail to exist for n=3, but exist again for all n>= 4. We further show that existence can be guaranteed for any n by slightly weakening the efficiency requirement or by restricting the graph to forests. All of our positive results are achieved via efficient algorithms.
Zitieren
APA
Hosseini, H., Pathak, S., & Zhou, Y. (2026). Non-Monotonicity in Fair Division of Graphs. Proceedings of the AAAI Conference on Artificial Intelligence, 40(20), 17059-17066. https://doi.org/10.1609/aaai.v40i20.38754
Vancouver
Hosseini H, Pathak S, Zhou Y. Non-Monotonicity in Fair Division of Graphs. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(20):17059-17066. doi:10.1609/aaai.v40i20.38754
BibTeX
@article{Hosseini2026,
author = {Hosseini, Hadi and Pathak, Shraddha and Zhou, Yu},
title = {Non-Monotonicity in Fair Division of Graphs},
journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
year = {2026},
volume = {40},
number = {20},
pages = {17059--17066},
doi = {10.1609/aaai.v40i20.38754}
}
EUVIMED