Abstract
We introduce a graphical framework for fair division in cake cutting, where comparisons between
agents are limited by an underlying network structure. We generalize the classical fairness notions of
envy-freeness and proportionality to this graphical
setting. Given a simple undirected graph G, an allocation is envy-free on G if no agent envies any of
her neighbor’s share, and is proportional on G if
every agent values her own share no less than the
average among her neighbors, with respect to her
own measure. These generalizations open new research directions in developing simple and efficient
algorithms that can produce fair allocations under
specific graph structures