两位年轻的计算机科学家已经弄清楚了如何将蛋糕公平地分配给任意数量的人，从而解决了数学家们几十年来一直在努力解决的问题。他们的工作让许多研究人员感到震惊，他们认为这种公平分配协议可能是不可能的。
蛋糕切割是许多现实世界问题的隐喻，这些问题涉及在那些对其特征有不同价值的人之间分配一些连续的对象，无论是蛋糕还是土地，例如，一个人渴望巧克力糖霜，而另一个人则盯着奶油花。至少从圣经时代起，人们就知道有一种方法可以在两个人之间分配这样的物体，这样谁也不会嫉妒对方：一个人将蛋糕切成两片她认为价值相等的切片，另一个人可以选择她最喜欢的切片。《创世纪》中，亚伯拉罕（当时被称为亚伯兰）和罗得使用这种“我切你选”的程序来分割土地，亚伯拉罕决定在哪里分割，罗得在约旦和迦南之间选择。
关于支持科学新闻
如果您喜欢这篇文章，请考虑通过以下方式支持我们屡获殊荣的新闻报道 订阅。通过购买订阅，您正在帮助确保关于塑造我们当今世界的发现和想法的具有影响力的故事的未来。
大约在 1960 年，数学家们设计出一种算法，可以为三名参与者产生类似的“无嫉妒”蛋糕分配。但直到现在，他们为三名以上参与者提出的最佳方案是政治学家 Steven Brams 和数学家 Alan Taylor 于 1995 年创建的 程序，该程序保证产生无嫉妒的分配，但它是“无界的”，这意味着它可能需要运行一百万步、十亿步或任何大数字，具体取决于参与者对蛋糕的偏好。
Brams 和 Taylor 的算法在当时被誉为一项突破，但卡内基梅隆大学的计算机科学家，也是 Spliddit 的创建者之一 Ariel Procaccia 说：“我认为它不是有界的这一事实是一个巨大的缺点”，Spliddit 是一种免费的在线工具，为室友之间分配家务或租金等任务提供公平分配算法。
在过去的 50 年里，包括 Procaccia 在内的许多数学家和计算机科学家都确信，对于在 n 个参与者之间分配蛋糕，可能没有有界的、无嫉妒的算法。
“这正是我进入公平分配主题的原因，”宾夕法尼亚州布林莫尔学院的数学教授 Walter Stromquist 说，他在 1980 年证明了一些关于蛋糕切割的开创性成果。“我一生都认为，当我有了时间，我会回到这个问题，并证明这个特定结果的扩展是不可能的。”
但在四月份，两位计算机科学家推翻了人们的期望，他们在 在线发布的一篇论文 中描述了一种无嫉妒的蛋糕切割算法，该算法的运行时间仅取决于参与者的数量，而不是他们的个人偏好。其中一位——卡内基梅隆大学的博士后研究员，27 岁的 Simon Mackenzie——将于 10 月 10 日在第 57 届 IEEE 计算机科学基础研讨会上展示该团队的发现，该研讨会是计算机科学领域最重要的会议之一。
该算法非常复杂：在 n 个参与者之间分配蛋糕可能需要多达 n^n^n^n^n^n 步以及大致等效的切割次数。即使只是少数参与者，这个数字也大于宇宙中原子的数量。但该团队的另一半成员，新南威尔士大学和澳大利亚数据研究小组 Data61 的 35 岁计算机科学家 Haris Aziz 说，研究人员已经有了使该算法更简单、更快的想法。
Procaccia 说，对于研究 公平分配理论 的人来说，这是“近几十年来最重要的成果”。
蛋糕块
Aziz 和 Mackenzie 的新算法建立在数学家 John Selfridge 和 John Conway 大约在 1960 年独立提出的，用于在三个人之间分配蛋糕的优雅程序之上。
如果 Alice、Bob 和 Charlie 想要分享一块蛋糕，该算法首先让 Charlie 将蛋糕切成三块，从他的角度来看，这三块蛋糕的价值相等。Alice 和 Bob 各自被要求指向他们最喜欢的切片，如果他们喜欢不同的切片，我们就完成了——他们各自拿走他们最喜欢的切片，Charlie 拿走剩下的切片，每个人都高高兴兴地回家。
如果 Alice 和 Bob 有相同的最爱，那么要求 Bob 从该切片上修剪掉一点蛋糕，以便剩余部分的值等于他的第二喜欢的切片；修剪下来的部分放在一边稍后处理。现在 Alice 可以从这三片蛋糕中选择她最喜欢的一片，然后 Bob 可以选择，但要求是，如果 Alice 没有选择修剪过的切片，他必须拿走它。Charlie 得到第三片切片。
在这个阶段，没有一个参与者嫉妒对方。Alice 很高兴，因为她先选择了；Bob 很高兴，因为他得到了他两个同样喜欢的首选之一；Charlie 很高兴，因为他得到了他最初的三块中的一块，在他看来，这三块都是相等的。
但是，仍然有修剪下来的部分需要分配。使分配这部分而不会产生更多修剪，并且陷入修剪和选择的无限循环成为可能的原因是，Charlie 对他目前得到的蛋糕不仅仅是满意；即使得到修剪切片的玩家得到所有等待分配的蛋糕，他也不会感到被欺骗，因为修剪切片加上修剪等于原始切片之一。Aziz 和 Mackenzie 通过说 Charlie “支配”了得到修剪切片的玩家来描述这种关系。
现在，例如，如果 Alice 是得到修剪切片的人，则算法按如下方式进行：Bob 将修剪下来的部分切成他认为价值相等的三块，然后首先 Alice 选择一块，然后是 Charlie，然后是 Bob。每个人都很高兴：Alice 因为她先选择了，Charlie 因为他得到了一块他比 Bob 更喜欢的切片（并且他不在乎 Alice 拿了多少），而 Bob 因为这三块切片在他看来是相等的。
Brams 和 Taylor 在设计他们 1995 年的算法时使用了支配的概念（没有这样称呼它），但他们无法将这个想法推进到足以获得有界算法。在接下来的 20 年里，其他人也做不到。“我认为这不是因为缺乏尝试，”Procaccia 说。
新手蛋糕切割者
当 Aziz 和 Mackenzie 几年前决定着手解决这个问题时，他们是蛋糕切割问题方面相对的新手。“我们没有那些一直在深入研究这个问题的人那么多的背景，”Aziz 说。“虽然这在大多数情况下是一个缺点，但在这种情况下，这在某种程度上是一个优势，因为我们没有以相同的方式思考。”
Aziz 和 Mackenzie 从头开始研究三方问题来试水，他们的分析最终引导他们找到了 四方案例的有界无嫉妒算法，他们于去年在网上发布了该算法。
他们无法立即看到如何将他们的算法扩展到四个以上的参与者，但他们狂热地投入到这个问题中。“在我们提交了四方案例的论文后，我们非常渴望在我们更资深、更聪明的人将其推广到 n 方案例之前尝试一下，”Aziz 说。大约一年后，他们的努力取得了成功。
与 Selfridge-Conway 算法一样，Aziz 和 Mackenzie 的复杂协议反复要求个别参与者将蛋糕切成 n 块相等的部分，然后要求其他参与者进行修剪并选择蛋糕块。但该算法还执行其他步骤，例如定期以仔细控制的方式交换参与者的蛋糕储藏部分，目的是增加参与者之间支配关系的数量。
这些支配关系使 Aziz 和 Mackenzie 能够降低问题的复杂性：例如，如果三名参与者支配了所有其他人，那么可以将这三名参与者连同他们的蛋糕切片一起送走——无论谁得到剩余的修剪部分，他们都会很高兴。现在需要担心的参与者更少了，并且在有限数量的此类步骤之后，每个人都已得到满足，并且所有蛋糕都已分发完毕。
Procaccia 说：“回顾一下，该算法有多么复杂，有人花这么长时间才找到一个算法也就不足为奇了。”但 Aziz 和 Mackenzie 已经认为他们可以大大简化他们的算法，使其成为一个不需要蛋糕交换并且少于 n^n^n 步的算法。Aziz 说，他们目前正在撰写这些新成果。
Brams 警告说，即使是更简单的此类算法也不太可能具有实际意义，因为参与者收到的蛋糕部分通常包括来自蛋糕不同部分的许多微小的碎屑——如果您要分配像土地这样的东西，这不是一种可行的方法。
但对于研究蛋糕切割的数学家和计算机科学家来说，Stromquist 说，新结果“重置了这个主题”。
Procaccia 说，既然研究人员知道可以在有限步数内公平地分配蛋糕，那么下一个目标是了解 Aziz 和 Mackenzie 的上限与分配蛋糕所需的现有下限切割次数之间的巨大差距。Procaccia 之前证明了，无嫉妒的蛋糕切割算法将至少需要大约 n2 步——但与 n^n^n^n^n^n 甚至 n^n^n 相比，这个界限微不足道。
Aziz 说，研究人员现在必须弄清楚如何弥合这一差距。“我认为在这两个方向上都可能取得进展。”
经 Quanta 杂志 许可转载，Quanta 杂志是 西蒙斯基金会 的编辑独立出版物
其使命是通过报道数学、物理和生命科学的研究进展和趋势，增进公众对科学的理解。