博弈培训讲座PPT分蛋糕博弈.ppt

分蛋糕博弈,讨价还价赢博弈,7.1 分蛋糕博弈,有一家外企招聘员工时出了这样一道面试题：要求应聘者把一盒蛋糕切成八份，分给八个人，但蛋糕盒里还必须留有一份。,而有些应聘者却感到此题很简单，把切好的八份蛋糕先拿出七份分给七个人，剩下的一份连蛋糕盒一起分给第八个人就是了。应聘者的创造性思维能力从这道题中就显而易见了。,7.1 分蛋糕博弈,解析：我们知道最可能实现一半对一半的公平分配的方案，是让一方把蛋糕切成两份，而让另一方先挑选。,在这种制度设置之下，如果切得不公平，得益的必定是先挑选的一方。所以负责切蛋糕的一方就得把蛋糕切得公平，,7.1 分蛋糕博弈,但是，这个方案极有可能是无法保证公平的。,因为人们容易想象切蛋糕的一方可能技术不老到或不小心切得不一样大，从而不切蛋糕的一方得到比较大的一半的机会增加。按照这样的想象，谁都不愿意做切蛋糕的一方。虽然双方都希望对方切、自己先挑，但是真正僵持的时间不会太长，因为僵持时间的损失很快就会比坚持不切而挑可能得到的好处大。也就是说，僵持的结果会得不偿失，会出现收益缩水的现象。,7.1 分蛋糕博弈,可以想象一下，若你讨价还价如何分割的是一个冰激凌蛋糕，在争吵怎么分配的同时，蛋糕已经在那边慢慢融化了。,因此，我们在生活中经常会看到这样的现象：桌子上放了一个冰激凌蛋糕，小娟向小明提议应该如此这般分配。假如小明同意，他们就会按照成立的契约分享这个蛋糕；假如小明不同意双方持续争执，蛋糕将完全融化，谁也得不到。,7.1 分蛋糕博弈,现在，小娟处于一个有力的地位：她使小明面临有所收获和一无所获的选择。即便她提出自己独吞整个蛋糕，只让小明在她吃完之后舔一舔切蛋糕的餐刀，小明的选择也只能是接受只舔一舔，否则他什么也得不到。在这样的游戏规则之下，小明一定不满足于只能分到1/9的蛋糕，他一定要求再次分配。这种情况下，分蛋糕的博弈就不再是一次性博弈。,7.1 分蛋糕博弈,事实上，对于两个人分蛋糕的情况，经典的“你来分我来选”的方法仍然是非常有效的，即使双方对蛋糕价值的计算方法不一致也没关系。,这块大“蛋糕”如何分配呢？,7.1 分蛋糕博弈,首先，由其中一人执刀，把蛋糕切分成两块；然后，另一个人选出他自己更想要的那块，剩下的那块就留给第一个人。由于分蛋糕的人事先不知道选蛋糕的人会选择哪一块，为了保证自己的利益，他必须（按照自己的标准）把蛋糕分成均等的两块。这样，不管对方选择了哪一块，他都能保证自己总可以得到蛋糕总价值的 1/2。,7.1 分蛋糕博弈,在公平分割(fair division)问题中，有一个最为根本的公平原则叫做“均衡分割”(proportional division)。,就是，如果有 n 个人分蛋糕，则每个人都认为自己得到了整个蛋糕至少 1/n 的价值。从这个角度来说，“你来分我来选”的方案是公平的在信息不对称的场合中，获得总价值的一半已经是很让人满意的结果了。,7.1 分蛋糕博弈,如果分蛋糕的人更多，均衡分割同样能够实现，而且实现的方法不止一种。,其中一种简单的方法就是，每个已经分到蛋糕的人都把自己手中的蛋糕分成更小的等份，让下一个没有分到蛋糕的人来挑选。,7.1 分蛋糕博弈,具体地说，先让其中两个人用“你来分我来选”的方法，把蛋糕分成两块；然后，每个人都把自己手中的蛋糕分成三份，让第三个人从每个人手里各挑出一份来；然后，每个人都把自己手中的蛋糕分成四份，让第四个人从这三个人手中各挑选一份；不断这样继续下去，直到最后一个人选完自己的蛋糕。,只要每个人在切蛋糕时能做到均分，无论哪块被挑走，他都不会吃亏；而第 n 个人拿到了每个人手中至少 1/n 的小块，合起来自然也就不会少于蛋糕总价值的 1/n。虽然这样下来，蛋糕可能会被分得零零碎碎，但这能保证每个人手中的蛋糕在他自己看来都是不小于蛋糕总价值的 1/n 的。,7.1 分蛋糕博弈,还有一种思路完全不同的分割方案叫做“最后削减人算法”，它也能做到均衡分割。,我们还是把总的人数用字母 n 来表示。首先，第一个人从蛋糕中切出他所认为的 1/n，然后把这一小块传给第二个人。第二个人可以选择直接把这块蛋糕递交给第三个人，也可以选择从中切除一小块（如果在他看来这块蛋糕比 1/n 大了），再交给第三个人。以此类推，每个人拿到蛋糕后都有一次“修剪”的机会，然后移交给下一个人。,7.1 分蛋糕博弈,规定，最后一个对蛋糕大小进行改动的人将获得这块蛋糕，余下的 n-1 个人则从头开始重复刚才的流程，分割剩下的蛋糕。每次走完一个流程，都会有一个人拿到了令他满意的蛋糕，下一次重复该流程的人数就会减少一人。不断这样做下去，直到每个人都分到蛋糕为止。,7.1 分蛋糕博弈,第一轮流程结束后，拿到蛋糕的人可以保证手中的蛋糕是整个蛋糕价值的 1/n。而对于每个没有拿到蛋糕的人来说，由于当他把蛋糕传下去之后，他后面的人只能减蛋糕不能加蛋糕，因此在他看来被拿走的那部分蛋糕一定不到 1/n，剩余的蛋糕对他来说仍然是够分的。,在此游戏规则下，大家会自觉地把手中的蛋糕修剪成自认为的 1/n，耍赖不会给他带来任何好处。,7.1 分蛋糕博弈,分蛋糕的人绝不敢把蛋糕切得更小，否则得到这块蛋糕的人就有可能是他；而如果他把一块大于 1/n 的蛋糕拱手交给了别人，在他眼里看来，剩下的蛋糕就不够分了，他最终分到的很可能远不及 1/n。,这样一来，均衡分割问题便完美解决了。,7.1 分蛋糕博弈,不过，细究起来，这种方法也不是完全公平的。,对于分蛋糕的人来说，两块蛋糕的价值均等，但对于选蛋糕的人来说，两块蛋糕的价值差异可能很大。因此，选蛋糕的人往往能获得大于 1/2 的价值。,如个人的喜好、选择决定了分蛋糕的人的风险。,7.1 分蛋糕博弈,如果 n 个人分完蛋糕后，每个人都自认为自己分得了至少 1/n 的蛋糕，但其中两个人还是打起来了，可能是什么原因呢？由于不同的人对蛋糕各部分价值的判断标准不同，因此完全有可能出现这样的情况虽然自己已经分到了至少 1/n 份，但在他看来，有个人手里的蛋糕比他还多。,7.1 分蛋糕博弈,看来，我们平常所说的公平，至少还有一层意思每个人都认为别人的蛋糕都没我手里的好。,在公平分割理论中，我们把满足这个条件的分蛋糕方案叫做免嫉妒分割(envy-free division)。,7.1 分蛋糕博弈,构造一套免嫉妒的分割方案非常困难。1960 年，John Selfridge 和 John Conway 各自独立地分析了人数为 3 的情况，构造出了第一个满足免嫉妒条件的三人分割方案。这种分割方案就被称为“Selfridge-Conway 算法”。,7.1 分蛋糕博弈,首先，A 把蛋糕分成三等份（当然是按照自己的看法来分的，后面提到的切分、选取也都是这样）。如果 B 认为这三块蛋糕中较大的两块是一样大的，那么按照 C、B、A 的顺序依次选取蛋糕，问题就解决了。麻烦就麻烦在 B 认为较大的两块蛋糕不一样大的情况。此时，B 就把最大的那块蛋糕的其中一小部分切下来，让剩余的部分和第二大的蛋糕一样大。被切除的部分暂时扔在一旁，在第二轮分割时再来处理。接下来，按照 C、B、A 的顺序依次选蛋糕，但有一个限制：如果 C 没有选那块被修剪过的蛋糕，B 就必须选它。,7.1 分蛋糕博弈,这样，三人就各分得了一块蛋糕。由于 A 是切蛋糕的人，对于他来说拿到哪一块都一样，因此 A 不会嫉妒别人。由于 B 选取的是两个较大块中的一个，因此 B 也不会嫉妒别人。由于 C 是第一个选蛋糕的，显然他也不会嫉妒别人。因此，就目前来说，三个人之间是不会有嫉妒发生的。,但是，还有一小块被切除的部分没分完，因此分割流程进入第二轮。,7.1 分蛋糕博弈,在 B 和 C 之间，一定有一个人选择了那块被修剪过的蛋糕。不妨把这个人重新记作 X，另一个人就记作 Y。让 Y 把最后那一小块分成三等份，按照 X、A、Y 的顺序依次挑选蛋糕，结束第二轮流程。这一轮结束后，每个人都又得到了一小块蛋糕。由于 X 是第一个选蛋糕的人，X 显然不会嫉妒别人；由于 Y 是分蛋糕的人，Y 也不会嫉妒别人。由于 A 比 Y 先选，A 不会嫉妒 Y。最后，A 也是不会嫉妒 X 的，因为即使 X 拥有了第二轮中的全部蛋糕，X 手里的蛋糕加起来也只是第一轮开始时 A 等分出来的其中一块蛋糕，这是不可能超过 A 的。这就说明了，三个人之间仍然不会有嫉妒发生，Selfridge-Conway 算法的确满足免嫉妒条件。,7.1 分蛋糕博弈,不过，Selfridge-Conway 算法只能在三人分蛋糕时使用，并不能扩展到人数更多的情况。对于人数更多的情况，免嫉妒分割问题更加困难，目前数学家们还没有找到一个比较可行的方案。正如数学家 Sol Garfunkel 所说，分蛋糕问题是 20 世纪数学研究中最重要的问题之一。直到现在，也还有一大群数学家正投身于分蛋糕问题之中，研究包括免嫉妒性在内的各种公平条件，致力于构造新的公平分割方案。,7.1 分蛋糕博弈,但是，要想实现上面所说的理想分割，双方需要完全公开自己的信息，并且要能够充分信任对方。,然而，在现实生活中，这是很难做到的。考虑到分蛋糕的双方尔虞我诈的可能性，实现绝对公平几乎是不可能完成的任务。,因此，我们只能退而求其次，给“公平”下一个大家普遍能接受的定义。,7.2 分蛋糕博弈的案例,分蛋糕的故事在很多领域都有应用。无论在政坛、商界还是在日常生活中，有关各方经常需要通过评判对总收益如何分配，这个总收益其实就是一块大“蛋糕”。,事实上，当分蛋糕博弈成为一个“动态博弈”时，就形成一个讨价还价博弈的基本模型。在经济生活中，小到日常的商品买卖，大到国际贸易乃至重大政治谈判，都存在着讨价还价的问题。,7.2 分蛋糕博弈的案例,例：古时候有个破落贵族的后代甲，穷困得实在没有办法过下去，不得不将家中祖传的古字画拿到一个大财主乙家去卖。这幅字画在甲看来至少值200两银子，财主乙认为这幅字画最多只值300两银子。,这样看来，如果顺利成交，字画的成交价格将在200300两银子之间。这个交易的过程不妨简化为这样：首先由乙开价，甲选择成交或还价。这个时候，如果乙同意甲的还价，交易顺利结束；如果乙不接受，则交易结束，买卖没有做成。这是一个很简单的两阶段动态博弈的方案。,7.2 分蛋糕博弈的案例,分蛋糕的谈判技巧：,用解决动态博弈问题的倒推法原理来分析这个讨价还价的过程。,首先看第二轮也就是最后一轮的博弈，只要甲的还价不超过300两银子，乙都会选择接受还价条件。,回过头来，我们再来看第一轮的博弈情况，甲拒绝由乙开出的任何低于300两银子的价格，这是很明显的。比如乙开价290两银子购买字画，甲在这一轮同意的话，只能卖得290两；如果甲不接受这个价格反而在第二轮博弈提高到299两银子时，乙仍然会购买此幅字画。两项比较，显然甲会还价。,7.2 分蛋糕博弈的案例,分蛋糕的谈判技巧：,这个例子中的财主乙先开价，破落贵族甲后还价，结果卖方甲可以获得最大收益，这正是一种后出价的后发优势。这一优势在这个例子中相当是分蛋糕动态博弈中最后提出条件的人几乎霸占整块蛋糕。,事实上，如果财主乙懂得博弈论：他可以改变策略，要么后出价，要么是先出价，但是不允许甲讨价还价。如果一次性出价，甲不答应，就坚决不会再继续谈判，来购买甲的字画。这个时候，只要乙的出价略高于200两银子，甲一定会将字画卖给乙。因为200两银子已经超出了甲的心理价位，一旦不成交，那一文钱也拿不到，只能继续受冻挨饿。,7.2 分蛋糕博弈的案例,狄更斯的文学名著荒凉山庄就描述了极端的情形：围绕贾恩迪斯山庄展开的争执变得没完没了，以至于最后整个山庄不得不卖掉，用于支付律师们的费用，而争执的双方由于各不相让什么也没有得到。,7.2 分蛋糕博弈的案例,按照同样的思路，假如不能达成工资协定就会引发罢工，那么公司将会失去利润，工人将会失去工作，也是两败俱伤。同样，假如各国陷入一轮旷日持久的贸易自由化谈判，他们就会在争吵收益分配的时候赔上贸易自由化带来的好处。,7.3 分蛋糕博弈得到的启示,博弈究竟是什么？通俗地讲，博弈论是一种游戏理论。,其准确的定义是：一些个人、团队或其他组织，面对一定的环境条件，在一定的规则约束下，依靠所掌握的信息，同时或先后，一次或多次从各自允许选择的行为或策略进行选择并加以实施，并从中各自取得相应结果或收益的过程。,现代经济学就是建立在博弈论的基础上的。,7.3 分蛋糕博弈得到的启示,在博弈理论中已经证明出，当谈判的多阶段博弈是单数阶段时，先开价者具有先发优势；它是双数阶段时，后开价者具有后发优势。,7.3 分蛋糕博弈得到的启示,谈判博弈的一个重要因素在于时间就是金钱，假如谈判越拉越长，谈判的对象-分割的蛋糕就会开始缩水。不过，这时各方仍然可能不愿意妥协，暗自希望只要谈成一个对自己更加有利的结果，那么好处将超过谈判的代价。,7.3 分蛋糕博弈得到的启示,谈判是一种像跳舞一样的艺术，参与谈判的谈判者应该尽量缩短谈判的过程，尽快达成一项协议，以便减少耗费的成本，从而避免损失，维护各自的最大利益。,