兩位年輕的計算機科學家已經弄清楚瞭如何將蛋糕公平地分配給任意數量的人，從而解決了數學家們幾十年來一直在努力解決的問題。他們的工作讓許多研究人員感到震驚，他們認為這種公平分配協議可能是不可能的。
蛋糕切割是許多現實世界問題的隱喻，這些問題涉及在那些對其特徵有不同價值的人之間分配一些連續的物件，無論是蛋糕還是土地，例如，一個人渴望巧克力糖霜，而另一個人則盯著奶油花。至少從聖經時代起，人們就知道有一種方法可以在兩個人之間分配這樣的物體，這樣誰也不會嫉妒對方：一個人將蛋糕切成兩片她認為價值相等的切片，另一個人可以選擇她最喜歡的切片。《創世紀》中，亞伯拉罕（當時被稱為亞伯蘭）和羅得使用這種“我切你選”的程式來分割土地，亞伯拉罕決定在哪裡分割，羅得在約旦和迦南之間選擇。
關於支援科學新聞
如果您喜歡這篇文章，請考慮透過以下方式支援我們屢獲殊榮的新聞報道 訂閱。透過購買訂閱，您正在幫助確保關於塑造我們當今世界的發現和想法的具有影響力的故事的未來。
大約在 1960 年，數學家們設計出一種演算法，可以為三名參與者產生類似的“無嫉妒”蛋糕分配。但直到現在，他們為三名以上參與者提出的最佳方案是政治學家 Steven Brams 和數學家 Alan Taylor 於 1995 年建立的 程式，該程式保證產生無嫉妒的分配，但它是“無界的”，這意味著它可能需要執行一百萬步、十億步或任何大數字，具體取決於參與者對蛋糕的偏好。
Brams 和 Taylor 的演算法在當時被譽為一項突破，但卡內基梅隆大學的計算機科學家，也是 Spliddit 的建立者之一 Ariel Procaccia 說：“我認為它不是有界的這一事實是一個巨大的缺點”，Spliddit 是一種免費的線上工具，為室友之間分配家務或租金等任務提供公平分配演算法。
在過去的 50 年裡，包括 Procaccia 在內的許多數學家和計算機科學家都確信，對於在 n 個參與者之間分配蛋糕，可能沒有有界的、無嫉妒的演算法。
“這正是我進入公平分配主題的原因，”賓夕法尼亞州布林莫爾學院的數學教授 Walter Stromquist 說，他在 1980 年證明了一些關於蛋糕切割的開創性成果。“我一生都認為，當我有了時間，我會回到這個問題，並證明這個特定結果的擴充套件是不可能的。”
但在四月份，兩位計算機科學家推翻了人們的期望，他們在 線上釋出的一篇論文 中描述了一種無嫉妒的蛋糕切割演算法，該演算法的執行時間僅取決於參與者的數量，而不是他們的個人偏好。其中一位——卡內基梅隆大學的博士後研究員，27 歲的 Simon Mackenzie——將於 10 月 10 日在第 57 屆 IEEE 計算機科學基礎研討會上展示該團隊的發現，該研討會是計算機科學領域最重要的會議之一。
該演算法非常複雜：在 n 個參與者之間分配蛋糕可能需要多達 n^n^n^n^n^n 步以及大致等效的切割次數。即使只是少數參與者，這個數字也大於宇宙中原子的數量。但該團隊的另一半成員，新南威爾士大學和澳大利亞資料研究小組 Data61 的 35 歲計算機科學家 Haris Aziz 說，研究人員已經有了使該演算法更簡單、更快的想法。
Procaccia 說，對於研究 公平分配理論 的人來說，這是“近幾十年來最重要的成果”。
蛋糕塊
Aziz 和 Mackenzie 的新演算法建立在數學家 John Selfridge 和 John Conway 大約在 1960 年獨立提出的，用於在三個人之間分配蛋糕的優雅程式之上。
如果 Alice、Bob 和 Charlie 想要分享一塊蛋糕，該演算法首先讓 Charlie 將蛋糕切成三塊，從他的角度來看，這三塊蛋糕的價值相等。Alice 和 Bob 各自被要求指向他們最喜歡的切片，如果他們喜歡不同的切片，我們就完成了——他們各自拿走他們最喜歡的切片，Charlie 拿走剩下的切片，每個人都高高興興地回家。
如果 Alice 和 Bob 有相同的最愛，那麼要求 Bob 從該切片上修剪掉一點蛋糕，以便剩餘部分的值等於他的第二喜歡的切片；修剪下來的部分放在一邊稍後處理。現在 Alice 可以從這三片蛋糕中選擇她最喜歡的一片，然後 Bob 可以選擇，但要求是，如果 Alice 沒有選擇修剪過的切片，他必須拿走它。Charlie 得到第三片切片。
在這個階段，沒有一個參與者嫉妒對方。Alice 很高興，因為她先選擇了；Bob 很高興，因為他得到了他兩個同樣喜歡的首選之一；Charlie 很高興，因為他得到了他最初的三塊中的一塊，在他看來，這三塊都是相等的。
但是，仍然有修剪下來的部分需要分配。使分配這部分而不會產生更多修剪，並且陷入修剪和選擇的無限迴圈成為可能的原因是，Charlie 對他目前得到的蛋糕不僅僅是滿意；即使得到修剪切片的玩家得到所有等待分配的蛋糕，他也不會感到被欺騙，因為修剪切片加上修剪等於原始切片之一。Aziz 和 Mackenzie 透過說 Charlie “支配”了得到修剪切片的玩家來描述這種關係。
現在，例如，如果 Alice 是得到修剪切片的人，則演算法按如下方式進行：Bob 將修剪下來的部分切成他認為價值相等的三塊，然後首先 Alice 選擇一塊，然後是 Charlie，然後是 Bob。每個人都很高興：Alice 因為她先選擇了，Charlie 因為他得到了一塊他比 Bob 更喜歡的切片（並且他不在乎 Alice 拿了多少），而 Bob 因為這三塊切片在他看來是相等的。
Brams 和 Taylor 在設計他們 1995 年的演算法時使用了支配的概念（沒有這樣稱呼它），但他們無法將這個想法推進到足以獲得有界演算法。在接下來的 20 年裡，其他人也做不到。“我認為這不是因為缺乏嘗試，”Procaccia 說。
新手蛋糕切割者
當 Aziz 和 Mackenzie 幾年前決定著手解決這個問題時，他們是蛋糕切割問題方面相對的新手。“我們沒有那些一直在深入研究這個問題的人那麼多的背景，”Aziz 說。“雖然這在大多數情況下是一個缺點，但在這種情況下，這在某種程度上是一個優勢，因為我們沒有以相同的方式思考。”
Aziz 和 Mackenzie 從頭開始研究三方問題來試水，他們的分析最終引導他們找到了 四方案例的有界無嫉妒演算法，他們於去年在網上釋出了該演算法。
他們無法立即看到如何將他們的演算法擴充套件到四個以上的參與者，但他們狂熱地投入到這個問題中。“在我們提交了四方案例的論文後，我們非常渴望在我們更資深、更聰明的人將其推廣到 n 方案例之前嘗試一下，”Aziz 說。大約一年後，他們的努力取得了成功。
與 Selfridge-Conway 演算法一樣，Aziz 和 Mackenzie 的複雜協議反覆要求個別參與者將蛋糕切成 n 塊相等的部分，然後要求其他參與者進行修剪並選擇蛋糕塊。但該演算法還執行其他步驟，例如定期以仔細控制的方式交換參與者的蛋糕儲藏部分，目的是增加參與者之間支配關係的數量。
這些支配關係使 Aziz 和 Mackenzie 能夠降低問題的複雜性：例如，如果三名參與者支配了所有其他人，那麼可以將這三名參與者連同他們的蛋糕切片一起送走——無論誰得到剩餘的修剪部分，他們都會很高興。現在需要擔心的參與者更少了，並且在有限數量的此類步驟之後，每個人都已得到滿足，並且所有蛋糕都已分發完畢。
Procaccia 說：“回顧一下，該演算法有多麼複雜，有人花這麼長時間才找到一個演算法也就不足為奇了。”但 Aziz 和 Mackenzie 已經認為他們可以大大簡化他們的演算法，使其成為一個不需要蛋糕交換並且少於 n^n^n 步的演算法。Aziz 說，他們目前正在撰寫這些新成果。
Brams 警告說，即使是更簡單的此類演算法也不太可能具有實際意義，因為參與者收到的蛋糕部分通常包括來自蛋糕不同部分的許多微小的碎屑——如果您要分配像土地這樣的東西，這不是一種可行的方法。
但對於研究蛋糕切割的數學家和計算機科學家來說，Stromquist 說，新結果“重置了這個主題”。
Procaccia 說，既然研究人員知道可以在有限步數內公平地分配蛋糕，那麼下一個目標是瞭解 Aziz 和 Mackenzie 的上限與分配蛋糕所需的現有下限切割次數之間的巨大差距。Procaccia 之前證明了，無嫉妒的蛋糕切割演算法將至少需要大約 n2 步——但與 n^n^n^n^n^n 甚至 n^n^n 相比，這個界限微不足道。
Aziz 說，研究人員現在必須弄清楚如何彌合這一差距。“我認為在這兩個方向上都可能取得進展。”
經 Quanta 雜誌 許可轉載，Quanta 雜誌是 西蒙斯基金會 的編輯獨立出版物
其使命是透過報道數學、物理和生命科學的研究進展和趨勢，增進公眾對科學的理解。