编辑推荐：
公平分配多层面蛋糕资源，在可行性和连续性约束下，提出双刀计算模型，证明两代理两层面存在精确分配，扩展至三层面及更多代理，并推广至2^a*3层和n≥2^a*3代理的分配。
Mohammad Azharuddin Sanpui
印度理工学院卡尔哈格普尔分校数学系，卡尔哈格普尔-721302，印度
摘要
我们考虑多层蛋糕切割问题，以便在满足连续性和可行性两个约束的前提下，公平地将可分割的资源（蛋糕的各层）分配给一组代理。首先，我们引入了一种新的多层蛋糕计算模型，称为“一对刀具”。接着，我们利用这个新模型证明了两个代理和两层蛋糕的精确多分配方案的存在性。然后，我们展示了如何为三层蛋糕及三个以上代理计算出既可行又连续的比例多分配方案。最后，我们开发了一种技术，可以计算出任意数量$n \geq 2^a \times 3$的代理和$2^a \times 3$层蛋糕的比例分配方案，其中$a$为任意正整数。
引言
在我们的日常生活中，有许多时间安排的情况，我们需要合理规划时间以完成日常任务。假设有一组大学生希望同时使用两种设施，比如参加研讨会或进行室内游戏。这两种设施的开放和关闭时间相同。小组中的每个人都愿意使用这两种设施，但每个人对使用每种设施的时间段有各自的偏好。
简单来说，分蛋糕的问题是一个比喻，用来说明如何公平地将资源分配给具有不同偏好的$n$个代理。蛋糕切割问题是公平分配理论中的核心主题[1]、[2]、[3]、[4]，并且在数学、经济学、政治科学和计算机科学领域也受到了广泛关注[5]、[6]、[7]、[8]、[9]、[10]。在蛋糕切割研究中，“无嫉妒”和“比例性”是最重要的公平分配标准。在无嫉妒的分配中，每个代理对其分配到的蛋糕部分都感到满意，而不会嫉妒其他代理的分配结果。在比例性分配中，每个代理至少获得其估计的蛋糕价值的$\frac{1}{n}$。当所有蛋糕都被分配完毕时，无嫉妒性就意味着分配是按比例进行的。众所周知，即使规定每个代理必须获得连续的蛋糕部分，无嫉妒的分配也是存在的[11]、[12]。除了存在性之外，这一过程的算法设计也长期以来一直是研究重点[14]、[15]、[16]、[17]、[18]、[19]。
我们不能将上述例子中的获取多种设施的问题视为蛋糕切割问题[20]。我们必须独立地划分两个时间段，以便每个代理都能使用这两种设施。现在的问题是如何根据他们的偏好公平地划分每个设施的时间段。这样，每个学生都可以使用每种设施，并且每个设施的分配时间段永远不会重叠。基于这些约束，Hosseini等人[20]提出了多层蛋糕切割问题。在多层蛋糕切割问题中，我们将每个设施视为一层可分割的异质蛋糕。每个学生对不重叠的时间段有一个加性偏好，称为“估值”。需要注意的是，不同学生对同一部分蛋糕的估值可能大相径庭。如果没有任何学生的时间段重叠，那么多层蛋糕的切割就是可行的；如果每个代理都能获得连续的时间段，那么切割就是连续的。我们在多层蛋糕切割中的目标是找到既公平又满足连续性和可行性约束的多分配方案（见表1）。
在第3节中，我们利用Austin移动刀具的思想证明了两个代理的精确可行多分配方案的存在性。第4节中，我们证明了对于三层蛋糕和任意数量$n \geq 3$的代理，存在一个既可行又连续的比例多分配方案。我们还证明了对于$2^a \times 3$层蛋糕和$n \geq 2^a \times 3$个代理，也存在一个既可行又连续的比例多分配方案，其中$a$为任意正整数。
蛋糕切割问题是公平分配的关键框架，它展示了如何在不同偏好个体之间公平分配可分割和异质资源。近年来，这一主题在经济学、数学和计算机科学文献中被广泛研究[21]、[22]、[23]、[24]、[25]。为了在代理群体之间公平分配多种可分割资源，Hosseini等人[20]提出了多层蛋糕切割的研究。他们证明了对于两层蛋糕和三种偏好类型的三个代理，存在一个既无嫉妒又可行的连续多分配方案。Igarashi和Meunier[26]也利用组合拓扑学证明了，当代理数量是质数幂且层数不超过代理数量时，存在一个既无嫉妒又可行的连续多分配方案。还有一些论文研究了多层蛋糕切割问题，其中代理可以无限制地同时从所有分配到的部分中受益[27]、[28]、[29]。
章节摘录
预备知识
我们考虑了Hosseini等人[20]提出的多层蛋糕切割概念。在切割多层蛋糕的问题中，会指定层数和代理的数量。模型设置包括一组代理$\{1, 2, \ldots, n\}$和一组层$\{1, 2, \ldots, m\}$。$m$层蛋糕用$\mathbb{M} = \{(L_{\ell} \mid L_{\ell} \subseteq [0, 1] \}$表示，其中$L_{\ell} \in \mathbb{M}$。每个代理$i \in \{1, 2, \ldots, n\}$对不重叠的时间段有一个加性偏好（即“估值”）。注意，不同学生对同一部分蛋糕的估值可能完全不同。如果没有任何代理的时间段重叠，则多层蛋糕的切割是可行的；如果每个代理都能获得连续的时间段，则切割是连续的。我们在多层蛋糕切割中的目标是找到既公平又满足连续性和可行性约束的多分配方案。
在第3节中，我们利用Austin移动刀具的思想证明了两个代理的精确可行多分配方案的存在性。第4节中，我们证明了对于三层蛋糕和任意数量$n \geq 3$的代理，存在一个既可行又连续的比例多分配方案。我们还证明了对于$2^a \times 3$层蛋糕和$n \geq 2^a \times 3$个代理，也存在一个既可行又连续的比例多分配方案，其中$a \in \mathbb{N}$。
蛋糕切割问题是公平分配的关键框架，它展示了如何在具有不同偏好的个体之间公平分配可分割和异质资源。近年来，这一主题在经济学、数学和计算机科学文献中得到了广泛研究[21]、[22]、[23]、[24]、[25]。为了在代理群体之间公平分配多种可分割资源，Hosseini等人[20]提出了多层蛋糕切割的研究。他们证明了对于两层蛋糕和三种偏好类型的三个代理，存在一个既无嫉妒又可行的连续多分配方案。Igarashi和Meunier[26]也利用组合拓扑学证明了，当代理数量是质数幂且层数不超过代理数量时，存在一个既无嫉妒又可行的连续多分配方案。还有一些论文研究了多层蛋糕切割问题，其中代理可以无限制地同时从所有分配到的部分中受益[27]、[28]、[29]。
章节片段
初步知识
我们考虑了Hosseini等人[20]提出的多层蛋糕切割概念。在切割多层蛋糕的问题中，会指定层数和代理的数量。模型设置包括一组代理$\{1, 2, \ldots, n\}$和一组层$\{1, 2, \ldots, m\}$。$m$层蛋糕用$\mathbb{C} = \{(L_{\ell} \mid L_{\ell} \subseteq [0, 1] \}$表示，其中$L_{\ell} \in \mathbb{M}$。每个代理$i \in \{1, 2, \ldots, n\}$对不重叠的时间段有一个加性偏好（即“估值”）。由于每个代理的偏好可能不同，因此对同一部分蛋糕的估值也可能大相径庭。如果没有任何代理的时间段重叠，则多层蛋糕的切割是可行的；如果每个代理都能获得连续的时间段，则切割是连续的。
精确的多层蛋糕切割
我们分析了为两个代理在两层蛋糕上获得精确多分配的挑战。Austin移动刀具方法为证明精确多分配的存在提供了基本概念。Austin移动刀具方法主要使用的数学工具是中间值定理[30]。简单来说，我们通过不断移动一对刀具（如下定义）来实现目标。
比例多层蛋糕切割
Igarashi和Meunier[26]利用组合拓扑学证明了对于任意层数$m$和任意数量$n \geq m$的代理，存在一个既可行又连续的比例多分配方案。我们的主要目标是利用Hosseini等人[20]提出的计算模型来证明公平多分配的存在性。通过使用Hosseini等人提出的切割和评估查询，我们展示了如何计算出既可行又连续的比例多分配方案。
讨论
我们研究了多层蛋糕切割问题，即在满足可行性和连续性两个约束的前提下，将多层蛋糕分配给一组代理。在第3节中，我们提出了一种新的计算模型。然后，我们利用这种新模型证明了两个代理和两层蛋糕的精确可行多分配方案的存在性。在第4节中，我们展示了如何为三层蛋糕和任意数量大于三个的代理计算出比例多分配方案。
CRediT作者贡献声明
Mohammad Azharuddin Sanpui：撰写 – 审稿与编辑，撰写 – 原始草稿，可视化，监督，形式分析，概念化。
利益冲突声明
作者声明他没有已知的财务利益或个人关系可能影响本文报告的工作。
