On the Structure of Envy-Free Orientations on Graphs
Given a set of goods to be allocated amongst agents, an allocation is envy-free up to any item (EFX) if no agent values any strict subset of another agent’s bundle over their own. The existence of EFX is a major open problem in fair division. Recently, Christodoulou, Fiat, Koutsoupias, and Sgouritsa studied a setting on a graph where the vertices were the agents and the edges were the goods, with each agent valuing only incident edges. They showed that an allocation was always possible, but if the allocation was restricted to a graph orientation, determining whether an EFX orientation existed was NP-hard.
To answer one of their open problems in their paper, we introduce the idea of strongly EFX orientable graphs, which are graphs that have EFX orientations regardless of any valuation on the edges. We make progress towards characterizing strongly EFX orientable graphs by studying the case where all the valuations on edges are either 0 or 1, and prove that in general, all strongly EFX orientable graphs are tripartite. This is joint work with Ruta Mehta.