TY - GEN
T1 - On the Structure of EFX Orientations on Graphs AAAI Track
AU - Zeng, Jinghan A.
AU - Mehta, Ruta
N1 - This project was supported by NSF grant CCF-2334461. Zeng would like to thank Elfarouk Harb and Daniel Schoepflin for a careful reading of this manuscript, and Pooja Kulkarni for thoughtful discussions.
PY - 2025
Y1 - 2025
N2 - Discrete Fair division is the problem of allocating a set of indivisible items among agents in a fair manner. Envy-freeness up to any good (EFX) has emerged as one of the strongest fairness guarantees for this problem, however, its existence remains unknown. Christodoulou, Fiat, Koutsoupias, and Sgouritsa (EC 2023) introduced graphical valuations represented by a graph, where nodes represent agents and edges are items valued only by its endpoints, and under these showed that EFX allocation exist. They showed that such an allocation need not be efficient-in the sense that every edge is assigned (oriented) to one of its endpoints-and proved that determining whether an EFX orientation exists is NP-hard. They left the characterization of graphs admitting EFX orientation as an important open question. Towards this question, we introduce the notion of strongly EFX-orientable graphs, defined as graphs that have an EFX orientation for any valuation assignment. We establish a surprising connection between this property and the chromatic number of the graph. Specifically: • Graphs with chromatic number χ(G) ≤ 2 are strongly EFX-orientable. • Graphs with χ(G) ≥ 4 are not strongly EFX-orientable. • For graphs with χ(G) = 3, we identify both strongly EFX-orientable and non-strongly EFX-orientable examples, demonstrating the sharpness of our characterization. For binary valuations, we provide a complete characterization.
AB - Discrete Fair division is the problem of allocating a set of indivisible items among agents in a fair manner. Envy-freeness up to any good (EFX) has emerged as one of the strongest fairness guarantees for this problem, however, its existence remains unknown. Christodoulou, Fiat, Koutsoupias, and Sgouritsa (EC 2023) introduced graphical valuations represented by a graph, where nodes represent agents and edges are items valued only by its endpoints, and under these showed that EFX allocation exist. They showed that such an allocation need not be efficient-in the sense that every edge is assigned (oriented) to one of its endpoints-and proved that determining whether an EFX orientation exists is NP-hard. They left the characterization of graphs admitting EFX orientation as an important open question. Towards this question, we introduce the notion of strongly EFX-orientable graphs, defined as graphs that have an EFX orientation for any valuation assignment. We establish a surprising connection between this property and the chromatic number of the graph. Specifically: • Graphs with chromatic number χ(G) ≤ 2 are strongly EFX-orientable. • Graphs with χ(G) ≥ 4 are not strongly EFX-orientable. • For graphs with χ(G) = 3, we identify both strongly EFX-orientable and non-strongly EFX-orientable examples, demonstrating the sharpness of our characterization. For binary valuations, we provide a complete characterization.
KW - Chromatic Number
KW - EFX
KW - Fair Division
KW - Graph Orientations
UR - https://www.scopus.com/pages/publications/105009800212
UR - https://www.scopus.com/pages/publications/105009800212#tab=citedBy
M3 - Conference contribution
AN - SCOPUS:105009800212
T3 - Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
SP - 2309
EP - 2316
BT - Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2025
A2 - Vorobeychik, Yevgeniy
A2 - Das, Sanmay
A2 - Nowe, Ann
PB - International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
T2 - 24th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2025
Y2 - 19 May 2025 through 23 May 2025
ER -