大家好，我是大老李。 今天這期節(jié)目是我之前節(jié)目的后續(xù)。我很早前做過(guò)一期節(jié)目叫“三人分蛋糕”問(wèn)題，就是如何分蛋糕給三個(gè)人，最為公平合理。我用了“三個(gè)和尚分蛋糕”的故事說(shuō)明了這個(gè)流程，這個(gè)故事我也引入到了我不久前出版的新書(shū)“老師沒(méi)教的數(shù)學(xué)”中。

而其中也提到了，數(shù)學(xué)家還沒(méi)有找到確切的4人或以上的分蛋糕方法。而前幾天我在美國(guó)計(jì)算機(jī)協(xié)會(huì)會(huì)網(wǎng)站上看到一條新聞：有界且無(wú)妒忌的分蛋糕算法（A Bounded and Envy-Free Cake Cutting Algorithm）。

我趕緊看了下這條新聞，原來(lái)澳大利亞新南威爾士大學(xué)的兩位研究者早在2016年8月就提交了一篇論文（最新修改是2017年）。稱(chēng)找到了對(duì)任意人數(shù)的有限步驟的無(wú)妒忌分蛋糕方法。我研究了一下這篇論文，看到這方法的思路非常有意思，這里介紹給大家。

先簡(jiǎn)單復(fù)習(xí)一下，什么是“分蛋糕問(wèn)題”。這里所說(shuō)的“分蛋糕問(wèn)題”是指：用離散的步驟，在有限的步驟內(nèi)，完成對(duì)一個(gè)蛋糕分割，分配給若干個(gè)分蛋糕的人。成功分配的標(biāo)準(zhǔn)中，最重要的一條，叫無(wú)妒忌，即任何人都認(rèn)為自己得到的蛋糕，多于或等于其他人的，這叫無(wú)妒忌。

這其中還有一些假設(shè)：每個(gè)人都是誠(chéng)實(shí)，穩(wěn)定的，對(duì)同樣的兩塊蛋糕的好壞判斷是不變的。且每個(gè)人對(duì)蛋糕的價(jià)值判斷是有傳遞性的，也就是當(dāng)你認(rèn)為A塊蛋糕比B好，B比C好，那么你會(huì)認(rèn)為A比C好。另外，我們也假定每個(gè)人不介意自己得到的蛋糕是好多個(gè)小塊，也允許兩片蛋糕無(wú)縫的合并成較大的一塊。 當(dāng)對(duì)蛋糕A切掉一塊時(shí)，總是認(rèn)為A的價(jià)值大于等于切掉后的；當(dāng)對(duì)蛋糕A增加一點(diǎn)時(shí)，總是認(rèn)為A的價(jià)值小于等于增加后的。以上都是必要的，但合理的一些假定。

還有，我們今天只討論使用離散的切割步驟的方法，“走刀法”不在考慮范圍內(nèi)。

基于以上的假定和分蛋糕目標(biāo)，對(duì)2個(gè)人來(lái)分，有一個(gè)大家熟知的分割方法，即某人先把蛋糕分成他認(rèn)為公平的兩塊，然后讓另一個(gè)人先挑，雙方肯定都不會(huì)覺(jué)得吃虧。

3人的情況，有一個(gè)名為“Selfrige-Conway流程”，可以達(dá)到無(wú)妒忌分割的目的。

而對(duì)4人或以上，一直沒(méi)有一個(gè)確切的流程。我之前節(jié)目播出后，有不少聽(tīng)眾給我發(fā)來(lái)了他們?cè)O(shè)計(jì)的4人分蛋糕流程，但這些流程最終都一個(gè)缺陷：沒(méi)有達(dá)到無(wú)妒忌的目的。比如很多人提出了這個(gè)流程：

假設(shè)是甲乙丙丁四人分蛋糕，甲先把蛋糕分成他認(rèn)為公平的2塊。然后讓乙、丙、丁評(píng)價(jià)哪一塊更好。如果恰好是乙認(rèn)為A塊蛋糕好，而丙和丁認(rèn)為B塊蛋糕好。那么就讓甲、乙去分A塊，丙、丁去分bB。而兩個(gè)人分一塊蛋糕的流程是我們已經(jīng)知道的。

以上流程的缺陷就在于，雖然甲、乙之間，丙、丁之間不會(huì)有妒忌。但是兩組人之間還是有可能產(chǎn)生妒忌。甲、乙可能會(huì)想：“丙怎么能拿到那么大一塊呢？丁，你切的蛋糕也太不均勻了吧！” 等等。總之，把一個(gè)大的問(wèn)題分解成兩個(gè)小問(wèn)題的思路是好的，但是要時(shí)刻防止妒忌的產(chǎn)生，這是很困難的。

那我們看看這次兩位澳大利亞研究者提出的流程。這個(gè)流程相當(dāng)復(fù)雜，原版論文有30多頁(yè)，我盡量把流程框架說(shuō)清楚。這兩位研究者把整個(gè)流程稱(chēng)為“主要協(xié)議” （main protocal），而主要協(xié)議又包含三個(gè)子協(xié)議，稱(chēng)為“核心協(xié)議”（core protocal），“分歧協(xié)議” (discrepency protocal)和”退出協(xié)議”(GoLeft protocal)。

核心協(xié)議是整了協(xié)議的主體，也是整個(gè)流程中最為主要和執(zhí)行次數(shù)最多的協(xié)議。核心協(xié)議的目的在于盡可能將更多的蛋糕封掉，但是在分的過(guò)程中，時(shí)刻保持無(wú)妒忌。這個(gè)流程大致是這樣，我以甲、乙、丙、丁四玩家分蛋糕為例：

1. 讓甲把蛋糕分成他認(rèn)為公平的4塊

2. 把四塊中的第一塊給甲

3. 把第二塊給乙。并且讓乙評(píng)價(jià)第三和第四塊。如果他認(rèn)為第三和第四塊中有哪塊比他得到的好，就請(qǐng)他從第三和第四塊中切下一點(diǎn)，使得這兩塊與他拿到的那塊一樣好。

4. 把第三塊給丙。并且讓丙評(píng)價(jià)第四塊。如果他認(rèn)為第四塊中比他得到的好，就請(qǐng)他從第四塊中切下一點(diǎn)，使得它們一樣好。

5. 接下來(lái)丁就拿剩下的一塊。

6. 此時(shí)進(jìn)行評(píng)估，所有四個(gè)玩家就手上拿到的蛋糕評(píng)估是否有“妒忌”，即否有任何人得到的比自己手上的好。

根據(jù)以上流程，我們可以確信甲不會(huì)妒忌，而其他人可能會(huì)對(duì)比他們更早得到蛋糕的人產(chǎn)生妒忌。

無(wú)論如何，如果此時(shí)沒(méi)有妒忌那是最好，這樣就完成了一次核心協(xié)議。如果有妒忌，則調(diào)整執(zhí)行順序，將所有蛋糕還原，再次進(jìn)行核心協(xié)議。

這里調(diào)整執(zhí)行順序有兩種調(diào)整策略，一種是調(diào)整蛋糕分配的順序。切蛋糕的人不變，之前是甲拿第一塊，可以改成甲拿第二塊，乙拿第一塊等等。這是一種調(diào)整策略。

還有另一個(gè)拿蛋糕的順序，之前是甲第一個(gè)拿，可以改成乙第一個(gè)拿，甲第二，丙第三等等。這是第二種調(diào)整策略。

算法中，要求枚舉所有可能的蛋糕分配順序和選蛋糕的順次，所以有兩重循環(huán)。而論文中證明了，枚舉了這兩輪循環(huán)后，其中至少有一次可以產(chǎn)生無(wú)妒忌的分配。

可以看得出 ，這是一個(gè)非常冗長(zhǎng)的步驟，最多可能要執(zhí)行(4!)^2*4次循環(huán)，才能得到一次分配結(jié)果。但好處在于，至少部分蛋糕被分配掉了，而且論文證明，每一次至少有的蛋糕被分配掉(n-2)/n了，其中n是人數(shù)。對(duì)四人來(lái)說(shuō)，每次可以分掉至少一半蛋糕。

而我們還可以繼續(xù)執(zhí)行核心流程，但是換其他人來(lái)切蛋糕。乙、丙、丁玩家都當(dāng)一次切蛋糕的，執(zhí)行一次核心流程。當(dāng)所有玩家都做了一次切蛋糕者，并執(zhí)行核心流程后，論文證明每個(gè)人都會(huì)認(rèn)為剩下的蛋糕小于等于自己已得蛋糕的一半。

而這個(gè)流程可以推廣到n個(gè)玩家，且最終每個(gè)玩家都會(huì)認(rèn)為剩下的蛋糕價(jià)值至多是自己已得蛋糕的（n-2)/n。

以上就是關(guān)于核心流程的介紹，核心協(xié)議已經(jīng)非常冗余，但也沒(méi)辦法，因?yàn)槲覀円_保蛋糕的分配不發(fā)生妒忌。

執(zhí)行完核心協(xié)議后，總是會(huì)剩下些蛋糕。當(dāng)然可以對(duì)剩下的蛋糕繼續(xù)執(zhí)行核心協(xié)議，但是這樣會(huì)沒(méi)完沒(méi)了。所以我們要有點(diǎn)其他方法，使得能在有限步驟分配完全部蛋糕。

而論文思路就是設(shè)法將分配剩余蛋糕的流程，轉(zhuǎn)化若干個(gè)人數(shù)更少的分蛋糕問(wèn)題。因?yàn)槲覀円呀?jīng)知道2人或3人分蛋糕的步驟了。如果我們將問(wèn)題分解成人數(shù)更少的小問(wèn)題，且每個(gè)小問(wèn)題所涉及的蛋糕部分都能不斷縮小，那么這個(gè)分蛋糕流程必然可以結(jié)束。

但是從之前我舉例的四人分蛋糕流程中可以看出，分解成小問(wèn)題后，要確保不發(fā)生妒忌是很難的。這里論文作者發(fā)現(xiàn)了兩種情況下，可以將問(wèn)題分解成小問(wèn)題：

一種情況叫“絕對(duì)占優(yōu)”（Domination）：某個(gè)玩家認(rèn)為剩下的蛋糕，即使全部分配給另一個(gè)玩家，他都不會(huì)妒忌，此時(shí)就稱(chēng)這個(gè)玩家對(duì)另一個(gè)玩家“絕對(duì)占優(yōu)”。比如如果甲發(fā)現(xiàn)，剩下的蛋糕全部給乙的話，甲也不妒忌，就叫甲對(duì)乙“絕對(duì)占優(yōu)”。

(絕對(duì)占優(yōu)示意圖：當(dāng)玩家2和4對(duì)玩家1和3都絕對(duì)占優(yōu)時(shí)，玩家2和4就可以退出分割流程。)

如果一個(gè)玩家對(duì)其他所有玩家都絕對(duì)占優(yōu)時(shí)，那這個(gè)玩家就可以退出游戲了。“你們玩，我不玩了，你們隨便怎么分我都沒(méi)意見(jiàn)”，是這樣吧？所以我們希望要盡可能發(fā)生絕對(duì)占優(yōu)的情況，這樣就能讓玩家數(shù)減少。

第二種可以讓大問(wèn)題變小問(wèn)題的情況叫“顯著分歧”。分蛋糕過(guò)程中，對(duì)蛋糕價(jià)值判斷產(chǎn)生分歧是難免的。但分歧達(dá)到一定程度，反而好處理了。比如，如果剩下的蛋糕現(xiàn)在分成a、b兩部分。甲、乙、丙都認(rèn)為A塊比B塊好，而且甲、乙、丙認(rèn)為A塊比B塊的3倍都好。但是丁認(rèn)為是B塊好。此時(shí)分歧很大，但卻好辦了。我們可以直接把B給丁，而甲、乙、丙對(duì)a塊執(zhí)行三人分蛋糕流程。

因?yàn)槎≌J(rèn)為B塊比A塊好，那么即使A塊后來(lái)整個(gè)分給了甲乙丙中的某個(gè)人，丁也不會(huì)妒忌。而甲、乙、丙都認(rèn)為B塊比A塊的三倍都要好，那么之后，如果他們?nèi)藢?duì)A塊的分配是無(wú)妒忌的，那么甲、乙、丙都會(huì)認(rèn)為自己得到蛋糕的至少是A塊的1/3，比b塊強(qiáng)，所以他們也不會(huì)妒忌丁。

以上這種情況可以推廣到一般人數(shù)，即當(dāng)?shù)案獗环譃锳、B 兩個(gè)部分，其中p個(gè)玩家認(rèn)為a比b的p倍要好，另q個(gè)玩家認(rèn)為B比A的q倍要好，則可以讓p個(gè)玩家分A，q個(gè)玩家分B，這樣一個(gè)大問(wèn)題被分解成了兩個(gè)小問(wèn)題，且能保持無(wú)妒忌。

根據(jù)以上兩種可以讓大問(wèn)題化為小問(wèn)題的思路，論文中設(shè)計(jì)了另兩個(gè)協(xié)議算法：

1. 分歧協(xié)議(discrepency protocal)。分歧協(xié)議就是為了處理出現(xiàn)分歧的情況，并且促使玩家中出現(xiàn)
   “顯著分歧”，使玩家分化為兩隊(duì)人，開(kāi)始各自對(duì)自己喜歡的那部分進(jìn)行分配的流程

2. 退出協(xié)議(GoLeft protocal)。退出協(xié)議就是促使玩家中出現(xiàn)絕對(duì)占優(yōu)的情況，當(dāng)有某個(gè)玩家出現(xiàn)對(duì)其他所有玩家絕對(duì)占優(yōu)時(shí)，他就可以退出這個(gè)游戲。

這兩個(gè)算法流程細(xì)節(jié)非常多，就不展開(kāi)敘述了。那么總體上這個(gè)分蛋糕的協(xié)議的框架就是：

先執(zhí)行若干輪次主協(xié)議，使得蛋糕的一部分被分掉。然后穿插執(zhí)行分歧和退出協(xié)議，使得原始問(wèn)題變?yōu)槿藬?shù)更少的小問(wèn)題。對(duì)這個(gè)小問(wèn)題繼續(xù)執(zhí)行主協(xié)議、分歧協(xié)議和退出協(xié)議。直至每個(gè)小問(wèn)題中的人數(shù)都小于等于3，那么這個(gè)問(wèn)題就能在有限步驟內(nèi)完成。

?????????? (分蛋糕流程主協(xié)議框架，轉(zhuǎn)自美國(guó)計(jì)算機(jī)協(xié)會(huì)ACM網(wǎng)站)

以上整個(gè)算法我介紹完了，整個(gè)算法的復(fù)雜度是一個(gè)十分驚人的數(shù)字，如果人數(shù)是n，則算法大約最多需要執(zhí)行n^n^n^n^n^n次。所以，這也能解釋你到目前為止可能有的一個(gè)最大疑問(wèn)：到底有沒(méi)有真實(shí)可運(yùn)行的代碼，實(shí)現(xiàn)以上流程？結(jié)論很明顯，就是沒(méi)有。因?yàn)榧词箤?xiě)出來(lái)，就算模擬4人的情況，程序也肯定跑不完。

這大概也是為什么這篇論文發(fā)布了這么久之后，才最終被美國(guó)計(jì)算機(jī)協(xié)會(huì)登載在網(wǎng)站上。因?yàn)闆](méi)有代碼，只能靠人力審閱論文，而這個(gè)算法又是非常冗余和繁復(fù)，所以審閱了3、4年才得以正式發(fā)表。但不管怎樣，這是一個(gè)突破，人類(lèi)第一次有了一個(gè)有現(xiàn)步驟內(nèi)的無(wú)妒忌的完美分蛋糕方法。特別是其中有關(guān)“顯著分歧”和“絕對(duì)占優(yōu)”概念，是很有實(shí)用價(jià)值的思路。

我覺(jué)得下一步是，我希望有人能提出簡(jiǎn)化版的，僅針對(duì)4人分蛋糕情形的算法步驟。因?yàn)槲覀兛梢钥闯?，針?duì)三人分蛋糕的Selfrige-Conway算法有點(diǎn)像執(zhí)行了2輪的這篇論文中提到的核心協(xié)議的過(guò)程。所以，針對(duì)4人，是否可以也提出一個(gè)簡(jiǎn)化算法，簡(jiǎn)化到可以具體寫(xiě)出具體分支流程呢？甚至可以不簡(jiǎn)化核心流程，只針對(duì)核心協(xié)議以外的操作步驟進(jìn)行簡(jiǎn)化，那也是一大突破。

好了，今天節(jié)目差不多了，無(wú)論如何，我們知道，科學(xué)家已經(jīng)發(fā)現(xiàn)了一種完美的分割蛋糕的方法，只是你要做好準(zhǔn)備，其步驟之多，到天荒地老都結(jié)束不了。讓我們下期再見(jiàn)。

參考鏈接：

https://cacm.acm.org/magazines/2020/4/243651-a-bounded-and-envy-free-cake-cutting-algorithm/fulltexthttps://arxiv.org/abs/1604.03655

喜馬拉雅FM，搜“大老李聊數(shù)學(xué)”，聽(tīng)更多數(shù)學(xué)內(nèi)容。

微信關(guān)注：dalaoli_shuxue