Re: [討論] 公平的分東西法
※ 引述《Raistlinmiao ()》之銘言：
: 我記得以前的小謎語裡面有問到
: 如果兩個人要平分一杯牛奶(假設有杯子 該有的都有 細節忽略)
: 最公平的方法 就是一個人把牛奶分成兩份 第二個人先挑走一份
恕刪
這個問題很好玩
我大學專題課的時候有接觸到類似的問題
首先問題的定義的是
假設我們要分配某個資源，例如pizza
這塊pizza可能是不均勻的
現在如果有n個人想要分這塊pizza
而每個人對這塊pizza都有自己的measure
例如A喜歡青椒，所以如果他得到的pizza上有很多青椒
即使這塊pizza很小，他仍會覺得很滿足
而我們定義每個人對原始整塊pizza的measure為1
如何找到一個切法使得每個人可以滿足他所得到的pizza
在切法上有一些規定
1.pizza是可以無限分割的
2.如果有n個人，則最多只可切n-1刀，每一刀只能將一塊分成2塊
每個人最多只可切一刀
3.當某一個人在切的時候，不可徵求其他人的意見
4.在某些時候(不是切pizza時)，可能必須要徵詢你的看法
你必須誠實問答，如果有欺騙的行為，也只是影響你自己的權益
如果按照以上的規定，可以找到一個演算法
使得每個人得到1/(2n-2)的pizza(按照他自己的measure)
詳細內容在"How to cut a cake almost fairly" 這篇paper有說明
google上應該找的到
另外，如果對這這一方面的問題很有興趣
還可以考慮閱讀這一本書
"Cake-Cutting Algorithms: Be Fair If You Can"
裡面提供了很多有關於資源分配的演算法
在每個人對資源的評斷標準不同時，如果找到一個分配方法
使得大家都滿意。
這書還蠻有趣的，只有一百多頁
這書是我大學時看的，可能有些內容也記不清楚了
現在書也不在我手邊，如果有錯誤的話，還請見諒
詳細演算法的內容，我回頭查明後再與大家分享。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.187.159.29
討論串 (同標題文章)
Inference 近期熱門文章
3
13
PTT遊戲區 即時熱門文章
55
107
13
26