谁偷吃了一块？

这篇文章是几天前写的《分蛋糕是极其复杂的》的扩充，最近实在没空码太多字，本文也只是寥寥而作。
在数学社会学，尤其是博弈论中，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)至少可以追溯至《希伯来圣经》，所以我们可以知道数学反映历史的趣味，以及用思考解决问题是需要时间和人力累积的知识问题。

想把我唱给你听
趁现在年少如花
花儿静静的开
装点你的岁月我的枝桠
谁能够代替你呢
趁年轻尽情的爱吧
最最亲爱的人啊
路途遥远我们在一起吧
我把我唱给你听
把你纯真无邪的笑容给我吧
我们应该有快乐的 幸福的晴朗的时光
我把我唱给你听 用我炙热的感情感动你好吗?
岁月是值得怀念的留念的 害羞的红色脸庞