Envy-Free Division of Multilayered Cakes

• 成果类型: Article
• 署名作者: Igarashi, Ayumi; Meunier, Frederic
• 署名单位: University of Tokyo; Institut Polytechnique de Paris; Ecole des Ponts ParisTech
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.0350
• 发表日期: 2025
• 关键词: cut; sperners

摘要

Dividing a multilayered cake under nonoverlapping 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 nonoverlapping and contiguous within each layer when the number of agents is a prime power, solving partially an open question by Hosseini et al. [Hosseini H, Igarashi A, Searns A (2020) Fair division of time: Multi-layered cake cutting. Proc. 29th Internat. Joint Conf. Artificial Intelligence (IJCAI), 182-188; Hosseini H, Igarashi A, Searns A (2020) Fair division of time: Multi-layered cake cutting. Preprint, submitted April 28, http://arxiv.org/abs/2004.13397]. Our approach follows an idea proposed by Jojic et al. [Jojic D, Panina G,.Zivaljevic R (2021) Splitting necklaces, with constraints. SIAM J. Discrete Math. 35(2):1268-1286] 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 [Segal-Halevi E, Suksompong W (2021) How to cut a cake fairly: A generalization to groups.