三個極度嫉妒的人分一個蛋糕，採用什麼策略，能讓三人都覺得公平？

11-25

本題已加入知乎圓桌 ? 日常經濟學 · 博弈人生，更多「博弈論」話題討論歡迎關注

若想知道「先切的人最後選」錯在哪裡，請先看本答案最後補充，確保自己理解問題的難點。
請勿因為配圖，想當然地認為本答案「假設了矩形蛋糕」。本答案中的演算法沒有做這個假設。

====正文====
這是著名的 cake cutting 問題。Fair division
所謂「三人都滿意」，數學上有多種可能的涵義，常用的兩種是：

公平：三人都認為自己的一份不少於 1/3
無怨：三人都不覺得別人拿得比自己多 Envy-free

無怨一定公平，但是公平不一定無怨。
daniel 的答案，上面這兩個條件都不滿足，只會引起自責，不算滿意／公平，是錯的。

兩人的情況很簡單：我切，你選。
三人的情況曾經長時間沒有解，40 年代找到公平程序，80 年代發表無怨程序。
多人的無怨切法還沒有完滿解決。

daniel 的答案是一種「走刀程序 moving-knife procedure」。真正達到「無怨」的走刀程序 見 Stromquist moving-knife procedure，80 年代由 Stromquist 提出。
需要一個裁判，從左向右走刀，三人拿著刀站在裁判右邊，保持在平分右邊蛋糕的位置（按各自標準）。一旦三人中有一個喊「切」，此人獲得裁判左邊的蛋糕。然後三人中位於中間位置的那位（B）把刀切下。沒蛋糕的兩位中，離裁判近的那位獲得中間那塊，遠的那位獲得右邊那塊。
容易證明，三人都認為自己的那份最大。

走刀程序的壞處是連續，假設了兩人同時叫停的概率為零，假設了蛋糕無限可分，現實中不好操作。
一個離散程序是 Selfridge 60 年代由 Selfridge 提出，90 年代由 Conway 獨立提出並發表。

A 按照自己的標準把蛋糕切三塊
如果 B 認為最大的兩塊一樣大，那麼把 C，B，A 的順序選蛋糕，結束。
如果 B 認為其中一塊 M 最大，他就從 M 削去一小塊 R，使之與第二大的那塊一樣大，把 R 放在一邊。
C 先選。如果 C 沒有選 M，那麼 B 必須選 M，否則一切正常，A 拿最後一塊。
B 和 C 中沒拿 M 的那位，把 R 分成三份，讓 B 和 C 中拿了 M 的那位先挑一份，然後 A 選一份，最後一份留給自己。結束。

可以證明，三人都認為自己的那一份最大，證明見維基頁面。

四人無怨分割的走刀程序，1997 年由 Brams, Taylor and Zwicker 提出。多人無怨分割的離散程序，1995 年由 Brams and Taylor 提出，但是需要切的次數可能無上界，因此應該說尚未完滿解決。

以上是「無怨」的切法。「公平」的切法要簡單一些，這裡有一個很通俗的介紹：Mathematics In Europe，波蘭數學家們做了很大貢獻。針對 n 人的一般公平程序如下（Banach and Knaster 提出）：

先排好順序。
第一個人切出他認為的 1/n。
按順序，每個人都判斷一下，這一份是不是太大。是的話就削掉一點並進原來的蛋糕，不是的話跳過。
所有人都判斷過後，這一塊給最後削過蛋糕的那位；如果沒有人削過蛋糕，這塊給第一個人。
重複 2－4，直至最後剩兩人，用我切你選的方式決定。

n=3 的簡化程序由 Steinhaus 在 1943 年提出。@朴三世的答案是 Steinhaus 程序的過簡版本，是錯的。存在的問題是，A 先選，B 第二個選，如果 B 選走的那杯不是 A 認為的最少的，那麼整個過程就不公平了。

====補充====
為何公平不一定無怨？這當然首先是根據數學定義，其表述就已經點明了這個邏輯關係。
而這兩個概念的現實意義，是因為同一塊蛋糕對每個人的價值不同。
比如下面是一個誇張的例子：
假設一個蛋糕，上面有不同的口味，巧克力，奶油，草莓等。參與分蛋糕的人口味不同，因此對不同部分賦予的價值也不同。這裡幾何上簡單的平均分配就不能解決問題，而公平分配也不一定能讓人滿意。這就是這個數學問題要解決的問題。

也是在這個意義上，許多人堅持的「第一個切的最後選」，不論是@王成的五字超簡版，還是@陳啟航的冗餘「嚴謹」版，都是錯誤的，前者甚至沒有一個完整的演算法。第一個切的人會按自己的標準盡量平分，但這不一定是其他兩人的標準，使得另兩人間可能出現不公平的情況。

比如 A-B 切 C-B-A 選的「策略」，以下就是一個不公平的情況：
A 按照尺寸切出自以為的 1/3 和 2/3，但在 BC 看來，因為小的一塊有更多巧克力，所以價值分別是 3/7 和 4/7。此時 B 的最佳策略是切出自以為的 3/7，3/7 和 1/7，C 眼光相同，但在 A 看來分別是 1/3，1/2 和 1/6，其中第二塊尺寸更大，只是巧克力不多。如果按照 C-B-A 的順序選，那麼 A 只可能拿到他眼中的 1/6，和 BC 眼中的 1/7。

很多人看了最高贊的回答表示無法理解其中的邏輯，我在網上上看了相關的英文證明，現在解釋給大家看看，希望能讓你豁然開朗。
先說「Stromquist three-knives procedure」，也就是前面提到的連續無怨分法。

問題為：
怎麼樣讓三個人分蛋糕讓三人都「無怨」既三人都覺得別人沒有自己拿得多。
附加：仍然很多人說「讓一個人切然後叫他最後一個選不就好了嗎，為什麼需要那麼複雜？」如果沒有這種想法可以跳過此段話，有這種想法的請看後面的解釋。問題的關鍵就是這裡的「無怨」指的是主觀的感受，並不是客觀的。也就是說我們覺得3塊是不是一樣大並不重要，必須要他們自己覺得別人的沒有自己的那塊好。舉個例子比如說蛋糕上有草莓有巧克力，A覺得草莓和巧克力都一樣好吃，所以他就平均分成了3份其中一分草莓比巧克力多（但是A並不在乎這一點，因為他覺得都一樣好吃）。接著B先選了一個草莓多的因為他覺得草莓比巧克力好吃，這個時候C就不高興了，因為在他也覺得草莓比巧克力好吃所以在他心中B佔了便宜那麼這就不是一個無怨的分法了。這裡我說蛋糕上有巧克力和草莓實際上是把「主觀」這個意思形象化了，就算蛋糕上什麼都沒有他們三個人依然可以有不同的偏好，依然可以覺得別人分得對自己不利。
再上一次圖：

過程為：

裁判把刀從左到右移動，三個人分別拿自己的刀在右邊從左到右移動，當有人叫」停「的時候裁判和此時正在三位玩家中間的人把刀切下去。一共兩刀，把蛋糕分為三塊。
叫「停」的人獲得裁判左邊的蛋糕，我們定義這塊蛋糕為"L"，這個叫停的人為「S"，沒叫「停」的兩人都為"Q"。
定義在裁判和中間那把刀（圖中的B)之間的蛋糕為M,將它分給刀離裁判最近的那個人。
定義剩下的那塊蛋糕為R（也就是中間那把刀的右邊那塊）分給剩下的那位（也就是離裁判最遠的的那位）

每個人的最佳解如下：
總是把你的刀放在一個你自己認為可以平分右半部分蛋糕的位置（就是裁判的刀右邊）。因此剛開始的時候你的刀是在整個蛋糕中間的，然後隨著裁判的刀移到而移到。
當你覺得左半部分蛋糕和你不叫「停」獲得的蛋糕是一樣的時候就叫「停」。（比如你的刀在最左邊，那麼叫「停」當L=M；如果是在最右邊，那麼叫」停「當L=R；如果你的刀在中間，那麼叫」停「當L=M=R）。

分析過程：
現在我們證明每個人用上述對策獲得的收穫都是無怨的。
我們先說兩個沒叫」停「的人Q, 他們肯定不會互相羨慕，因為自己得到的那一塊蛋糕都包含了自己刀的位置。又因為他們兩都沒有叫，所以在他們心中自己得到那部分肯定比S大，因此他們也不羨慕S。
又說S，剛剛講最佳解的時候已經說過了，他叫停就說明在他眼中L已經等於他不叫停可以獲得的那一部分，而且又大於等於剩下的那一部分，因此他也不會羨慕兩個Q。
因此所有人都獲得了他們自己眼中最大之一或者最大的那份蛋糕，因此所有人都無怨。

順便提一下，用此方法得到的蛋糕是"connected(連接)"的，也就是說如果把整塊蛋糕想像成一個數區間，那麼每人獲得的蛋糕都是一個數區間。然而用下面那個離散解法得到的就有可能是一個「disconnected(斷點)"的蛋糕，也就是玩家最後獲得的蛋糕有可能是一個由幾個區間組成的集合。

現在我們說 Selfridge–Conway discrete procedure
規則：

P1 按照自己的標準把蛋糕切三塊
如果P2認為最大的兩塊一樣大，那麼把 P3，P2，P1 的順序選蛋糕，結束。
如果 P2 認為其中一塊 A 最大，他就從 A 削去一小塊，讓A變成A1和A2（A1為被削的整體，A2為削出的一小塊），使之與第二大的那塊一樣大，把 A2 放在一邊。
P3 先在A1和其它兩塊中作出選擇。
然後P2選，但是如果 P3 沒有選 A1，那麼 P2 必須選 A1，否則P2隨意選擇剩餘兩塊。
P1 拿最後一塊，然後我們開始分A2。
由於(5)號規則，A1肯定被P2或者P3拿了，現在重新定義拿了A1的人為PA,沒拿的為PB，第一位玩家仍然為P1。
(1)PB把A2等分。（2）PA從A2里選一塊，我們叫他A21。（3）P1選剩下兩個小塊，我們叫它A22。 (4)PB把最後一小塊拿走，我們叫它A23。

最後結果為：
PA拿了A1+A21。
PB拿了B+A23。
P1拿了C+A22。
現在證明大家都無怨。以下的」最大「定義都為」此玩家自己認為的最大「。
PA拿了A1+A21, 對於他來說，A1≥B並且A1≥C, 因為：如果是P3拿了A1那麼他肯定覺得A1為最大因為他自己選擇了A1。如果是P2被迫拿了A1那麼他也肯定認為A1為最大，因為他在(3)里讓A1變成了最大的之一。 PA同時也認為A21為A2里的最大一份，因為他最先做出選擇。因此A1+A21≥ B+A23，A1+A21≥ C+A22
PA無怨。

PB拿了B+A23，對於他來說，B≥A1並且B≥C，因為：如果是P3拿了B那麼他肯定覺得B最大因為他最先做出選擇。如果是P2拿了B那麼他也會覺得B最大，因為在(3)他讓B成為了兩個最大的之一。又因為PB是分了A2的人，因此對於他來說，所有的小份都一樣大，既A21=A22=A23。因此因此B+A23≥ A1+A21，B+A23≥C+A22.
PB無怨。

P1拿了C+A22，對於他來說，C≥A1並且C=B，因為他是第一個分蛋糕的人，在他眼中A=B=C（A1因為被切掉了一部分自然比剩下兩塊小）。
也就是說P1肯定覺得PB不比自己拿得多，因為C=B，而A22≥A23（分A2的時候P1在PB前面），因此C+A22≥B+A23。
同時P1也覺得PA不比自己拿得多，因為他覺得A=C，又因為A=A1+A2=A1+(A21+A22+A23)，所以C≥A1+A21（也就是說就算P1不要A22並且PA把A2都拿走了，P1也不會覺得PA比他拿得多）。
P1無怨。

切蛋糕問題在很多資源分配的問題上都有應用，比如說土地的分配，廣告位置的分配，還有播放時段的分配。

參考鏈接：
Stromquist three-knives procedure
Selfridge–Conway_discrete_procedure

把蛋糕均分成六塊，告訴他們蛋糕被切成四塊。當面給每個人一塊，背後單獨給每個人一塊。

這個問題記得好像是有通用模型的：首先隨便選出一個人作為執刀手，方便期間假設蛋糕是長條形的吧，然後執刀手拿著刀從蛋糕的最左端開始，緩緩的向右移。這個期間，N個人裡面任何一個都可以隨時喊「停」，誰喊了以後，這一段的蛋糕就切下來給他，他拿著蛋糕退出。執刀手繼續從最左邊開始，繼續剛才的步驟。
如果某個人到最後也一聲不吭，那麼就認為他放棄了吃蛋糕的權利。
如果某個人喊了，並且得到了蛋糕，那麼他得到的一定是符合他心理預期的。
如果某個人由於貪心，一塊本來已經達到他心理預期的蛋糕被別人喊走了，那麼他也只能怪自己太貪心而不能抱怨執刀手不公平。

a隨意切，將蛋糕切成兩份

b再隨意切，把兩份的其中一份變為兩份

c先挑，a後挑，b拿最後的

大家都非常貪婪

所以a必然會切得極為接近1:2，小的切的大了就是給c切的，小的切的小了，b就會玉石俱焚平分小的，a就虧大了。a自己做的選擇，不會不服。
b看到一大一小的肯定會選擇其一盡量平分，因為自己最後選，不可能讓自己吃虧。如果b認為a分的不錯，b就會平分大的，如果b認為a有意要坑自己，那麼他絕不能是最吃虧的，至少要讓a和自己一樣吃虧，c與他無冤無仇，與他無關。b也是自己做的選擇，不會不服。
c最先選，肯定不會不服。

a和b的博弈非常明白和極端，他們為了避免雙輸，必然盡心盡責，所以這必然是最優解，他們必然沒有理由不滿意，c置身戰場之外，樂得逍遙。

貪婪的人必然是智慧的，不用擔心他們的操作精度。

給他們兩個蛋糕，然後問他們，你們究竟有何功績啊？

誰吃到最大一塊就要付出代價，必須被大家嘿嘿嘿。吃最小的可以先嘿嘿嘿。

不吃虧方案

所謂不吃虧，指每個人都認為自己的蛋糕大於平均數（未必是最多的），佔了一點便宜。

兩個人分蛋糕

AB隨機瓜分蛋糕。
AB將已得蛋糕平均分成2份，AB均從對方的2份蛋糕中挑出所謂最大的那份，此時AB各有2份蛋糕。AB都會認為自己的總份量大於1/2。

三個人分蛋糕

AB隨機瓜分蛋糕。
AB將已得蛋糕平均分成2份，AB均從對方的2份蛋糕中挑出所謂最大的那份，此時AB各有2份蛋糕。AB都會認為自己的總份量大於1/2。
AB將已得蛋糕平均分成3份，C各從AB的3份蛋糕中挑出所謂最大的那份，此時ABC各有2份蛋糕。ABC都會認為自己的總份量大於1/3。

四個人分蛋糕

AB隨機瓜分蛋糕。
AB將已得蛋糕平均分成2份，AB均從對方的2份蛋糕中挑出所謂最大的那份，此時AB各有2份蛋糕。AB都會認為自己的總份量大於1/2。
AB將已得蛋糕平均分成3份，C各從AB的3份蛋糕中挑出所謂最大的那份，此時ABC各有2份蛋糕。ABC都會認為自己的總份量大於1/3。
ABC將已得蛋糕平均分成4份，D各從ABC的4份蛋糕中挑出所謂最大的那份，此時ABCD各獲有3份蛋糕。ABCD都會認為自己的總份量大於1/4。

五個人分蛋糕

AB隨機瓜分蛋糕。
AB將已得蛋糕平均分成2份，AB均從對方的2份蛋糕中挑出所謂最大的那份，此時AB各有2份蛋糕。AB都會認為自己的總份量大於1/2。
AB將已得蛋糕平均分成3份，C各從AB的3份蛋糕中挑出所謂最大的那份，此時ABC各有2份蛋糕。ABC都會認為自己的總份量大於1/3。
ABC將已得蛋糕平均分成4份，D各從ABC的4份蛋糕中挑出所謂最大的那份，此時ABCD各獲有3份蛋糕。ABCD都會認為自己總份量大於1/4。
ABCD將已得蛋糕平均分成5份，E各從ABCD的5份蛋糕中挑出所謂最大的那份，此時ABCDE各有4份蛋糕。ABCDE都會認為自己的總份量大於1/5。

······
······
······
PS：不是無怨方案

當然是一個人切三塊，然後另外兩個人先選啦，當然這兩個人可以用猜拳的方式決定誰先選

已經有人給出了很漂亮的解答@陳浩，不過個人覺得這個問題很有趣，不寫一寫自己的看法總覺得很難受（強迫症沒救了）。
首先個人只是從邏輯推理的角度來思考這個問題，並為這個問題簡化提出四個大前提：
1、三個人都是極度自私，因此不願意看到別人分得比自己多，即要自己的大於等於別人的。
2、三個人都是極度自私，存在報復心理。
3、三個人都足夠聰明並能做足夠充分的邏輯推理。
4、三個人都能準確地切分蛋糕。
同時，先假設了一個可能的操作模式，A切給B，B切給A，C拿剩下的，並且C若不滿意剩下的這塊，則可以和AB中一人交換。這個模式保證C拿到的必然是最大的，AB必然會考慮如何使自己也拿到最大的，由此形成的邏輯循環能夠造成三人平分的結果。具體分析如下。
這個模式只有三步：A切、B切、C選
A切可能存在三種結果：大於三分之一，小於三分之一，等於三分之一
分別分析三種情況。
A大於三分之一給B，B為了拿到最大的，必然切割留給C一塊和自己一樣大的。這樣結果C=B&>A，顯然A不會這麼做。
A小於三分之一給B，B已經無法拿到最大的，由於其損失由A造成，因此B會切一塊更小的給A，A考慮到這一點也不會這麼做。
因此A只能切三分之一給B。
此時，B為了拿到最多的，只能將剩下的三分之二平分給A和C。
結束。

該模式成立。

當然第二條和第四條前提是有待商榷的，不過隨便回答一下，權當做一次腦力運動

先分為三等分，隨機分配給三個人；將三人分別置於能看見彼此但聽不到彼此聲音的三個房間。對每個人都詢問認為哪個的最大，然後關燈，假裝換成了對方的，那就行了……

擲骰子，贏家拿整個蛋糕。
只要保證擲骰子不出千，肯定是夠公平。就是不知道
100-0-0
算不算「分蛋糕」

「拿刀的先砍死一個，剩下的平分」。

買蛋糕的時候看到這個問題，極有回答的慾望。
在我看來，上面排名靠前的答案已經非常完美了，但我還是要參合一刀，我剛才在那磨了好久。
這不是一個純粹的數學問題，也不是純粹的經濟學問題，而是一個現實生活問題，既然是生活上的問題，就來點簡單的解決方案。

他們三人極度自私，他們彼此不信任，所以我們找來了第三方機構，一個切蛋糕師傅，一個切蛋糕指導，一個總監。就叫他們平均切蛋糕團隊吧。
甲方：三個極度自私的人，暫且稱為A，B，C
乙方：平均切蛋糕團隊。
合作目的：乙方負責給甲方提供一項讓三個作風嚴謹的人物可接受的切蛋糕方案，讓這三個人覺得世界公平。
解決方案：
因為蛋糕的切口具有不可逆性，一旦有人不滿意，則任務失敗。所以我們引入製圖的概念，進行理論上的平均分割，在大家都同意後，在設計圖紙上簽字，表達滿意的思想。
首先，切蛋糕的師傅表示從中間切一刀，將蛋糕平均分成兩份，問題來了：

這個問題困擾平均切蛋糕團隊很久，經過小組討論，總監找到了一個辦法，就是通過幾何作圖找出圓的中心，理論上沒有問題，總監曾經在初中的時候學過如何通過尺規找出圓的中心，但是由於操作起來比較麻煩，而且三個自私的人不一定明白為什麼直角三角形斜邊的中心就是圓心，這個方法就被放棄了。

經過總監仔細觀察，突然發現，what is this？

這個秘密被總監發現的時候她差點忘了咽口水，她覺得這個圖形似乎比較好分割，於是把切蛋糕指導叫過來，說，把這個圖形分割成三等分。切蛋糕指導通過幾何學原理，很快就將該圖形平均分成三份。

切蛋糕指導把這個方法拿給切蛋糕師傅的時候切蛋糕師傅傻了，他一看，是這樣的。

總監想，要不把蛋糕橫過來切三份？

但是這次的問題比較辣手，因為她第一次發現原來蛋糕是這樣的：

那些做蛋糕的人實在精明，為何不把蛋糕切好，做成切糕。
就在一籌莫展之時，總監憂傷地想起了前男友，那是一個平安夜的黃昏，男友帶著她買了很多優美的禮物，經過蛋糕店前，一隻萌萌的卡通貓咪蛋糕跳入眼帘，蛋糕師傅戴著口罩優雅地裱花，那一定是世界上最漂亮的食物了，總監這樣想。男友看著她笑了出來，說，嘿，小饞貓，我有點餓了。於是她開心得拉著男友進了蛋糕店。回到賓館，他們坐在巨大的落地窗前，看著這個城市的夜景，切蛋糕。她本想把蛋糕平均分成兩份，但是男友握著她溫柔的小手，把水果和巧克力多的那份切到了她的碟子里，她心裡頓時比蛋糕還甜。
到這裡，總監不忍再想下去，她走到切蛋糕指導那裡，說我有個好主意，於是她在紙上刷刷刷刷刷刷寫了一分鐘，把甲方的三個自私的傢伙叫過來。
總監說，經過我們團隊的一致商討，我們覺得這塊蛋糕讓A來切比較好，但是有個條件，A，你不能握刀，B，你負責持刀，A握住B的手，憑感覺分成三份，切完讓C先選，然後B選，A最後選，如何？
A開始不好意思起來，想，這樣的方法，雖然有點變態，但由我來切，聽起來還蠻公平的，還摸了B的手，好的。
B想，刀在我手裡，反正我肯定不會讓他佔便宜。
C想，反正我先選，隨你們怎麼切。
成交！

為什麼不用秤去稱量呢，保證每人的每份質量都相等就OK了

來，學黨國動遷大法。
在分之前先切一塊藏起來。
然後告訴你，我這是新蛋糕分法。
再告訴你，我這是陽光政策，
接著讓你看著大家分，
可以看到每個人分多少。
下一步制定量化標準，
越多越好，
這一步由精算師來搞，
把人忽悠暈了作為目標。
之後給每個人根據量化標準的蛋糕份額。
最後把偷偷藏起來的另一塊蛋糕切開，
每人分一點點。
剩下的自己吃。

除了沒參與分蛋糕的，
每人都滿意，
連分蛋糕的都滿意。

隨便切，然後抽籤。讓極度自私的人覺得，一切都是命運決定的。

怎麼感覺加個discount factor，這個題可以轉成3 player rubinstein bargaining呀？

Consider 3 player version of rubinstein bargaining, in which agreement of all 3 players is required to end the game. (All players are satisfied with the result). Consider symmetric case where common discount factor in (0,1).

P1 proposes at period 3k, P2 3k+1, and P3 3k+2. As there exists first-mover advanage, order of proposing are drawn randomly, with each player has equal chances to become the first, second or third prosper.

T-period subgame perfect equilibrium converges to stationary subgame perfect equilibrium as T goes to infinity. As discount factor goes to 1 (players are patient enough), the sharing converges to fair share with each participants receive 1/3 and immediate acceptance.

感覺有點cheat了，加了一個repeated game去解釋單期share unit pie的問題，確實算是cheat。

把蛋糕砸了，三個都分不到，就是三個人心理覺得最公平的，哪怕得不到，其他兩個人也得不到。

第一個人畫圖，第二個人下手切，第三個人先挑選