  The classical cake cutting problem studies how to find fair allocations of a
heterogeneous and divisible resource among multiple agents. Two of the most
commonly studied fairness concepts in cake cutting are proportionality and
envy-freeness. It is well known that a proportional allocation among $n$ agents
can be found efficiently via simple protocols [16]. For envy-freeness, in a
recent breakthrough, Aziz and Mackenzie [5] proposed a discrete and bounded
envy-free protocol for any number of players. However, the protocol suffers
from high multiple-exponential query complexity and it remains open to find
simpler and more efficient envy-free protocols.
  In this paper we consider a variation of the cake cutting problem by assuming
an underlying graph over the agents whose edges describe their acquaintance
relationships, and agents evaluate their shares relatively to those of their
neighbors. An allocation is called locally proportional if each agent thinks
she receives at least the average value over her neighbors. Local
proportionality generalizes proportionality and is in an interesting middle
ground between proportionality and envy-freeness: its existence is guaranteed
by that of an envy-free allocation, but no simple protocol is known to produce
such a locally proportional allocation for general graphs. Previous works
showed locally proportional protocols for special classes of graphs, and it is
listed in both [1] and [8] as an open question to design simple locally
proportional protocols for more general classes of graphs. In this paper we
completely resolved this open question by presenting a discrete and bounded
locally proportional protocol for any given graphs. Our protocol has a query
complexity of only single exponential, which is significantly smaller than the
six towers of $n$ query complexity of the envy-free protocol given in [5].
