分蛋糕如何最公平

1、分蛋糕如何最公平 大家或許都知道經(jīng)典的兩人分餅問題 為了實現(xiàn)公平性，只需要一個人切，另一個人選即可。 不過，在現(xiàn)實生活中，情況遠沒有那么理想。 如果把大餅換成蛋糕，問題就復(fù)雜了很多 你想 吃奶油，我想吃巧克力，他想吃水果 ?如果分蛋糕的人對蛋糕各部分的價值看法有分歧， 還能實 現(xiàn)公平的分割嗎？如果分蛋糕的人不止兩個呢？事實上，對于兩個人分蛋糕的情況，經(jīng)典的 “你來分我來選”的方法仍然是非常有效的，即使 雙方對蛋糕價值的計算方法不一致也沒關(guān)系。 首先，由其中一人執(zhí)刀，把蛋糕切分成兩塊； 然后， 另一個人選出他自己更想要的那塊， 剩下的那塊就留給第一個人。 由于分蛋糕的人事先不知道選 蛋糕的人會選

2、擇哪一塊，為了保證自己的利益，他必須(按照自己的標(biāo)準(zhǔn))把蛋糕分成均等的兩 塊。這樣，不管對方選擇了哪一塊，他都能保證自己總可以得到蛋糕總價值的 1/2 。不過，細究起來，這種方法也不是完全公平的。 對于分蛋糕的人來說， 兩塊蛋糕的價值均等， 但對于選蛋糕的人來說，兩塊蛋糕的價值差異可能很大。因此，選蛋糕的人往往能獲得大于 1/2 的價值。一個簡單的例子就是， 蛋糕表面是一半草莓一半巧克力的。 分蛋糕的人只對蛋糕體積感 興趣，于是把草莓的部分分成一塊，把巧克力的部分分成一塊； 但他不知道，選蛋糕的人更偏愛 巧克力一些。因此，選蛋糕的人可以得到的價值超過蛋糕總價值的一半， 而分蛋糕的人只能恰好 獲

3、得一半的價值。而事實上，更公平一些的做法是， 前一個人得到所有草莓部分和一小塊巧克力 部分，后面那個人則分得剩下的巧克力部分。 這樣便能確保兩個人都可以得到一半多一點的價值。但是，要想實現(xiàn)上面所說的理想分割， 雙方需要完全公開自己的信息， 并且要能夠充分信任 對方。然而，在現(xiàn)實生活中，這是很難做到的。考慮到分蛋糕的雙方爾虞我詐的可能性，實現(xiàn)絕 對公平幾乎是不可能完成的任務(wù)。因此，我們只能退而求其次，給 “公平”下一個大家普遍能接受 的定義。在公平分割 (fair division) 問題中，有一個最為根本的公平原則叫做 “均衡分割” (proportional division) 。它的意思就

4、是， 如果有 n 個人分蛋糕，則每個人都認為自己得到了 整個蛋糕至少 1/n 的價值 。從這個角度來說， “你來分我來選”的方案是公平的 在信息不對 稱的場合中，獲得總價值的一半已經(jīng)是很讓人滿意的結(jié)果了。如果分蛋糕的人更多， 均衡分割同樣能夠?qū)崿F(xiàn)， 而且實現(xiàn)的方法不止一種。 其中一種簡單的 方法就是，每個已經(jīng)分到蛋糕的人都把自己手中的蛋糕分成更小的等份， 讓下一個沒有分到蛋糕 的人來挑選。具體地說，先讓其中兩個人用 “你來分我來選”的方法，把蛋糕分成兩塊；然后，每 個人都把自己手中的蛋糕分成三份， 讓第三個人從每個人手里各挑出一份來； 然后，每個人都把 自己手中的蛋糕分成四份， 讓第四個人從這

5、三個人手中各挑選一份； 不斷這樣繼續(xù)下去， 直到最 后一個人選完自己的蛋糕。 只要每個人在切蛋糕時能做到均分， 無論哪塊被挑走，他都不會吃虧； 而第 n 個人拿到了每個人手中至少 1/n 的小塊，合起來自然也就不會少于蛋糕總價值的 1/n 雖然這樣下來，蛋糕可能會被分得零零碎碎， 但這能保證每個人手中的蛋糕在他自己看來都是不 小于蛋糕總價值的 1/n 的。還有一種思路完全不同的分割方案叫做 “最后削減人算法 ”，它也能做到均衡分割。我們還是 把總的人數(shù)用字母 n 來表示。首先，第一個人從蛋糕中切出他所認為的 1/n ，然后把這一小塊 傳給第二個人。第二個人可以選擇直接把這塊蛋糕遞交給第三個人，

6、 也可以選擇從中切除一小塊 (如果在他看來這塊蛋糕比 1/n 大了)，再交給第三個人。以此類推，每個人拿到蛋糕后都有 一次“修剪 ”的機會，然后移交給下一個人。規(guī)定，最后一個對蛋糕大小進行改動的人將獲得這塊 蛋糕，余下的 n - 1 個人則從頭開始重復(fù)剛才的流程，分割剩下的蛋糕。每次走完一個流程，都 會有一個人拿到了令他滿意的蛋糕，下一次重復(fù)該流程的人數(shù)就會減少一人。不斷這樣做下去， 直到每個人都分到蛋糕為止。第一輪流程結(jié)束后，拿到蛋糕的人可以保證手中的蛋糕是整個蛋糕價值的 1/n 。而對于每 個沒有拿到蛋糕的人來說， 由于當(dāng)他把蛋糕傳下去之后， 他后面的人只能減蛋糕不能加蛋糕， 因 此在他看

7、來被拿走的那部分蛋糕一定不到 1/n ，剩余的蛋糕對他來說仍然是夠分的。在接下來 的流程中，類似的道理也同樣成立。更為厲害的是， 在此游戲規(guī)則下， 大家會自覺地把手中的蛋 糕修剪成自認為的 1/n ，耍賴不會給他帶來任何好處。分蛋糕的人絕不敢把蛋糕切得更小，否 則得到這塊蛋糕的人就有可能是他；而如果他把一塊大于 1/n 的蛋糕拱手交給了別人，在他眼 里看來，剩下的蛋糕就不夠分了，他最終分到的很可能遠不及 1/n 。這樣一來，均衡分割問題便完美解決了。不過，正如前面我們說過的，均衡條件僅僅是一個 最低的要求。在生活中，人們對 “公平 ”的概念還有很多更不易形式化的理解。如果對公平的要求 稍加修改

8、， 上述方案的缺陷便暴露了出來。 讓我們來看這樣一種情況： 如果 n 個人分完蛋糕后， 每個人都自認為自己分得了至少1/n 的蛋糕， 但其中兩個人還是打起來了， 可能是什么原因呢？由于不同的人對蛋糕各部分價值的判斷標(biāo)準(zhǔn)不同， 因此完全有可能出現(xiàn)這樣的情況 雖然自己 已經(jīng)分到了至少 1/n 份，但在他看來，有個人手里的蛋糕比他還多?？磥恚覀兤匠Ｋf的公 平，至少還有一層意思 每個人都認為別人的蛋糕都沒我手里的好。在公平分割理論中， 我們把滿足這個條件的分蛋糕方案叫做免嫉妒分割 (envy-free division) 。免嫉妒分割是一個比均衡分割更強的要求。 如果每個人的蛋糕都沒我多， 那我的

9、蛋糕至少有 1/n ，也就是說滿足免嫉妒條件的分割一定滿足均衡的條件。 但反過來， 滿足均衡條件的分割卻 不一定是免嫉妒的。比方說， A 、 B 、 C 三人分蛋糕，但 A 只在乎蛋糕的體積， B 只關(guān) 心蛋糕上的草莓顆數(shù)， C 只關(guān)心蛋糕上的巧克力塊數(shù)。最后分得的結(jié)果是， A 、 B 、 C 三 人的蛋糕體積相等，但 A 的蛋糕上什么都沒有， B 的蛋糕上有一顆草莓兩塊巧克力， C 的蛋 糕上有兩顆草莓一塊巧克力。因此，每個人從自己的角度來看都獲得了整個蛋糕恰好 1/3 的價 值，但這樣的分法明顯是不科學(xué)的 B 、 C 兩人會互相嫉妒。之前我們介紹的兩種均衡分割方案， 它們都不滿足免嫉妒性。

10、 就拿第一種方案來說吧， 如果 有三個人分蛋糕， 按照規(guī)則， 首先應(yīng)該讓第一人分第二人選， 然后兩人各自把自己的蛋糕切成三 等份，讓第三人從每個人手中各挑一份。這種分法能保證每個人獲得至少 1/3 的蛋糕，但卻可 能出現(xiàn)這樣的情況： 第三個人從第二個人手中挑選的部分， 恰好是第一個人非常想要的。 這樣一 來，第一個人就會覺得第三個人手里的蛋糕更好一些，這種分法就不和諧了。構(gòu)造一套免嫉妒的分割方案非常困難。 1960 年， John Selfridge 和 John Conway 各自 獨立地分析了人數(shù)為 3 的情況，構(gòu)造出了第一個滿足免嫉妒條件的三人分割方案。這種分割方 案就被稱為 “ Sel

11、fridge-Conway 算法 ”。首先， A 把蛋糕分成三等份(當(dāng)然是按照自己的看法來分的，后面提到的切分、選取也都 是這樣)。如果 B 認為這三塊蛋糕中較大的兩塊是一樣大的，那么按照 C 、 B 、 A 的順序 依次選取蛋糕，問題就解決了。麻煩就麻煩在 B 認為較大的兩塊蛋糕不一樣大的情況。此時， B 就把最大的那塊蛋糕的其中一小部分切下來，讓剩余的部分和第二大的蛋糕一樣大。被切除 的部分暫時扔在一旁，在第二輪分割時再來處理。接下來，按照 C 、 B 、 A 的順序依次選 蛋糕，但有一個限制：如果 C 沒有選那塊被修剪過的蛋糕， B 就必須選它。這樣，三人就各分得了一塊蛋糕。由于 A 是

12、切蛋糕的人，對于他來說拿到哪一塊都一樣， 因此 A 不會嫉妒別人。 由于 B 選取的是兩個較大塊中的一個， 因此 B 也不會嫉妒別人。 由于 C 是第一個選蛋糕的，顯然他也不會嫉妒別人。因此，就目前來說，三個人之間是不會有嫉妒 發(fā)生的。但是，還有一小塊被切除的部分沒分完，因此分割流程進入第二輪。在 B 和 C 之間，一定有一個人選擇了那塊被修剪過的蛋糕。不妨把這個人重新記作 X ， 另一個人就記作 Y 。讓 Y 把最后那一小塊分成三等份，按照 X 、 A 、 Y 的順序依次挑選 蛋糕，結(jié)束第二輪流程。這一輪結(jié)束后，每個人都又得到了一小塊蛋糕。由于 X 是第一個選蛋 糕的人， X 顯然不會嫉妒別人； 由于 Y 是分蛋糕的人， Y 也不會嫉妒別人。 由于 A 比 Y 先 選， A 不會嫉妒 Y 。最后， A 也是不會嫉妒 X 的，因為即使 X 擁有了第二輪中的全部蛋糕， X 手里的蛋糕加起來也只是第一輪開始時 A 等分出來的其中一塊蛋糕， 這是不可能超過 A 的。 這就說明了，三個人之間仍然不會有嫉妒發(fā)生， Selfridge-Conway 算法的確滿足免嫉妒條件。不過， Se