On Fairness with Graphical Valuations

The existence of envy-free up to any item (EFX) allocations is widely regarded as a central open problem in discrete fair division, and remains open beyond three agents. A recent line of work has carved out a structurally rich and surprisingly tractable corner of the landscape: the class of graphical valuations, introduced by Christodoulou, Fiat, Koutsoupias, and Sgouritsa (EC 2023), in which agents are vertices of a graph, items are edges, and each item is valued only by its two endpoint-agents. Their remarkable observation that EFX always exists on such instances has catalyzed a fast-moving body of follow-up work. This talk will survey this trajectory, leading to various intriguing questions this young area has surfaced. We hope to demonstrate that graphical valuations have become a productive meeting point for structural graph theory, parameterized complexity, and fair division.