Leírás
Dividing a multi-layered cake under non-overlapping constraints captures several scenarios, e.g, allocating multiple facilities over time where each agent can utilize at most one facility simultaneously. We establish the existence of an envy-free multi-division that is non-overlapping and contiguous within each layer when the number of agents is a prime power, solving partially an open question by Hosseini et al. (2020). Our approach follows an idea proposed by Jojić et al. (2020) for envy-free divisions, relying on a general fixed-point theorem. We further design a fully polynomial-time approximation scheme for the two-layer three-agent case, with monotone preferences. All results are actually established for divisions among groups of almost the same size. In the one-layer three-group case, our algorithm is able to deal with any predetermined sizes, still with monotone preferences. For three groups, this provides an algorithmic version of a recent theorem by Segal-Halevi and Suksompong (2021).
Joint work with Ayumi Igarashi