Relaxations of Envy-Freeness Over Graphs

In allocating a set of indivisible items among agents, the condition of envy-freeness cannot always be achieved. Envy-freeness up to any good (EFX) and envy-freeness with 𝑘 hidden items (HEF-𝑘) are two compelling relaxations of envy-freeness, which remain elusive in many settings. We study a natural relaxation of these two fairness constraints, where we place the agents on the vertices of a graph, and only require that our allocations satisfy the EFX (resp. HEF) constraint on the edges of the graph. We refer to these allocations as graph-EFX (resp. graph-HEF) or simply 𝐺-EFX (resp. 𝐺-HEF) allocations. We show that, for any graph 𝐺, there always exists a 𝐺-HEF-𝑘 allocation of goods, where 𝑘 is the size of a minimum vertex cover of 𝐺, and this is tight. We show that 𝐺-EFX allocations of goods exist for three different classes of graphs-two of them generalizing the star 𝐾 1,𝑛-1 and the third generalizing the threeedge path 𝑃 4. Many of these results extend to allocations of chores as well. Overall, we show several natural settings in which the graph structure helps obtain strong fairness guarantees. Finally, we devise an algorithm tested using Spliddit data, to show that 𝐺-EFX allocations appear to exist for paths 𝑃 𝑛 , pointing the way towards generalizing our results to even broader families of graphs.