  In the classical cake cutting problem, a resource must be divided among
agents with different utilities so that each agent believes they have received
a fair share of the resource relative to the other agents. We introduce a
variant of the problem in which we model an underlying social network on the
agents with a graph, and agents only evaluate their shares relative to their
neighbors' in the network. This formulation captures many situations in which
it is unrealistic to assume a global view, and also exposes interesting
phenomena in the original problem.
  Specifically, we say an allocation is locally envy-free if no agent envies a
neighbor's allocation and locally proportional if each agent values her own
allocation as much as the average value of her neighbor's allocations, with the
former implying the latter. While global envy-freeness implies local
envy-freeness, global proportionality does not imply local proportionality, or
vice versa. A general result is that for any two distinct graphs on the same
set of nodes and an allocation, there exists a set of valuation functions such
that the allocation is locally proportional on one but not the other.
  We fully characterize the set of graphs for which an oblivious single-cutter
protocol-- a protocol that uses a single agent to cut the cake into pieces
--admits a bounded protocol with $O(n^2)$ query complexity for locally
envy-free allocations in the Robertson-Webb model. We also consider the price
of envy-freeness, which compares the total utility of an optimal allocation to
the best utility of an allocation that is envy-free. We show that a lower bound
of $\Omega(\sqrt{n})$ on the price of envy-freeness for global allocations in
fact holds for local envy-freeness in any connected undirected graph. Thus,
sparse graphs surprisingly do not provide more flexibility with respect to the
quality of envy-free allocations.
