从分蛋糕说起

2012-06-04 16:04:00 +0000

网友如下求助:

如何分配总租值为2700的三个房间,使三人都满意。 ####如果是两个人分得话,马上就想到了“小熊分蛋糕”的问题。 两个熊宝宝分一块蛋糕,一个合理的分割方案是:宝宝1切蛋糕,宝宝2选择蛋糕。此方案有一个妙处在于,博弈双方各占优势,又各占劣势,宝宝1切割的优势与选择的劣势的结合使得他必须尽可能降低其切割优势,因为他必须对他的切割劣势埋单,即切割尽可能平均。这样的结果就是:切割方不在具有优势,选择方就也丧失了劣势,因为前者已经放弃了优势(因为他选择尽可能平均分配),使得他的选择的优势也失去了意义。最终的结果是:该分配双方均不占优势,双方均觉得公平。利用这个方案,可以很好的解决两个人分割利益\责任的问题,我们只需使一方为划分者,另一方为选择方就可以了。 显然,这个方案只能局限与两人分割情形。那么对于多人分割又当如何处理呢?


####分蛋糕升级版: 假设熊妈妈给了宝宝们两块味道不同的蛋糕,一个合理的分割方案是: >宝宝1切蛋糕1,宝宝2切蛋糕2,切某一蛋糕的宝宝就会丧失那次切割的选择权,即:宝宝2在选择蛋糕1的部分具有优先权,宝宝1在选择蛋糕2的部分具有优先选择权。如果两个宝宝的口味一致,即蛋糕对他们来说具有相同价值,那么就把问题转化为了两个基本分蛋糕的问题。 如果两个宝宝对蛋糕喜好的口味不一致,那么博弈的结果可能就是宝宝各会分得自己喜爱的完整蛋糕。

此问题可以衍生出一个现实问题:

A,B公同租总价为p两间房子。那么一个合理的分割方案为:A,B分别提供自己的定价方案:假设A对两房子的定价分别为a1,a2(a1+a2=p);同理B对两房子的定价分别为b1,b2.则我们做以下计算:p1=(a1+b1)/2;p2=(a2+b2)/2;此时,两房子的定价即为p1,p2且满足p1+p2=p。那么房子如何分配呢?a1,b1中的大值者来负责p1,a2,b2中的大值者来负责p2.可以证明,该方案是一种很合理的分个方案。


####多个参与者的情形,只需对上述过程拓展,通解: 对n个人分担\负责价值p(分为n个子部分)的问题,解决方案: 第i个人对k部分的估价为:$$x_{ik}$$,其中: 我们对k部分的定价为: 此时,所有部分的总价仍为p:

__分配规则__很SIMPLE:对第k部分出价最高的i拥有该部分的,要对该部分付费。 这里利用了一个博弈心理: >如果你想拥有一个部分K,那么你就要出足量的钱来保证在所有人里出钱最多,这样的事件有两面性:一方面,你会拥有最爱的部分;另一方面,你要付出足量的钱来保证。二者作用的结果就是使参与者投出自己认为合适的钱到合适的部分上,最终的分配结果不会有抱怨不公平方:因为每个参与者都有权力决定分配结果,对结果不满意,只能怪自己。付出越大,收获希望越大,投入产出成正比,所以积极的方案.