A Complete Landscape of EFX Allocations on Graphs: Goods, Chores and Mixed Manna

We study envy-free up to any item (EFX) allocations on simple graphs where vertices and edges represent agents and items respectively. An agent (vertex) is only interested in items (edges) that are incident to her and all other items always have zero marginal value to her. Christodoulou et al. [EC, 2023] first proposed this setting and studied the case of goods where every item has non-negative marginal values to every agent. In this work, we significantly generalize this setting and provide a complete set of results by considering the allocation of arbitrary items that can be goods, chores, or mixed manna under doubly monotone valuations with a mild assumption. For goods, we complement the results by Christodoulou et al. [EC, 2023] by considering another weaker notion of EFX in the literature and showing that an orientation -- a special allocation where each edge must be allocated to one of its endpoint agents -- that satisfies the weaker notion always exists and can be computed in polynomial time, contrary to the stronger notion for which an orientation may not exist and determining its existence is NP-complete. For chores, we show that an envy-free allocation always exists, and an EFX orientation may not exist but its existence can be determined in polynomial time. For mixed manna, we consider the four notions of EFX in the literature. We prove that an allocation that satisfies the strongest notion of EFX may not exist and determining its existence is NP-complete, while one that satisfies any of the other three notions always exists and can be computed in polynomial time. We also prove that an orientation that satisfies any of the four notions may not exist and determining its existence is NP-complete.