(網路上應該可以找得到類似的資訊....沒差, 反正是寫給自己紀念的)
 
假設這裡有一塊蛋糕, 要分給兩個人. 最公平的方法就是, 某甲切成兩份後, 某乙再從中選擇他要的那一份.
這就是 Cut & Choose. 最常用在平分不可數的東西(蛋糕, 勞務...) 時.
某甲的任務是 Cut, 某乙的任務則是 Choose. 這兩個人的任務即使對調, 也可以順利執行.
 
那麼, 當對象有三個人時, 該怎麼實行 Cut & Choose 呢?
首先我們必須先認清問題的預設立場為何. 在這裡有三個預設立場必須注意:
1. 某甲, 某乙, 某丙所被分配到的任務必須可以單獨且順序性 (sequentially) 執行, 不能有兩個人必須同時執行然後導致大打出手的任務.
2. 這是兩人的 Cut & Choose 不會有的問題; 但三人以上就必須考慮 "串通" 的可能性. 不能因其中兩人串通而導致第三人得到不公平的結果.
3. 如上一段說的, 某甲, 某乙, 某丙的任務, 即使對調也要可以順利執行. 所以誰是某甲, 誰是某乙, 誰是某丙, 應由亂數決定. 即使有某兩人 "串通" , 整個過程仍要維持公平.
 
以前曾經花過整整兩天來想這個問題, 結果雖然有想到一個方法, 但卻沒有辦法再衍生應用到四個人以上.
今天突然矛塞頓開, 把整個方法想清楚了. 開懷大笑 也可以應用到 N 個人身上.
 
方法如下: (請用反白字看)
 
Step 1: 某甲切一份給某丙. (某甲認為的 1/3)
Step 2: 某乙 - 確認是否同意這一份給某丙. 如果不同意, 某乙可從這一小份中, 再切小份一點 (某乙認為的 1/3) 給某丙
Step 3: 某丙 - 確認是否願意接受. 如果願意接受, 某丙退場, 問題降為兩人的 Cut & Choose
Step 4: 某乙 - 如果某丙不願接受, 而某乙在 Step 2 有再切過一刀時, 某乙必須無條件接受該份. (某乙收下自己認為的 1/3) 某乙退場.
                       
如果某乙在 Step 2 沒有再切過, 某乙可選擇是否願意接受該份. 如果不接受, 則某甲必須無條件接受該份. (某甲收下自己認為的 1/3) 某甲退場
 
這樣是否能防止串通呢? 答案是可以的.
如果某甲與某乙串通, 則目標是讓某丙的份量減少, 但某丙有權於最後拒絕.
如果某甲與某丙串通, 某乙只要在 Step 2 誠實執行, 最差結果也能拿回自己認定的 1/3
如果某乙與某丙串通, 只要某甲在 Step 1 誠實執行, 某乙與某丙無法在整個過程中獲得讓自己所得變大的機會.
 
那麼, 將這套方法衍生到 N 個人又是如何呢?
Step 1: Mr.1 - Cut 1 piece (1/N) to Mr.N
Step 2: Mr.2 ~ Mr.N-1 - Review the piece sequentially to fit everybody's recognition of 1/N
Step 3: Mr.N - Decide to accept the piece or not.
Step 4: Mr.N-1 ~ Mr.1 - Accept the piece if he once cut it; or decide to accept the piece or not if he hasn't cut it.
Step 5: Once anyone takes the piece, the problem complexity is reduced by 1.
This method can even be applied on (N=2) case.
 
 
最後, 當然 Cut & Choose 不是萬能的, 先不說蛋糕被切個稀巴爛 (吐舌頭), 只要每一等份的價值因人而異時, Cut & Choose 雖然能保證人人都能接受, 但並不能保證總滿意度是最高的.
人類還是要常用 "溝通" 的工具才是.
創作者介紹

Claudia's Present

Claudia Ko 發表在 痞客邦 PIXNET 留言(0) 人氣()