  We study the problem of dividing a multi-layered cake under non-overlapping
constraints. This problem, recently proposed by Hosseini et al. (IJCAI, 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 layer when the number of agents is a prime power and the number of layers
is at most the number of agents, providing a positive partial answer to an open
question by Hosseini et al. 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\'{c}, Panina, and \v{Z}ivaljevi\'{c} (2020) to the
envy-free division problem of a cake. We further design a fully polynomial-time
approximation scheme (FPTAS) to find an approximate envy-free solution that is
both non-overlapping and contiguous for a two-layered cake division among three
agents with monotone preferences. More generally, we establish all the results
for divisions among groups of almost the same size. When there are three groups
and one layer, our FPTAS is actually able to deal with groups of any
predetermined sizes, still under the monotone preference assumptions. For three
groups, this provides thus an algorithmic version of a recent theorem by
Segal-Halevi and Suksompong (2021). A classical lemma from topology ensures
that every self-map of a simplex mapping each facet to itself is surjective.
This lemma has often been used in economics theory and our algorithm can be
interpreted as an FPTAS counterpart of its two-dimensional version.

Computer Science and Game Theory;Discrete Mathematics