Envy-free division of multi-layered cakes
share
We study the problem of dividing a multi-layered cake among heterogeneous agents under non-overlapping constraints. This problem, recently proposed by Hosseini et al. (2020), captures several natural scenarios such as the allocation of multiple facilities over time where each agent can utilize at most one facility simultaneously, and the allocation of tasks over time where each agent can perform at most one task simultaneously. We establish the existence of an envy-free multi-division that is both non-overlapping and contiguous within each layered cake when the number n of agents is a prime power and the number m of layers is at most n, thus providing a positive partial answer to a recent open question. To achieve this, we employ a new approach based on a general fixed point theorem, originally proven by Volovikov (1996), and recently applied by Jojić, Panina, and Živaljević (2020) to the envy-free division problem of a cake. We further show that for a two-layered cake division among three agents with monotone preferences, an ε-approximate envy-free solution that is both non-overlapping and contiguous can be computed in logarithmic time of 1/ε.
READ FULL TEXT