Envy-Free and Efficient Allocations for Graphical Valuations

In graphical valuations, agents are the vertices of a graph and every item is an edge that only its two endpoints care about. Such instances always admit allocations that are envy-free up to any item (EFX), but what about exact envy-freeness? In joint work with Aditi Sethia, I show that with binary utilities you can decide in polynomial time whether an envy-free allocation exists, while utilities from {0, 1, d} already make the problem NP-hard. With few distinct utilities, it is fixed-parameter tractable in the vertex cover number. I also measure the welfare cost of EFX: none for binary utilities, unbounded beyond them.