1379
需用时 02:45
平均分蛋糕并不难,难的是和谐分蛋糕

分蛋糕不但要讲究均衡,还要讲究和谐。如果 n 个人分完蛋糕后,每个人都自认为自己分得了至少 1/n 的蛋糕,但其中两个人还是打起来了,可能是什么原因呢?由于不同的人对蛋糕各部分价值的判断标准不同,因此完全有可能出现这样的情况——虽然自己已经分到了至少 1/n 份,但在他看来,有个人手里的蛋糕比他还多。所谓和谐分蛋糕,就是要求每个人都认为别人的蛋糕都没我手里的好。在公平分割理论中,我们把满足这个条件的分蛋糕方案叫做免嫉妒分割 (envy-free division)。

更严格的要求:免嫉妒分割

免嫉妒分割是一个比均衡分割更强的要求。如果每个人的蛋糕都没我多,那我的蛋糕至少有 1/n,也就是说满足免嫉妒条件的分割一定满足均衡的条件。但反过来,满足均衡条件的分割却不一定是免嫉妒的。比方说,A、B、C 三人分蛋糕,但 A 只在乎蛋糕的体积,B 只关心蛋糕上的草莓颗数,C 只关心蛋糕上的巧克力块数。最后分得的结果是,A、B、C 三人的蛋糕体积相等,但 A 的蛋糕上什么都没有,B 的蛋糕上有一颗草莓两块巧克力,C 的蛋糕上有两颗草莓一块巧克力。因此,每个人从自己的角度来看都获得了整个蛋糕恰好 1/3 的价值,但这样的分法明显是不科学的——B、C 两人会互相嫉妒。

之前我们介绍的两种均衡分割方案,它们都不满足免嫉妒性。就拿第一种方案来说吧,如果有三个人分蛋糕,按照规则,首先应该让第一人分第二人选,然后两人各自把自己的蛋糕切成三等份,让第三人从每个人手中各挑一份。这种分法能保证每个人获得至少1/3的蛋糕,但却可能出现这样的情况:第三个人从第二个人手中挑选的部分,恰好是第一个人非常想要的。这样一来,第一个人就会觉得第三个人手里的蛋糕更好一些,这种分法就不和谐了。

三人免嫉妒分割方案

构造一套免嫉妒的分割方案非常困难。1960 年,John Selfridge 和 John Conway 各自独立地分析了人数为 3 的情况,构造出了第一个满足免嫉妒条件的三人分割方案。这种分割方案就被称为“Selfridge-Conway 算法”。

首先,A 把蛋糕分成三等份(当然是按照自己的看法来分的,后面提到的切分、选取也都是这样)。如果 B 认为这三块蛋糕中较大的两块是一样大的,那么按照 C、B、A 的顺序依次选取蛋糕,问题就解决了。麻烦就麻烦在 B 认为较大的两块蛋糕不一样大的情况。此时,B 就把最大的那块蛋糕的其中一小部分切下来,让剩余的部分和第二大的蛋糕一样大。被切除的部分暂时扔在一旁,在第二轮分割时再来处理。接下来,按照 C、B、A 的顺序依次选蛋糕,但有一个限制:如果 C 没有选那块被修剪过的蛋糕,B 就必须选它。

这样,三人就各分得了一块蛋糕。由于 A 是切蛋糕的人,对于他来说拿到哪一块都一样,因此 A 不会嫉妒别人。由于 B 选取的是两个较大块中的一个,因此 B 也不会嫉妒别人。由于 C 是第一个选蛋糕的,显然他也不会嫉妒别人。因此,就目前来说,三个人之间是不会有嫉妒发生的。

但是,还有一小块被切除的部分没分完,因此分割流程进入第二轮。

在 B 和 C 之间,一定有一个人选择了那块被修剪过的蛋糕。不妨把这个人重新记作 X,另一个人就记作 Y。让 Y 把最后那一小块分成三等份,按照 X、A、Y 的顺序依次挑选蛋糕,结束第二轮流程。这一轮结束后,每个人都又得到了一小块蛋糕。由于 X 是第一个选蛋糕的人,X 显然不会嫉妒别人;由于 Y 是分蛋糕的人,Y 也不会嫉妒别人。由于 A 比 Y 先选,A 不会嫉妒 Y。最后,A 也是不会嫉妒 X 的,因为即使 X 拥有了第二轮中的全部蛋糕,X 手里的蛋糕加起来也只是第一轮开始时 A 等分出来的其中一块蛋糕,这是不可能超过 A 的。这就说明了,三个人之间仍然不会有嫉妒发生,Selfridge-Conway 算法的确满足免嫉妒条件。

不过,Selfridge-Conway 算法只能在三人分蛋糕时使用,并不能扩展到人数更多的情况。对于人数更多的情况,免嫉妒分割问题更加困难,目前数学家们还没有找到一个比较可行的方案。正如数学家 Sol Garfunkel 所说,分蛋糕问题是 20 世纪数学研究中最重要的问题之一。直到现在,也还有一大群数学家正投身于分蛋糕问题之中,研究包括免嫉妒性在内的各种公平条件,致力于构造新的公平分割方案。

The End

发布于2010-11-26, 本文版权属于果壳网(guokr.com),禁止转载。如有需要,请联系果壳

举报这篇文章

matrix67

数学狂

pic