On the Structure of EFX Orientations on Graphs

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 EFXorientable 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 𝜒 (𝐺) ≤ 2 are strongly EFXorientable. • Graphs with 𝜒 (𝐺) ≥ 4 are not strongly EFX-orientable. • For graphs with 𝜒 (𝐺) = 3, we identify both strongly EFXorientable and non-strongly EFX-orientable examples, demonstrating the sharpness of our characterization. For binary valuations, we provide a complete characterization.