In this talk, we will explore envy-freeness up to any good (EFX) in settings where valuations are represented by a graph of arbitrary size, with vertices corresponding to agents and edges corresponding to items. An item (edge) has zero marginal value to all agents (vertices) not incident to the edge. Each vertex may have an arbitrary monotone valuation on the set of incident edges. We will first examine allocations that correspond to edge orientations, noting that EFX may not always be achievable. Furthermore, determining whether an EFX orientation exists is NP-complete. The main result is that EFX allocations exist for this setting. This is one of the few cases where EFX allocations are known to exist for more than 3 agents.
Reference: https://dl.acm.org/doi/pdf/10.1145/3580507.3597764
