分蛋糕是一门复杂的艺术

by Matrix on 7月 25, 2009

(维基百科)

谁偷吃了一块?

这篇文章是几天前写的《分蛋糕是极其复杂的》的扩充,最近实在没空码太多字,本文也只是寥寥而作。
在数学社会学,尤其是博弈论中,Envy-free(翻译过来大概就是“没有嫉妒”或“心满意足”?)是专门指如何给N位满腹心事各怀鬼胎的人分东西,比如蛋糕、糖果,如何让每个人都感到心满意足。大概我们这些从小受孔融让梨(人家是成功人士,虽被“恶人”曹操杀了,但好歹是励志故事),尊老爱幼教育的人不以为然,但每当看到别人拿走自己眼里的“大块”蛋糕(或肉、鱼、鸡腿),是否心理会隐隐感到不快,也就是嫉妒?然后说不定还藏在心底,该天再报复一下:-)很多时候公平是能让问题消于无形。


分蛋糕或公平分配问题最早是Steinhaus于1948年提出的,1980 年费城Swarthmore学院的Walter Stromquist证明存在一个Envy-free解。换句话说,一块蛋糕切N-1次分给N个人,让每个人都满意是可能的。N=2和N=3的情况比较简单(其实N=3已经相当繁琐了),1992年Steven Brams和Alan Taylor证明了N>3的情况,但算法过于复杂,他们为此特地写了一本书来剖析如何公平的分蛋糕。最近香港城市大学的Xiaotie Deng和同事提出了一种更高效分蛋糕算法,算法的计算可在多项式时间内完成。但唯一令人遗憾的问题是算法适用范围是N=3,另外的一些特例只能得到近似的Envy-free解。

以下引用流變日誌的介绍(很详细,就copy一下了)

N=2

假如切的和先选的都是同一位,则另一位一定觉得不公平。所以最好的解决方法是『一个人切蛋糕,另一人先选』,这样第一个人就尽量不会大小眼,而第二个人的选择也不会占到什么便宜。甚至,可以视你特别想挑选草莓或樱桃与否来决定你要切蛋糕还是要先选。关于这种防止对方和自己觉得不公的数学或赛局理论术语,叫做「fairness」。

这种分法不只在蛋糕之上,例如说两人必须共同负担的家务(被称为「chore division」的同质性问题,此时是分越少越好,其分配的方法在多人时就不一样了)、一起分享的权利等等都可以表列,一人区分,另一人先选。于是数学家很自然就会问,如何对3人以上也做同样的分配?结果问题比想像中复杂。

2. N=3

当甲乙丙三个人要分一块蛋糕时,先将状况简化一下,蛋糕是圆形,而且每个人在意的只有蛋糕大小,对装饰不考虑。那么可能的分法有两种。

a.第一种分法,假定让甲执刀,从一条起点的半径绕着蛋糕转,剩下的乙和丙观察,如果其中有一个人(例如丙)觉得已经到1/3时喊停,让甲切下蛋糕当作丙分得的那份。剩下来的状况就和两人分一样了。

这种分法可以推广到n个人的时候,按照常识当然是等分为n份最合理,每个人理想值是1/n。情况有点像竞标,由一个人负责切,其他人先觉得到达1/n时喊停,那一块切下来给他。状况就递减到n-1,如此重复下去,直到两人为止。注意到,在这里表示在还没到1/n前就喊停的人,就亏到了。

这种分法也引出一另个情境,就是假定三人分蛋糕,乙和丙没有订定契约或者暗中勾结,让刀子超过1/3还没停。情况是假定乙和丙勾心斗角,有各自的理性抉择,同时每个人都会嫉妒别人分到比自己多。

而且在分的时候即使正好切三份,往往会有人觉得不公平而嫉妒,例如拿到第一块的人会认为自己所得少于1/3。所以第一种分法无法做到让人人都觉得「自己的选择比别人好」,而自己的选择比别人好的意思是,「自己觉得至少得到1/3」。满足这个条件的分法是较为复杂的「envy-free」问题。

◎前述N=2的分法已经保证不会嫉妒,因为甲自认他等分蛋糕,乙不会得到更好,而乙相信她自己的判断,先选先赢不会输,因此两人都不会嫉妒。

b.底下是三个人的envy-free分法。方法已经有点复杂了。

b-1假定顺序是甲、乙、丙,先由甲分成他认为均等的三份a, b, c。

b-2接着由乙来判断甲的切法。如果乙发现可以接受甲的切法就pass,可以接受的意思是不能有一块独大。乙要认为至少有两块是最大的(另一块较小则没差),三块同样大也行。 (此时a=b=c或a=b>=c)。如果乙发现有一块a最大,则将那一块切一部份t下来当成「剩余」等等再分(a=a’+t),让a’至少和b一样大。那么到时候选蛋糕时,如果乙真的切了一块下来,他就必须拿a’,除非先选的丙抢先一步将a’拿走。

b-3按照丙、乙、甲的顺序挑选蛋糕。丙觉得先选先赢,乙不管有没有多切一块t下来他的选择都是前两名最大者,也OK,而甲自认分均等,也不会拿到被多切的a’ (因为如果有的话,不是被丙先拿去,就是乙要强制接收a’),也OK ,所以三人在不嫉妒的情形下分完蛋糕。此时如果乙曾经切下t,则还需要将t平均分配才算分完。

b-4假设乙拿到a’,则由丙把t分成三等份,按照乙、甲、丙的顺序选蛋糕。乙觉得先选先赢,OK;甲不会嫉妒乙,因为甲认为乙的全部所得小于等于1/3!而甲也不会嫉妒丙,因为甲比丙先选。丙则是认为他三等分的,所以无差。如此就将剩余的t也在envy-free状况下分完了。

◎同样方式不厌其烦详述一遍,其实乙和丙是对称的。假设丙拿到a’,则由乙把t分成三等份,按照丙、甲、乙的顺序选蛋糕。丙觉得先选先赢,OK;甲不会嫉妒丙,因为甲认为丙的全部所得小于等于1/3!而甲也不会嫉妒乙,因为甲比乙先选。乙则是认为他三等分的,所以无差。如此就将剩余的t也在envy-free状况下分完了。

3. N>3

以上N=3的解决方法是由数学家Selfridge和Conway证明出来的,因为是数学证明,所以原本是用数学符号、函数来描述,也有助于推广到大于3的情形。另外N=3还有「双刀解法」,也是相当繁复,概念上解法都是要让每个人推得的不等式优于(>=)其他所有人。

N>3的情形由Steven Brams和Alan Taylor在1992年解决,但是提出的演算法难以执行。后来作者们合写了一本书专门研讨这个「公平分配」的问题,也在2006年又提出了一些更好的方案。这些可以在网站上找到。

所以,要实际上的「公平」(每个人分一样),又要在心理上满足自己比别人更好而「不嫉妒」,据两位作者言(N=2 case)至少可以追溯至《希伯来圣经》,所以我们可以知道数学反映历史的趣味,以及用思考解决问题是需要时间和人力累积的知识问题。

Leave your comment

Required.

Required. Not published.

If you have one.