七、分蛋糕博弈

1、分蛋糕博弈,討價還價贏博弈,7.1 分蛋糕博弈,有一家外企招聘員工時出了這樣一道面試題：要求應聘者把一盒蛋糕切成八份，分給八個人，但蛋糕盒里還必須留有一份。,而有些應聘者卻感到此題很簡單，把切好的八份蛋糕先拿出七份分給七個人，剩下的一份連蛋糕盒一起分給第八個人就是了。應聘者的創(chuàng)造性思維能力從這道題中就顯而易見了。,7.1 分蛋糕博弈,解析： 我們知道最可能實現(xiàn)一半對一半的公平分配的方案，是讓一方把蛋糕切成兩份，而讓另一方先挑選。,在這種制度設置之下，如果切得不公平，得益的必定是先挑選的一方。所以負責切蛋糕的一方就得把蛋糕切得公平，,7.1 分蛋糕博弈,但是，這個方案極有可能是無法保證公平的。,

2、因為人們?nèi)菀紫胂笄械案獾囊环娇赡芗夹g不老到或不小心切得不一樣大，從而不切蛋糕的一方得到比較大的一半的機會增加。按照這樣的想象，誰都不愿意做切蛋糕的一方。雖然雙方都希望對方切、自己先挑，但是真正僵持的時間不會太長，因為僵持時間的損失很快就會比堅持不切而挑可能得到的好處大。也就是說，僵持的結(jié)果會得不償失，會出現(xiàn)收益縮水的現(xiàn)象。,7.1 分蛋糕博弈,可以想象一下，若你討價還價如何分割的是一個冰激凌蛋糕，在爭吵怎么分配的同時，蛋糕已經(jīng)在那邊慢慢融化了。,因此，我們在生活中經(jīng)常會看到這樣的現(xiàn)象：桌子上放了一個冰激凌蛋糕，小娟向小明提議應該如此這般分配。假如小明同意，他們就會按照成立的契約分享這個蛋糕；假

3、如小明不同意雙方持續(xù)爭執(zhí)，蛋糕將完全融化，誰也得不到。,7.1 分蛋糕博弈,現(xiàn)在，小娟處于一個有力的地位：她使小明面臨有所收獲和一無所獲的選擇。即便她提出自己獨吞整個蛋糕，只讓小明在她吃完之后舔一舔切蛋糕的餐刀，小明的選擇也只能是接受只舔一舔，否則他什么也得不到。在這樣的游戲規(guī)則之下，小明一定不滿足于只能分到1/9的蛋糕，他一定要求再次分配。這種情況下，分蛋糕的博弈就不再是一次性博弈。,7.1 分蛋糕博弈,事實上，對于兩個人分蛋糕的情況，經(jīng)典的“你來分我來選”的方法仍然是非常有效的，即使雙方對蛋糕價值的計算方法不一致也沒關系。,這塊大“蛋糕”如何分配呢？,7.1 分蛋糕博弈,首先，由其中一人執(zhí)

4、刀，把蛋糕切分成兩塊；然后，另一個人選出他自己更想要的那塊，剩下的那塊就留給第一個人。由于分蛋糕的人事先不知道選蛋糕的人會選擇哪一塊，為了保證自己的利益，他必須（按照自己的標準）把蛋糕分成均等的兩塊。這樣，不管對方選擇了哪一塊，他都能保證自己總可以得到蛋糕總價值的 1/2 。,7.1 分蛋糕博弈,在公平分割 (fair division) 問題中，有一個最為根本的公平原則叫做“均衡分割” (proportional division) 。,就是， 如果有 n 個人分蛋糕，則每個人都認為自己得到了整個蛋糕至少 1/n 的價值 。從這個角度來說，“你來分我來選”的方案是公平的在信息不對稱的場合中，

5、獲得總價值的一半已經(jīng)是很讓人滿意的結(jié)果了。,7.1 分蛋糕博弈,如果分蛋糕的人更多，均衡分割同樣能夠?qū)崿F(xiàn)，而且實現(xiàn)的方法不止一種。,其中一種簡單的方法就是，每個已經(jīng)分到蛋糕的人都把自己手中的蛋糕分成更小的等份，讓下一個沒有分到蛋糕的人來挑選。,7.1 分蛋糕博弈,具體地說，先讓其中兩個人用“你來分我來選”的方法，把蛋糕分成兩塊；然后，每個人都把自己手中的蛋糕分成三份，讓第三個人從每個人手里各挑出一份來；然后，每個人都把自己手中的蛋糕分成四份，讓第四個人從這三個人手中各挑選一份；不斷這樣繼續(xù)下去，直到最后一個人選完自己的蛋糕。,只要每個人在切蛋糕時能做到均分，無論哪塊被挑走，他都不會吃虧；而第

6、n 個人拿到了每個人手中至少 1/n 的小塊，合起來自然也就不會少于蛋糕總價值的 1/n 。雖然這樣下來，蛋糕可能會被分得零零碎碎，但這能保證每個人手中的蛋糕在他自己看來都是不小于蛋糕總價值的 1/n 的。,7.1 分蛋糕博弈,還有一種思路完全不同的分割方案叫做“最后削減人算法”，它也能做到均衡分割。,我們還是把總的人數(shù)用字母 n 來表示。首先，第一個人從蛋糕中切出他所認為的 1/n ，然后把這一小塊傳給第二個人。第二個人可以選擇直接把這塊蛋糕遞交給第三個人，也可以選擇從中切除一小塊（如果在他看來這塊蛋糕比 1/n 大了），再交給第三個人。以此類推，每個人拿到蛋糕后都有一次“修剪”的機會，然后

7、移交給下一個人。,7.1 分蛋糕博弈,規(guī)定，最后一個對蛋糕大小進行改動的人將獲得這塊蛋糕，余下的 n - 1 個人則從頭開始重復剛才的流程，分割剩下的蛋糕。每次走完一個流程，都會有一個人拿到了令他滿意的蛋糕，下一次重復該流程的人數(shù)就會減少一人。不斷這樣做下去，直到每個人都分到蛋糕為止。,7.1 分蛋糕博弈,第一輪流程結(jié)束后，拿到蛋糕的人可以保證手中的蛋糕是整個蛋糕價值的 1/n 。而對于每個沒有拿到蛋糕的人來說，由于當他把蛋糕傳下去之后，他后面的人只能減蛋糕不能加蛋糕，因此在他看來被拿走的那部分蛋糕一定不到 1/n ，剩余的蛋糕對他來說仍然是夠分的。,在此游戲規(guī)則下，大家會自覺地把手中的蛋糕修

8、剪成自認為的 1/n ，耍賴不會給他帶來任何好處。,7.1 分蛋糕博弈,分蛋糕的人絕不敢把蛋糕切得更小，否則得到這塊蛋糕的人就有可能是他；而如果他把一塊大于 1/n 的蛋糕拱手交給了別人，在他眼里看來，剩下的蛋糕就不夠分了，他最終分到的很可能遠不及 1/n 。,這樣一來，均衡分割問題便完美解決了。,7.1 分蛋糕博弈,不過，細究起來，這種方法也不是完全公平的。,對于分蛋糕的人來說，兩塊蛋糕的價值均等，但對于選蛋糕的人來說，兩塊蛋糕的價值差異可能很大。因此，選蛋糕的人往往能獲得大于 1/2 的價值。,如個人的喜好、選擇決定了分蛋糕的人的風險。,7.1 分蛋糕博弈,如果 n 個人分完蛋糕后，每個人

9、都自認為自己分得了至少 1/n 的蛋糕，但其中兩個人還是打起來了，可能是什么原因呢？由于不同的人對蛋糕各部分價值的判斷標準不同，因此完全有可能出現(xiàn)這樣的情況雖然自己已經(jīng)分到了至少 1/n 份，但在他看來，有個人手里的蛋糕比他還多。,7.1 分蛋糕博弈,看來，我們平常所說的公平，至少還有一層意思每個人都認為別人的蛋糕都沒我手里的好。,在公平分割理論中，我們把滿足這個條件的分蛋糕方案叫做免嫉妒分割 (envy-free division) 。,7.1 分蛋糕博弈,構造一套免嫉妒的分割方案非常困難。 1960 年， John Selfridge 和 John Conway 各自獨立地分析了人數(shù)為 3

10、 的情況，構造出了第一個滿足免嫉妒條件的三人分割方案。這種分割方案就被稱為“Selfridge-Conway 算法”。,7.1 分蛋糕博弈,首先，A 把蛋糕分成三等份（當然是按照自己的看法來分的，后面提到的切分、選取也都是這樣）。如果 B 認為這三塊蛋糕中較大的兩塊是一樣大的，那么按照 C 、 B 、 A 的順序依次選取蛋糕，問題就解決了。麻煩就麻煩在 B 認為較大的兩塊蛋糕不一樣大的情況。此時，B 就把最大的那塊蛋糕的其中一小部分切下來，讓剩余的部分和第二大的蛋糕一樣大。被切除的部分暫時扔在一旁，在第二輪分割時再來處理。接下來，按照 C 、 B 、 A 的順序依次選蛋糕，但有一個限制：如果

11、C 沒有選那塊被修剪過的蛋糕，B 就必須選它。,7.1 分蛋糕博弈,這樣，三人就各分得了一塊蛋糕。由于 A 是切蛋糕的人，對于他來說拿到哪一塊都一樣，因此 A 不會嫉妒別人。由于 B 選取的是兩個較大塊中的一個，因此 B 也不會嫉妒別人。由于 C 是第一個選蛋糕的，顯然他也不會嫉妒別人。因此，就目前來說，三個人之間是不會有嫉妒發(fā)生的。,但是，還有一小塊被切除的部分沒分完，因此分割流程進入第二輪。,7.1 分蛋糕博弈,在 B 和 C 之間，一定有一個人選擇了那塊被修剪過的蛋糕。不妨把這個人重新記作 X ，另一個人就記作 Y 。讓 Y 把最后那一小塊分成三等份，按照 X 、 A 、 Y 的順序依次

12、挑選蛋糕，結(jié)束第二輪流程。這一輪結(jié)束后，每個人都又得到了一小塊蛋糕。由于 X 是第一個選蛋糕的人， X 顯然不會嫉妒別人；由于 Y 是分蛋糕的人， Y 也不會嫉妒別人。由于 A 比 Y 先選， A 不會嫉妒 Y 。最后，A 也是不會嫉妒 X 的，因為即使 X 擁有了第二輪中的全部蛋糕，X 手里的蛋糕加起來也只是第一輪開始時 A 等分出來的其中一塊蛋糕，這是不可能超過 A 的。這就說明了，三個人之間仍然不會有嫉妒發(fā)生，Selfridge-Conway 算法的確滿足免嫉妒條件。,7.1 分蛋糕博弈,不過，Selfridge-Conway 算法只能在三人分蛋糕時使用，并不能擴展到人數(shù)更多的情況。對于

13、人數(shù)更多的情況，免嫉妒分割問題更加困難，目前數(shù)學家們還沒有找到一個比較可行的方案。正如數(shù)學家 Sol Garfunkel 所說，分蛋糕問題是 20 世紀數(shù)學研究中最重要的問題之一。直到現(xiàn)在，也還有一大群數(shù)學家正投身于分蛋糕問題之中，研究包括免嫉妒性在內(nèi)的各種公平條件，致力于構造新的公平分割方案。,7.1 分蛋糕博弈,但是，要想實現(xiàn)上面所說的理想分割，雙方需要完全公開自己的信息，并且要能夠充分信任對方。,然而，在現(xiàn)實生活中，這是很難做到的。考慮到分蛋糕的雙方爾虞我詐的可能性，實現(xiàn)絕對公平幾乎是不可能完成的任務。,因此，我們只能退而求其次，給“公平”下一個大家普遍能接受的定義。,7.2 分蛋糕博弈

14、的案例,分蛋糕的故事在很多領域都有應用。無論在政壇、商界還是在日常生活中，有關各方經(jīng)常需要通過評判對總收益如何分配，這個總收益其實就是一塊大“蛋糕”。,事實上，當分蛋糕博弈成為一個“動態(tài)博弈”時，就形成一個討價還價博弈的基本模型。在經(jīng)濟生活中，小到日常的商品買賣，大到國際貿(mào)易乃至重大政治談判，都存在著討價還價的問題。,7.2 分蛋糕博弈的案例,例：古時候有個破落貴族的后代甲，窮困得實在沒有辦法過下去，不得不將家中祖?zhèn)鞯墓抛之嬆玫揭粋€大財主乙家去賣。這幅字畫在甲看來至少值200兩銀子，財主乙認為這幅字畫最多只值300兩銀子。,這樣看來，如果順利成交，字畫的成交價格將在200300兩銀子之間。這個

15、交易的過程不妨簡化為這樣：首先由乙開價，甲選擇成交或還價。這個時候，如果乙同意甲的還價，交易順利結(jié)束；如果乙不接受，則交易結(jié)束，買賣沒有做成。這是一個很簡單的兩階段動態(tài)博弈的方案。,7.2 分蛋糕博弈的案例,分蛋糕的談判技巧 ：,用解決動態(tài)博弈問題的倒推法原理來分析這個討價還價的過程。,首先看第二輪也就是最后一輪的博弈，只要甲的還價不超過300兩銀子，乙都會選擇接受還價條件。,回過頭來，我們再來看第一輪的博弈情況，甲拒絕由乙開出的任何低于300兩銀子的價格，這是很明顯的。比如乙開價290兩銀子購買字畫，甲在這一輪同意的話，只能賣得290兩；如果甲不接受這個價格反而在第二輪博弈提高到299兩銀子

16、時，乙仍然會購買此幅字畫。兩項比較，顯然甲會還價。,7.2 分蛋糕博弈的案例,分蛋糕的談判技巧 ：,這個例子中的財主乙先開價，破落貴族甲后還價，結(jié)果賣方甲可以獲得最大收益，這正是一種后出價的后發(fā)優(yōu)勢。這一優(yōu)勢在這個例子中相當是分蛋糕動態(tài)博弈中最后提出條件的人幾乎霸占整塊蛋糕。,事實上，如果財主乙懂得博弈論：他可以改變策略，要么后出價，要么是先出價，但是不允許甲討價還價。如果一次性出價，甲不答應，就堅決不會再繼續(xù)談判，來購買甲的字畫。這個時候，只要乙的出價略高于200兩銀子，甲一定會將字畫賣給乙。因為200兩銀子已經(jīng)超出了甲的心理價位，一旦不成交，那一文錢也拿不到，只能繼續(xù)受凍挨餓。,7.2 分

17、蛋糕博弈的案例,狄更斯的文學名著荒涼山莊就描述了極端的情形：圍繞賈恩迪斯山莊展開的爭執(zhí)變得沒完沒了，以至于最后整個山莊不得不賣掉，用于支付律師們的費用，而爭執(zhí)的雙方由于各不相讓什么也沒有得到。,7.2 分蛋糕博弈的案例,按照同樣的思路，假如不能達成工資協(xié)定就會引發(fā)罷工，那么公司將會失去利潤，工人將會失去工作，也是兩敗俱傷。同樣，假如各國陷入一輪曠日持久的貿(mào)易自由化談判，他們就會在爭吵收益分配的時候賠上貿(mào)易自由化帶來的好處。,7.3 分蛋糕博弈得到的啟示,博弈究竟是什么？通俗地講，博弈論是一種游戲理論。,其準確的定義是：一些個人、團隊或其他組織，面對一定的環(huán)境條件，在一定的規(guī)則約束下，依靠所掌握的信息，同時或先后，一次或多次從各自允許選擇的行為或策略進行選擇并加以實施，并從中各自取得相應結(jié)果或收益的過程。,現(xiàn)代經(jīng)濟學就是建立在博弈論的基礎上的。,7.