切好蛋糕，然后吃掉它

 

原文作者，Marianne Freiberger，转自Plus网站。

翻译作者，小鹤e，哆嗒数学网翻译组成员。

校对：Radium

 

关注 哆嗒数学网 每天获得更多数学趣文

 

两位计算机科学家采用一种新方法把蛋糕分给任意数量的人，而不引起任何人的嫉妒，因而在切蛋糕理论上取得了突破。这个结果不仅仅与生日派对有关:无论是土地资源、播出时间还是石油资源，蛋糕可以代表任何连续的研究对象。从离婚诉讼到政治冲突，切蛋糕理论的灵感来自于各种各样的问题。

当只有两个人分蛋糕时，问题就很简单了。让第一个人切蛋糕，第二个人选择他想要的那块。第一个人会确保他切的蛋糕中的两个部分他都很满意。根据喜好和蛋糕上的东西，第一个人可能会把蛋糕切成两等份，或者切成一块小一块大，但小的那块有草莓。无论第二个人选择哪一块，第一个人都不会嫉妒。第二个人可能不喜欢切蛋糕的方式，但是，因为他或她先挑，所以也不会嫉妒第一个人的那块。一般来说，如果没有人嫉妒其他人的蛋糕，那么该分法就称为无嫉妒分法。

 

 

这种针对两个人的分法早已为人所知，但直到20世纪60年代，数学家约翰·塞尔弗里奇(John L. Selfridge)才发明了一种适用于三人最优而高效的方法(后来约翰·康韦(John H. Conway)也独立发现)。1995年，史蒂文·布拉姆斯(Steven J. Brams)和艾伦·泰勒(Alan D. Taylor)提出了一种突破性的方法，适用于任何人，但有一个缺点。即使只有四个人吃蛋糕，公平划分所需的切割步骤也可能是任意大的。为了找到划分方法主刀人需要问吃蛋糕的人一些问题——这与划分方法完成所需的时间有关——可能是任意大的。这个界限究竟有多大取决于参与者的偏好(如果你幸运的话，它们可能很小)，但关键是你不能从一开始就限制算法运行的时间和需要进行多少次划分。这尤其令人失望，因为数学家们确认，对于吃蛋糕的n个人来说，只需要切n-1刀就有一个无嫉妒分法。问题只是在于找到那个分法。

一种变动是允许移动刀：主刀人将刀(或几把刀)在蛋糕上移动，当吃蛋糕的人认为应该切蛋糕时大喊“停”。至少对于四个吃蛋糕的人来说，这使得切蛋糕的步骤减少到五步。但是吃蛋糕的人要做无数次决定。对于刀在轴上移动的每个点，他们需要决定是否喊停。由于我们真正想要的是一个可以在计算机上运行的离散分步算法，这种移动刀的方法并不完全令人满意。

由哈里斯·阿齐兹(Haris Aziz)和西蒙·麦肯齐(Simon MacKenzie)设计的这种新方法是离散的，它规定了切蛋糕的数量，以及主刀人需要向吃蛋糕的人提出的问题的数量。无界限方法的合作者Brams对这个结果很满意：“我相信Azizz - Mackenzie算法是一个重要的理论结果，肯定有所突破，而我们之前用泰勒得到的结果——通过限定算法所需的步长(或切割步骤)——证明了它是有限的，但我们无法确定它的上限。”

这就意味着像蛋糕一样的冲突可以在一瞬间解决了吗?不完全是——阿齐兹和麦肯齐的结果纯粹是理论上的兴趣。当涉及到n个吃蛋糕的人时，你需要问的问题的数量界限如下一个数：

不管吃蛋糕的人喜欢什么，问题个数超过这个数字后，你都不需要继续问下去。但这仍然导致了难以想象的过大的界限:即使对于n=2，标准计算器也会崩溃。布拉姆斯说:“无论是否使用移动刀，要缩小这种界限都是一个挑战。”“然而，我不认为这样的数字会让这些算法有任何实用价值。”

 

还有一个问题。Aziz 和MacKenzie的方法保证了没有人会嫉妒别人的蛋糕。但这并不能保证每个人都满意。可能存在另一种蛋糕的划分，它让一个或多个吃蛋糕的人更满意，而且不会让任何人变得更嫉妒他人——用数学表达就是，无嫉妒法通常不是帕累托最优的。吃蛋糕的人可能会抱怨:他们可能不会嫉妒别人的蛋糕，但如果知道自己可以在其他划分方法中获得的更多，他们可能也会很不高兴。同时满足无嫉妒和帕累托最优往往是不可能的。因此，尽管理论家们在努力降低算法的界限，但现实中的实践者们需要认真思考，在特定的冲突中，哪种划分是最好的:无嫉妒、帕累托最优，还是其他一些标准。

 

如何把蛋糕分给三个人，使得三个人都不会嫉妒别人。

假设我们的三个人分别被称为A、B和C，我们不分性别地把每个人称为“他”。首先，C把蛋糕切成它认为有相同价值的三块。然后A和B各自挑选。如果他们选择两个不同的部分，这个过程就完成了。

假设A和B想要相同的一块蛋糕。在这种情况下，B会对它认为最有价值的蛋糕进行一些修剪，以匹配B认为第二有价值的那部分蛋糕。把切下来的余料放在一边，让A先挑。接下来，B选择他的那块，但有一个条件，如果A没有选择被修剪的那块，那么B必须选择它。最后，C选择。现在A不嫉妒了，因为它第一个选择。B不嫉妒，因为它的第一个选择是同等价值的:无论A选择什么，都有一个同等价值的部分留给B。C也不嫉妒，因为从C的角度来看，唯一降低了价值的部分，是被修减了的那块，但它会被A或B拿走，而最初的三个部分对它来说是同等价值的。

这样就剩下余料那部分了。假设在前一轮中被裁掉的蛋糕被A选中。让B把余料分成它认为有同样价值的三块。让A第一个选，C第二个选，B最后选。A不嫉妒，因为它先选。如果C嫉妒，那么它一定是嫉妒A，因为C在第一轮中是满意的，第二轮时，它选在B之前，所以它也不嫉妒B。那么C嫉妒A吗?在第一轮中，A选择了被修剪掉的那块蛋糕，也就是说，A在第一轮中选择了对C来说没有其他两块那么大的蛋糕。我们用V表示在C眼中最初3块蛋糕的价值。我们把W记为C眼中余料的价值。现在对C来说总价值是V加上W；而C眼中分配给A的价值是V-W加上部分W显然，V-W加上部分W的总是小于V，也就是说，C认为，A分配给A自己的价值小于C分配给它的价值，因此C不嫉妒A。

如果是B在第一轮中选择了被修剪的那块呢?在这种情况下，只需交换上一段中A和B的角色。

 

关注 哆嗒数学网 每天获得更多数学趣文