如何把蛋糕分給三個人，使得三個人都不會嫉妒別人_風聞

兩位計算機科學家採用一種新方法把蛋糕分給任意數量的人，而不引起任何人的嫉妒，因而在切蛋糕理論上取得了突破。這個結果不僅僅與生日派對有關:無論是土地資源、播出時間還是石油資源，蛋糕可以代表任何連續的研究對象。從離婚訴訟到政治衝突，切蛋糕理論的靈感來自於各種各樣的問題。

當只有兩個人分蛋糕時，問題就很簡單了。讓第一個人切蛋糕，第二個人選擇他想要的那塊。第一個人會確保他切的蛋糕中的兩個部分他都很滿意。根據喜好和蛋糕上的東西，第一個人可能會把蛋糕切成兩等份，或者切成一塊小一塊大，但小的那塊有草莓。無論第二個人選擇哪一塊，第一個人都不會嫉妒。第二個人可能不喜歡切蛋糕的方式，但是，因為他或她先挑，所以也不會嫉妒第一個人的那塊。一般來説，如果沒有人嫉妒其他人的蛋糕，那麼該分法就稱為無嫉妒分法。

這種針對兩個人的分法早已為人所知，但直到20世紀60年代，數學家約翰·塞爾弗裏奇(John L. Selfridge)才發明了一種適用於三人最優而高效的方法(後來約翰·康韋(John H. Conway)也獨立發現)。1995年，史蒂文·布拉姆斯(Steven J. Brams)和艾倫·泰勒(Alan D. Taylor)提出了一種突破性的方法，適用於任何人，但有一個缺點。即使只有四個人吃蛋糕，公平劃分所需的切割步驟也可能是任意大的。為了找到劃分方法主刀人需要問吃蛋糕的人一些問題——這與劃分方法完成所需的時間有關——可能是任意大的。這個界限究竟有多大取決於參與者的偏好(如果你幸運的話，它們可能很小)，但關鍵是你不能從一開始就限制算法運行的時間和需要進行多少次劃分。這尤其令人失望，因為數學家們確認，對於吃蛋糕的n個人來説，只需要切n-1刀就有一個無嫉妒分法。問題只是在於找到那個分法。

一種變動是允許移動刀：主刀人將刀(或幾把刀)在蛋糕上移動，當吃蛋糕的人認為應該切蛋糕時大喊“停”。至少對於四個吃蛋糕的人來説，這使得切蛋糕的步驟減少到五步。但是吃蛋糕的人要做無數次決定。對於刀在軸上移動的每個點，他們需要決定是否喊停。由於我們真正想要的是一個可以在計算機上運行的離散分步算法，這種移動刀的方法並不完全令人滿意。

由哈里斯·阿齊茲(Haris Aziz)和西蒙·麥肯齊(Simon MacKenzie)設計的這種新方法是離散的，它規定了切蛋糕的數量，以及主刀人需要向吃蛋糕的人提出的問題的數量。無界限方法的合作者Brams對這個結果很滿意：“我相信Azizz - Mackenzie算法是一個重要的理論結果，肯定有所突破，而我們之前用泰勒得到的結果——通過限定算法所需的步長(或切割步驟)——證明了它是有限的，但我們無法確定它的上限。”

這就意味着像蛋糕一樣的衝突可以在一瞬間解決了嗎?不完全是——阿齊茲和麥肯齊的結果純粹是理論上的興趣。當涉及到n個吃蛋糕的人時，你需要問的問題的數量界限如下一個數：n^n^n^n^n^n( ^ 表示次方)

不管吃蛋糕的人喜歡什麼，問題個數超過這個數字後，你都不需要繼續問下去。但這仍然導致了難以想象的過大的界限:即使對於n=2，標準計算器也會崩潰。布拉姆斯説:“無論是否使用移動刀，要縮小這種界限都是一個挑戰。”“然而，我不認為這樣的數字會讓這些算法有任何實用價值。”

還有一個問題。Aziz 和MacKenzie的方法保證了沒有人會嫉妒別人的蛋糕。但這並不能保證每個人都滿意。可能存在另一種蛋糕的劃分，它讓一個或多個吃蛋糕的人更滿意，而且不會讓任何人變得更嫉妒他人——用數學表達就是，無嫉妒法通常不是帕累托最優的。吃蛋糕的人可能會抱怨:他們可能不會嫉妒別人的蛋糕，但如果知道自己可以在其他劃分方法中獲得的更多，他們可能也會很不高興。同時滿足無嫉妒和帕累托最優往往是不可能的。因此，儘管理論家們在努力降低算法的界限，但現實中的實踐者們需要認真思考，在特定的衝突中，哪種劃分是最好的:無嫉妒、帕累托最優，還是其他一些標準。

如何把蛋糕分給三個人，使得三個人都不會嫉妒別人。

假設我們的三個人分別被稱為A、B和C，我們不分性別地把每個人稱為“他”。首先，C把蛋糕切成它認為有相同價值的三塊。然後A和B各自挑選。如果他們選擇兩個不同的部分，這個過程就完成了。

假設A和B想要相同的一塊蛋糕。在這種情況下，B會對它認為最有價值的蛋糕進行一些修剪，以匹配B認為第二有價值的那部分蛋糕。把切下來的餘料放在一邊，讓A先挑。接下來，B選擇他的那塊，但有一個條件，如果A沒有選擇被修剪的那塊，那麼B必須選擇它。最後，C選擇。現在A不嫉妒了，因為它第一個選擇。

B不嫉妒，因為它的第一個選擇是同等價值的:無論A選擇什麼，都有一個同等價值的部分留給B。C也不嫉妒，因為從C的角度來看，唯一降低了價值的部分，是被修減了的那塊，但它會被A或B拿走，而最初的三個部分對它來説是同等價值的。

這樣就剩下餘料那部分了。假設在前一輪中被裁掉的蛋糕被A選中。讓B把餘料分成它認為有同樣價值的三塊。讓A第一個選，C第二個選，B最後選。A不嫉妒，因為它先選。如果C嫉妒，那麼它一定是嫉妒A，因為C在第一輪中是滿意的，第二輪時，它選在B之前，所以它也不嫉妒B。那麼C嫉妒A嗎?

在第一輪中，A選擇了被修剪掉的那塊蛋糕，也就是説，A在第一輪中選擇了對C來説沒有其他兩塊那麼大的蛋糕。我們用V表示在C眼中最初3塊蛋糕的價值。我們把W記為C眼中餘料的價值。現在對C來説總價值是V加上W；而C眼中分配給A的價值是V-W加上部分W顯然，V-W加上部分W的總是小於V，也就是説，C認為，A分配給A自己的價值小於C分配給它的價值，因此C不嫉妒A。

如果是B在第一輪中選擇了被修剪的那塊呢?在這種情況下，只需交換上一段中A和B的角色。