Approximate envy-freeness in graphical cake cutting

We study the problem of fairly allocating a divisible resource in the form of a graph, also known as graphical cake cutting.Unlike for the canonical interval cake, a connected envy-free allocation is not guaranteed to exist for a graphical cake.We focus on the existence and computation of connected allocations with low envy.For general graphs, we show that there is always a 1/2-additive-envy-free allocation and, if the agents' valuations are identical, a (2 + ǫ)-multiplicative-envy-free allocation for any ǫ > 0. In the case of star graphs, we obtain a multiplicative factor of 3 + ǫ for arbitrary valuations and 2 for identical valuations.We also derive guarantees when each agent can receive more than one connected piece.All of our results come with efficient algorithms for computing the respective allocations.1 Without this assumption, one cannot obtain nontrivial envy-free guarantees-see the caption of Figure 1 (right) for a brief discussion. 2 Star graphs (and path graphs) are also often studied in the context of indivisible items (see Section 1.2).In graphical cake cutting, all path graphs are equivalent to the classic interval cake, which is why the role of star graphs is further highlighted. 3We discuss further motivation for investigating this case at the beginning of Section 4.