公平分割问题:均衡分割与免嫉妒分割

    大家或许都知道经典的两人分饼问题——为了实现公平性,只需要一个人切,另一个人选即可。不过,在现实生活中,情况远没有那么理想。如果把大饼换成蛋糕,问题就复杂了很多——你想吃奶油,我想吃巧克力,他想吃水果⋯⋯如果分蛋糕的人对蛋糕各部分的价值看法有分歧,还能实现公平的分割吗?如果分蛋糕的人不止两个呢?

    事实上,对于两个人分蛋糕的情况,经典的“你来分我来选”的方法仍然是非常有效的,即使双方对蛋糕价值的计算方法不一致也没关系。首先,由其中一人执刀,把蛋糕切分成两块;然后,另一个人选出他自己更想要的那块,剩下的那块就留给第一个人。由于分蛋糕的人事先不知道选蛋糕的人会选择哪一块,为了保证自己的利益,他必须(按照自己的标准)把蛋糕分成均等的两块。这样,不管对方选择了哪一块,他都能保证自己总可以得到蛋糕总价值的 1/2 。
    不过,细究起来,这种方法也不是完全公平的。对于分蛋糕的人来说,两块蛋糕的价值均等,但对于选蛋糕的人来说,两块蛋糕的价值差异可能很大。因此,选蛋糕的人往往能获得大于 1/2 的价值。一个简单的例子就是,蛋糕表面是一半草莓一半巧克力的。分蛋糕的人只对蛋糕体积感兴趣,于是把草莓的部分分成一块,把巧克力的部分分成一块;但他不知道,选蛋糕的人更偏爱巧克力一些。因此,选蛋糕的人可以得到的价值超过蛋糕总价值的一半,而分蛋糕的人只能恰好获得一半的价值。而事实上,更公平一些的做法是,前一个人得到所有草莓部分和一小块巧克力部分,后面那个人则分得剩下的巧克力部分。这样便能确保两个人都可以得到一半多一点的价值。
    但是,要想实现上面所说的理想分割,双方需要完全公开自己的信息,并且要能够充分信任对方。然而,在现实生活中,这是很难做到的。考虑到分蛋糕的双方尔虞我诈的可能性,实现绝对公平几乎是不可能完成的任务。因此,我们只能退而求其次,给“公平”下一个大家普遍能接受的定义。在公平分割 (fair division) 问题中,有一个最为根本的公平原则叫做“均衡分割” (proportional division) 。它的意思就是, 如果有 n 个人分蛋糕,则每个人都认为自己得到了整个蛋糕至少 1/n 的价值 。从这个角度来说,“你来分我来选”的方案是公平的——在信息不对称的场合中,获得总价值的一半已经是很让人满意的结果了。


    如果分蛋糕的人更多,均衡分割同样能够实现,而且实现的方法不止一种。其中一种简单的方法就是,每个已经分到蛋糕的人都把自己手中的蛋糕分成更小的等份,让下一个没有分到蛋糕的人来挑选。具体地说,先让其中两个人用“你来分我来选”的方法,把蛋糕分成两块;然后,每个人都把自己手中的蛋糕分成三份,让第三个人从每个人手里各挑出一份来;然后,每个人都把自己手中的蛋糕分成四份,让第四个人从这三个人手中各挑选一份;不断这样继续下去,直到最后一个人选完自己的蛋糕。只要每个人在切蛋糕时能做到均分,无论哪块被挑走,他都不会吃亏;而第 n 个人拿到了每个人手中至少 1/n 的小块,合起来自然也就不会少于蛋糕总价值的 1/n 。虽然这样下来,蛋糕可能会被分得零零碎碎,但这能保证每个人手中的蛋糕在他自己看来都是不小于蛋糕总价值的 1/n 的。
    还有一种思路完全不同的分割方案叫做“最后削减人算法”,它也能做到均衡分割。我们还是把总的人数用字母 n 来表示。首先,第一个人从蛋糕中切出他所认为的 1/n ,然后把这一小块传给第二个人。第二个人可以选择直接把这块蛋糕递交给第三个人,也可以选择从中切除一小块(如果在他看来这块蛋糕比 1/n 大了),再交给第三个人。以此类推,每个人拿到蛋糕后都有一次“修剪”的机会,然后移交给下一个人。规定,最后一个对蛋糕大小进行改动的人将获得这块蛋糕,余下的 n – 1 个人则从头开始重复刚才的流程,分割剩下的蛋糕。每次走完一个流程,都会有一个人拿到了令他满意的蛋糕,下一次重复该流程的人数就会减少一人。不断这样做下去,直到每个人都分到蛋糕为止。
    第一轮流程结束后,拿到蛋糕的人可以保证手中的蛋糕是整个蛋糕价值的 1/n 。而对于每个没有拿到蛋糕的人来说,由于当他把蛋糕传下去之后,他后面的人只能减蛋糕不能加蛋糕,因此在他看来被拿走的那部分蛋糕一定不到 1/n ,剩余的蛋糕对他来说仍然是够分的。在接下来的流程中,类似的道理也同样成立。更为厉害的是,在此游戏规则下,大家会自觉地把手中的蛋糕修剪成自认为的 1/n ,耍赖不会给他带来任何好处。分蛋糕的人绝不敢把蛋糕切得更小,否则得到这块蛋糕的人就有可能是他;而如果他把一块大于 1/n 的蛋糕拱手交给了别人,在他眼里看来,剩下的蛋糕就不够分了,他最终分到的很可能远不及 1/n 。

 
    这样一来,均衡分割问题便完美解决了。不过,正如前面我们说过的,均衡条件仅仅是一个最低的要求。在生活中,人们对“公平”的概念还有很多更不易形式化的理解。如果对公平的要求稍加修改,上述方案的缺陷便暴露了出来。让我们来看这样一种情况:如果 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 世纪数学研究中最重要的问题之一。直到现在,也还有一大群数学家正投身于分蛋糕问题之中,研究包括免嫉妒性在内的各种公平条件,致力于构造新的公平分割方案。

(感谢 0.618 同学的友情帮助)

37 条评论

  • Ernest

    whoa 首次佔到沙發……

  • 0.618

    嗷嗷~

    明明是618老师!哦不,大师!

  • 胖吉胖吉

    好久不见了

  • ww

    表示第三段逻辑混乱 不知所云

  • 白左

    问题就在于每个人的价值体系不一样,而且就算根据价值体系分完,某些情况还可能“反悔”

    假设A只对蛋糕体积感兴趣,B只对草莓感兴趣,C只对巧克力感兴趣
    对于一个有1颗草莓和两块巧克力的蛋糕该如何分配呢?或者对于有N颗草莓和M块巧克力的蛋糕该如何分配呢?
    显然最好的情况下是每个人都拿到自己感兴趣的部分:A拿到了什么都没有的一大块蛋糕,B拿到了所有的草莓,而C拿到了所有的巧克力。但是这种共赢状态显然不是总是成立的

  • biohu

    其中有个分发,N个人平分蛋糕,要把蛋糕总共分成N!块。

  • 喝水小熊

    我记得在《环球科学》的某篇文章中提到,多于3个人的方案也已经有了,只不过非常复杂,不能用很短篇幅说清楚。

  • Izual_Yang

    把整个蛋糕打成浆,按体积均分。——该方法由木津千里同学提供。

  • 枕小路

    呃~~~~我表示看见逻辑就头晕,不过很喜欢那种思维

  • 路人

    第二轮分蛋糕的人,一定是除了A的那个没有选被修剪过的蛋糕的人吗?

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

    这样好像也可以换。

  • wakato

    不知道大家听过“划轨脚”没有?
    假设有n个人。
    首先第1个人分蛋糕。
    接着第2个人对每分蛋糕编号。
    余下n-2个人各在“划轨脚”图上随意划上2笔。
    最后通过“划轨脚”来配对每个人对应的蛋糕编号。
    END

    个人理解关于免嫉妒分割:
    我觉得满足免嫉妒条件的分割不一定满足实物上对每一个人都均衡的条件。
    因为“免嫉妒分割”是基于个人的心理偏好。
    预期满足每个人的心理偏好底线,还不如让他们接受分配结果。

    我觉得“一个人切,另一个人选”其实不是均衡分割,而是免嫉妒分割。
    虽然它看起来最优时候的结果是均衡分割。
    一个人在面对不确定性时,按照自己的偏好来尽量平等地分配。
    另一个人则按自己的偏好来选择其中的份额。
    在整个过程中,双方都没有公开自己的偏好,但他们都接受分配的结果。
    为什么呢?我觉得,他们都认为分配机制对他们来说是机会平等的。

  • wakato

    关于“划轨脚”的说明:
    http://baike.baidu.com/view/2021603.htm

  • wakato

    关于“划轨脚”的说明:
    baike.baidu.com/view/2021603.htm

  • 秋山光和

    其实,如果蛋糕、草莓、巧克力……都是允许无限分割的,那么只要初始分配是“平等”【意为在数量上完全相等】的,那么通过引入交易,就可以达到“公平”
    我们假设有某两个人A,B,草莓s(strawberry),巧克力c;同时假设,引入交易后,草莓的价格为1,巧克力为P
    下面用反证法证明交易后A、B各自消费的s和c(As,Ac)(Bs,Bc)满足非嫉妒性
    不妨设A嫉妒B,意味着A认为UA(Bs,Bc)>UB(As,Ac)
    因为每个理性人的交易价格是一致的。
    这意味着1*Bs+P*Bc>1*As+P*Ac【若不然,As、Ac就不是A在他的约束条件下所能交易得到的最优选择】
    但是,根据最初分配的平等假设,1*Bs+P*Bc必然=1*As+P*Ac【若不然,在这样的价格下的交易必然会导致某一类物品的供给和需求不匹配】
    综上,A不会嫉妒B,交易达到的结果是公平的。

  • 秋山光和

    上面有个地方打错了
    不妨设A嫉妒B,意味着A认为UA(Bs,Bc)>UB(As,Ac)
    这里应该是
    不妨设A嫉妒B,意味着A认为UA(Bs,Bc)>UA(As,Ac)

    U的意思是效用

  • guest007

    这题的确有一对大学教授和研究生研究。 论文一抓一堆。 大家一定要安心阅读,这里有很深的很正规的科学理论体系, 3 人分割不是每个人可以懂得, 4 人分割时就已经让高手眼花乐。

  • guest007

    wiki 有比较好的介绍。

  • 天意

    精彩!

  • kfc

    又看到Conway了…这是一个什么样的神人…

  • Chap

    16楼的,公平交易这个想法我一开始也想到,但是從三个人开始时,交易的次序会產生嫉妒
    舉列:
    A和B都非常喜欢巧克力不喜欢草莓,但C卻非常喜欢草莓
    如果先由A和C交易,A会用所有草莓換C的巧克力
    之後到B,B想和A換巧克力,但A不願意,因此B对A產生嫉妒

  • 秋山光和

    to22L
    点头,你说的很对。这个方案的关键就在于,交换不是一对一的,是整体的。
    考虑一个坐市商,报出每样物品的价格,并接受所有人愿意在这个价格下的购买和售出(目标都是坐市商),如果所有物品在于所有人的购买和售出数量下能够达到出清,那么之前提出的价格就是交易价格,否则坐市商将报出新的价格。【新报价格的原则是:总购买超出0的物品将提高价格,总售出超出0的物品将降低价格】
    瓦尔拉斯均衡可以证明这个价格是存在的。

  • 秋山光和

    比如你的这个例子,假设草莓巧克力价格比是1:1,A和B只要巧克力,C只要草莓

    就相当于A、B、C的初始物品(草莓,巧克力)是(x,x)
    A和B希望的都是(0,2x)【当然,第二项亦即巧克力越多越好,但是x草莓只能交换到x巧克力】
    C希望的是(2x,0)【同上】
    你所说的这种情况就是,A与C达成了交易,分别达到了(0,2x)和(2x,0),但B停留在(x,x)
    我们现在考虑整个市场的需求,AB对巧克力的购买需求是2x,对草莓的售出是2x;而C对草莓的购买需求是x,对巧克力售出是x
    显然对于整个市场而言购买和售出没有出清,所以我们应该提高巧克力的价格【巧克力的总购买为x>0】,降低草莓的价格【草莓的总售出是x>0】
    假设新的价格是草莓:巧克力=1:2,那么x草莓只能交换到0.5x巧克力。
    所以A、B均售出x草莓,得到0.5x巧克力,均达到(0,1.5x)
    而C售出x巧克力,得到2x草莓,达到(3x,0)
    AB不会嫉妒啦,所以之前的“交易次序”带来的问题就是市场没有出清的表现。

  • Chap

    但是这裡还有一个大問題,如果C是很貪婪的人,A和B都不要草莓,只要巧克力,

    最后的平均狀态不是
    A:(0,1.5x) B:(0,1.5x) C:(3x,0)

    而是
    A:(0,x+h) B:(0,x+h) C:(3x,x-2h)
    h为一个很少的数

    为什么?因为这是垄断

  • 秋山光和

    不会垄断……你的意思就是h<0.5x吧?
    这就说明巧克力是多数人(在这里是A和B)都想要的,所以属于稀缺品。自然价格会更高。
    这里不好打字,但是你可以设计一个需求函数自己算一下最优解。

  • Chap

    这裡还有一个風険,市場上你虞我詐,假如A和B知道C很爰草莓,他們一起合作,不買C的草莓,直到草莓的价格下降才购入,情況会不同.
    你所說的是公平市場的Demand Supply.但是直实情況複雜得多

  • 秋山光和

    除非引入外部契约,在这个情况下合作不会是纳什均衡。

  • 秋山光和

    刚才我推算了一下,如果AB对巧克力是完全喜爱,对草莓完全无所谓的话,确实会有草莓价格被压低,但是这并不是垄断的力量,而是AB本身的效用函数所决定的。
    假设ABC各自的效用函数是
    Ua=Cho
    Ub=Cho
    Uc=S^2+0.1Cho
    我们假设三人的初始消费束都为(S,Cho)=(1,1),巧克力作为计价物价格始终为1,如果C将草莓价格压低到一个非常小的ξ(>0),那么AB在交换之后的消费束就是
    (0,1+ξ)
    C的消费束是(3,1-2ξ)【注意1-2ξ<1+ξ,AB不会嫉妒C,C就更不可能嫉妒AB了】
    但是,根据“对巧克力是完全喜爱,对草莓完全无所谓”这一假设,只要交易后草莓数量稍微大于1,对AB就是有利可图的。所以对于AB来说,虽然ξ很小,但是(0,1+ξ)也比(1,1)好!

  • Mimee

    今年在加拿大美国数学夏令营(canada/usa mathcamp)的时候 john conway本人就在 但是分蛋糕问题(there will be cake)却是另一人讲的

    matrix67应该考虑暑假来美国做这个夏令营的讲师(instructor/mentor)或顾问(jc)

  • Ken

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

    个人拙见,我觉得这个反例讲的不好。因为蛋糕是第一个人分的,他分的时候可以预测到之后的发展,所以能够避免第3个人拿到自己非常想要的那部分(比如把那块部分一开始就切成2块)。事实上从后面的Selfridge-Conway 算法也可以看到,分蛋糕和第一个选蛋糕的人是永远不会嫉妒别人的,问题是出在剩下的那个人身上。

    这个反例应该这样讲,对于最后一个人有可能发生这种情形:他想要的蛋糕部分全部在第二个人的手里,而他却被迫必须从第一个和第二个人分别只挑选一个出来。结果就是第二个人手中有2块他所想要部分,而他自己只有1块。嫉妒由此产生。

  • Ken

    我又想了一下,得到了几个有意思的结论。
    对于2个人分蛋糕来说,分蛋糕的人永远只能获得50%的满足,而选蛋糕的人能够获得大于50%的满足。
    而对于3个人分蛋糕的话,如果三个人价值评价各不相同(这是很有可能出现的情况),可以保证每个人都获得大于33.3%的满足。
    从这种意义上来说,3个人分蛋糕反而比2个人分蛋糕更为公平。

    一个可供解决的办法是:A先分蛋糕为2份,B再选择其中的一块分成2份,而A把剩下的一块分成2份,最后让对方选。这样做尽量让两人同时饰演了分蛋糕和选蛋糕的角色。

  • manson

    10 楼说的好!

  • orbea jersey

    en 说的挺有道理的

  • a

    C分蛋糕为三块X、Y、Z,若A和B各自认为最大的一块不同,或A和B认为最小的一块相同,事情都好办。

    若A认为X最大、Y第二大,B认为X最大、Z第二大。那么A把X分为两半让B先挑剩下的给自己,把Y分为两半让C先挑剩下的给自己,则A得到了自己认为较大的两块中的一半,B把Z分为两半让C先挑剩下的给自己,这样B也得到了自己认为较大的两块中的一半,C得到从A、B中挑来的也不会有意见。

  • qirenrui

    to 35L:方案要求不公开信息

  • www.tongbao918.com

    行动是成功的阶梯,行动越多,登得越高。

发表评论