Cake Cutting with Single-Peaked Valuations

In the cake cutting problem, one allocates a heterogeneous divisible resource (cake) to n participating agents. The central criteria of an allocation to satisfy and optimize is envy-freeness and efficiency. In this paper, we consider cake cutting with single-peaked preferences: each agent is assumed to have a favorite point in the cake; the further a piece of cake is from her favorite point, the less her valuation on this piece is. Under this assumption, agents can be considered as a point embedded in a metric space, and thus this setting models many practical scenarios. We present a protocol in the standard query model which outputs an envy-free allocation in linear running time.