自私演算法

Ⅰ selfish gene 什麼意思

selfish gene
自私基因，（遺傳學方面的）
自體(自我)復制基因
The Selfish Gene自私的基因；BBC自私的基因；自私基因；自公的基果

selfish-gene theory自私基因論
selfish-gene concept自私基因概念
Selfish Gene Algorithm演算法

His first book, The Selfish Gene was an international bestseller.

他的第一本著作《自私的基因》在國際上暢銷不衰。

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

這是著名的 cake cutting 問題。Fair division
所謂「三人都滿意」，數學上有多種可能的涵義，常用的兩種是：
公平：三人都認為自己的一份不少於 1/3

無怨：三人都不覺得別人拿得比自己多 Envy-free

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

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

daniel 的答案是一種「走刀程序 moving-knife procere」。真正達到「無怨」的 走刀程序 見 Stromquist moving-knife procere，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。