悠日教會: 公平切蛋糕

公平切蛋糕是一種公平分配問題。這個問題涉及異質資源，例如具有不同配料的蛋糕，它被認為是可分割的——可以將其切成任意小塊而不破壞其價值。資源必須分配給對蛋糕的不同部分有不同偏好的幾個合作夥伴，即，有些人喜歡巧克力配料，有些人喜歡櫻桃，有些人只想要盡可能大的一塊。分配應該是一致公平的——每個人都應該得到一份被認為是公平的份額。

「蛋糕」只是一個比喻；公平切蛋糕的程序可以用來分割各種資源，例如土地、廣告空間或廣播時間。

公平切蛋糕的典型程序是分而治之，創世記中為解決亞伯拉罕和羅得的衝突而提到。這個過程解決了兩個人的公平分配問題。公平切蛋糕的現代研究始於第二次世界大戰期間，當時雨果·斯坦豪斯 (Hugo Steinhaus)要求他的學生斯特凡·巴納赫 (Stefan Banach)和布羅尼斯瓦夫·納斯特(Bronisław Knaster)找到對三個或更多人進行分而選擇的概括。他們開發了最後的遞減程序。^[ 1 ]如今，公平切蛋糕已成為數學、電腦科學、經濟學和政治學領域深入研究的課題。^[ 2 ]

假設

有一個蛋糕C，通常假設它是有限的一維線段、二維多邊形或多維歐幾里德平面R ^d的有限子集。

有n個人對C具有主觀價值函數。每個人i都有一個價值函數Vi _，它將C的子集映射到數字。所有價值函數都被假定為相對於長度、面積或（一般而言）勒貝格測度絕對連續。^[³^]這表示不存在「原子」－不存在可供一個或多個代理人分配正值的奇點，因此蛋糕的所有部分都是可分的。在許多情況下，價值函數被假定為sigma 加法（整體的值等於其各部分值的總和）。

C必須分成n 個不相交的子集，這樣每個人都會收到一個不相交的子集。分配給個人i 的作品稱為 $X_{i}$ ，和 $C=X_{1}\sqcup \cdots \sqcup X_{n}$ 。

n個人對C擁有平等的權利。也就是說，人民的權利不存在爭議——每個人都同意其他人都有權獲得公平的份額。唯一的問題是如何分配蛋糕，讓每個人都能得到公平的份額。

在下面的例子中，將使用下面的蛋糕作為說明。

蛋糕有兩個部分：巧克力和香草。
有兩個人：愛麗絲和喬治。
Alice 對巧克力的評價為 9，對香草的評價為 1。
喬治對巧克力的評價為 6，對香草的評價為 4。

正義要求

相稱性

正義的最初且最常見的標準是相稱性（PR）。在按比例切蛋糕時，每個人都會收到一塊他認為至少是整個蛋糕價值的1/ n的蛋糕。在範例蛋糕中，可以透過將所有香草和 4/9 巧克力給喬治（值為 6.66），將另外 5/9 巧克力給愛麗絲（值為 5）來實現比例分配。用符號表示：

\forall {i}:\ V_{i}(X_{i})\geq 1/n

對於具有相加估值的n個人來說，比例除法總是存在的。最常見的協定是：

最後一個減數器，一種可以保證n 個片段連接的協定（即沒有人得到一組兩個或更多斷開連接的片段）。特別是，如果蛋糕是一維區間，那麼每個人都會收到一個區間。該協議是離散的並且可以輪流播放。它需要 O( n ² ) 次操作。
Dubins-Spanier動刀過程是 Last 減數器的連續時間版本。^[ 4 ]
Fink 協定（也稱為連續對或孤獨選擇器）是一種可用於線上劃分的離散協定：給定n − 1 個夥伴的比例劃分，當新夥伴加入時，協定會修改現有的劃分，以便新合作夥伴和現有合作夥伴均保留為1/ n。缺點是每個夥伴都會收到大量不連貫的碎片。
Even-Paz 協議基於遞歸地將蛋糕和代理組減半，只需要 O( n log n ) 次操作。這是比例除法最快的確定性協議，也是可以保證各部分連接的最快的比例除法協議。
Edmonds–Pruhs 協議是一種隨機協議，只需要 O( n ) 操作，但只保證部分比例除法（每個夥伴至少收到 1/ an，其中a是某個常數），並且它可能為每個夥伴提供一組“麵包屑”而不是單一連接的碎片。
貝剋土地劃分協議可以在幾個鄰國之間按比例劃分有爭議的領土，這樣每個國家都可以獲得與其目前擁有的領土相連和相鄰的份額。
考慮到至少兩個合夥人對至少一件作品的價值有不同的看法，伍德爾的超比例分割協議產生的分割使每個合夥人嚴格超過 1/ n 。

有關更多詳細資訊和完整參考，請參閱比例蛋糕切割。

比例標準可以推廣到人民權利不平等的情況。例如，在不同權益的比例分蛋糕中，蛋糕屬於股東，其中一人持有20%，另一人持有80%。這就引出了加權比例標準（WPR）：

\forall i:V_{i}(X_{i})\geq w_{i}

其中w _i是總和為 1 的權重。

無嫉妒

另一個常見標準是無嫉妒（EF）。在無嫉妒的切蛋糕過程中，每個人都會收到一塊他認為至少與其他蛋糕一樣珍惜的蛋糕。用符號表示：

\forall i,j:\ V_{i}(X_{i})\geq V_{i}(X_{j})

在某些情況下，比例性和無嫉妒性之間存在著隱含關係，如下表所示：

代理商	估價	EF意味著PR？	PR 意味著 EF？
2	添加劑	是的	是的
2	一般的	不	不
3+	添加劑	是的	不
3+	一般的	不	不

分而選協議找到的分配始終是 EF。如果價值函數是可加的，那麼這個除法也是 PR；否則，比例性就得不到保證。

即使估值不是相加的，只要它們可以表示為一致的偏好集，n個人的 EF 劃分就存在。 EF劃分已經分別針對必須連接的情況和可以斷開的更簡單的情況進行了研究。

對於連接件，主要結果是：

Stromquist 的移動刀程序為 3 個人提供了一個無嫉妒的劃分，方法是給每個人一把刀，並指示他們以預先指定的方式在蛋糕上連續移動刀。
Simmons 協定可以任意精確度為n個人產生一個無嫉妒除法的近似值。如果值函數是可加的，則除法也會成比例。否則，分配仍然是無嫉妒的，但不一定是成比例的。該演算法給出了解決一些公平劃分問題的快速實用的方法。^[ 5 ]^[ 6 ]

這兩種演算法都是無限的：第一個是連續的，第二個可能需要無限的時間才能收斂。事實上，任何有限協議都無法找到將連接區間劃分為 3 個或更多人的無嫉妒劃分。

對於可能斷開的部分，主要結果是：

Selfridge-Conway 離散程序最多可使用 5 次切割，為 3 人提供無嫉妒的劃分。
Brams-Taylor-Zwicker 動刀程序最多可使用 11 次切割，為 4 人提供無嫉妒的分割。
最後減法器協定的可重入變體找到了有限時間內無羨慕慕除法的加法近似。具體來說，對於每個常數 $\epsilon >0$ ，它傳回一個除法，其中每個夥伴的值至少是最大值減去 $\epsilon$ ，及時 $O(n^{2}/\epsilon )$ 。
三種不同的程序，一種由Brams 和 Taylor (1995)提出，一種由Robertson 和 Webb (1998)提出，另一種由 Pikhurko (2000) 提出，為n個人產生了一個無嫉妒的劃分。兩種演算法都需要有限但無限的切割次數。
^{Aziz 和 Mackenzie (2016) [ 7 ]}的過程在有限數量的查詢中找到n個人的無嫉妒劃分。

一般情況下的負面結果比關聯情況下的負面結果弱得多。我們所知道的是，每個無嫉妒除法演算法都必須至少使用 Ω( n ² ) 個查詢。這個結果與最著名程式的運行時複雜性之間存在很大差距。

更多詳細資訊和完整參考資料，請參閱無羨慕的蛋糕切割。

其他標準

第三個較不常見的標準是公平性(EQ)。在公平的分配中，每個人都享有完全相同的價值。在範例蛋糕中，可以透過給每個人一半巧克力和一半香草來實現公平分配，這樣每個人都享有價值 5。

\forall i,j:\ V_{i}(X_{i})=V_{j}(X_{j})

第四個標準是準確性。如果每個夥伴i的權利是 w _i，則精確劃分是這樣的劃分：

\forall {i,j}:\ V_{i}(X_{j})=w_{j}

如果權重全部相等（等於 1/ n），則該除法稱為完美除法，且：

\forall i,j:\ V_{i}(X_{j})=1/n

幾何要求

在某些情況下，分配給合作夥伴的棋子除了公平之外還必須滿足一些幾何約束。

最常見的限制是連通性。如果「蛋糕」是一維區間，則這表示每塊蛋糕也是一個區間。如果蛋糕是一維圓形（“餡餅”），則這意味著每個部分都是弧形的要求；請參閱公平切餡餅。
另一個約束是鄰接性。這項限制適用於「蛋糕」是有爭議的領土，必須在鄰國之間瓜分的情況。在這種情況下，可能會要求分配給每個國家的棋子與其當前領土相鄰；這個限制是透過希爾的土地劃分問題來處理的。
在土地劃分中，通常存在二維幾何約束，例如，每塊應該是正方形或更一般地是胖物體。^[ 8 ]

程序要求

除了最終分割區的所需屬性之外，還存在分割過程的所需屬性。這些屬性之一是真實性（又稱激勵相容性），它有兩個層次。

弱真實性意味著，如果合作夥伴向演算法透露了他的真實價值衡量標準，則無論其他合作夥伴做什麼，他都保證會收到他的公平份額（例如，在按比例分配的情況下，整個蛋糕價值的1/ n）。即使所有其他夥伴結盟的唯一目的是傷害他，他仍然會得到保證的比例。從這個意義上說，大多數切蛋糕演算法都是真的。^[ 1 ]
強烈的誠實意味著任何合作夥伴都無法從謊言中獲益。也就是說，說真話是佔優策略。大多數切蛋糕協議都不是非常真實的，但是已經開發了一些真實的協議；看如實切蛋糕。

另一個屬性是對稱性：過程中不同角色之間不應存在差異。已經研究了該屬性的幾個變體：

匿名性要求，如果代理被排列並重新執行過程，那麼每個代理都會收到與原始執行中完全相同的片段。這是一個強條件；目前，只有 2 名特工知道匿名程序。
對稱性要求，如果對代理進行排列並重新執行過程，則每個代理都會收到與原始執行中相同的值。這比匿名性弱；目前，對於任意數量的代理人來說，對稱和比例的過程是已知的，並且需要 O( n ³ ) 次查詢。對於任意數量的代理來說，對稱且無嫉妒的過程是已知的，但它需要更長的時間——它需要n！執行現有的無嫉妒程序。
亞里斯多德主義要求，如果兩個主體具有相同的價值度量，那麼他們就會獲得相同的價值。這比對稱性弱；任何無嫉妒的程序都會滿足它。此外，亞里斯多德和比例過程對於任意數量的代理都是已知的，並且需要 O( n ³ ) 查詢。

有關詳細資訊和參考，請參閱對稱公平蛋糕切割。

第三類程序要求是單調性：當用更小/更大的蛋糕和更小/更大的代理集重新應用分割程序時，所有代理的效用應該朝相同的方向變化。有關更多詳細信息，請參閱資源單調性。

效率要求

除了正義之外，考慮分工的經濟效率也很常見；看看高效的切蛋糕。效率有幾個等級：

較弱的概念是帕累托效率。把整個蛋糕送給一個人就很容易滿足了；挑戰在於如何與公平結合來滿足這項要求。請參閱高效無嫉妒劃分。
一個更強烈的概念是功利最大化－最大化效用總和。（嗯）。當價值函數是可加的時，就存在 UM 劃分。直觀地說，要創建 UM 部門，我們應該將每一塊蛋糕交給最重視它的人。在蛋糕範例中，UM 部門會將整個巧克力送給 Alice，將整個香草送給 George，從而實現 9 + 4 = 13 的功利價值。可以被分成幾塊，使得每塊的價值密度對所有人來說都是恆定的。當價值函數不是分段常數時，UM 分配的存在源自於經典測度論定理。請參閱功利主義切蛋糕。

高效率公平分工

對於具有附加價值函數的n個人，PEEF 劃分始終存在。這就是韋勒定理。^[ 9 ]

如果蛋糕是一維區間，並且每個人必須接收一個連通區間，則以下一般結果成立：如果價值函數是嚴格單調的（即，每個人嚴格偏愛一塊而不是其所有真子集），則每個EF 劃分為還有PE。^[ 10 ]因此，在這種情況下， Simmons 協議產生了 PEEF 劃分。

如果蛋糕是一維圓（即兩個端點拓樸確定的區間）並且每個人都必須收到一條連通的弧，那麼前面的結果就不成立：EF除法不一定是PE。此外，還有一些不存在 PEEF 除法的（非相加）價值函數對。然而，如果有 2 種試劑，並且其中至少一種具有附加值函數，則存在 PEEF 劃分。^[ 11 ]

如果蛋糕是一維的，但每個人都可能收到它的一個不相連的子集，那麼 EF 劃分不一定是 PE。在這種情況下，需要更複雜的演算法來找到 PEEF 劃分。

如果值函數是可加的且分段常數，則存在找到 PEEF 除法的演算法。^[ 12 ]如果值密度函數是可加的且Lipschitz 連續的，那麼它們可以近似為分段常數函數“盡可能接近”，因此該演算法近似“盡可能接近”PEEF 除法。^[ 12 ]

EF 部門不一定是 UM。^[ 13 ]^[ 14 ]處理這個困難的一種方法是在所有可能的EF分割中找到功利價值最高的EF分割。這個問題已經針對一個一維區間的蛋糕進行了研究，每個人都可能收到不相連的碎片，並且價值函數是可加的。^[ 15 ]

計算模型

推理演算法的運行時複雜度需要計算模型。文獻中常見幾種這樣的模型：

Robertson-Webb 查詢模型——其中演算法可能會向每個代理商詢問兩種查詢之一：「評估給定的一塊蛋糕」或「用給定值標記一塊蛋糕」。
移動刀模型－演算法不斷在蛋糕上方移動一把或多把刀，直到一些代理人大喊「停止」。
直接揭示模型—所有代理人向機制揭示他們的整個估值。只有當估值可以簡潔地表示時，例如，當它們是分段均勻、分段常數或分段線性時，模型才有意義。
同步報告模型－代理同時發送其價值測量的離散化。離散化是一系列切點以及這些切點之間的片段值（例如：兩個智能體的協定可能要求每個智能體報告三個切點 (0, x ,1) 的序列，其中(0, x ) 和 ( x ,1)的值為1/2)。^[ 16 ]

分割多個蛋糕

切蛋糕問題有一個概括，即有多個蛋糕，每個智能體需要在每個蛋糕中得到一塊。

Cloutier、Nyman 和 Su ^[ 17 ]研究兩人無羨慕多蛋糕分割。對於兩個蛋糕，他們證明當有 2 個代理並且每個蛋糕被切成 2 塊時，EF 分配可能不存在。然而，當有 2 個智能體並且一個蛋糕被切成 3 塊（最不想要的一塊被丟棄）時，或者當有 3 個智能體並且每個蛋糕被切成 2 塊（一個智能體被忽略；其餘兩個的分配為EF）。
Lebert、Meunier 和 Carbonneaux ^[ 18 ]證明，對於兩個蛋糕，當有3 個代理且每個蛋糕被切成5 塊（每個蛋糕中最不想要的兩個塊被丟棄）時，EF 分配始終存在。
Nyman、Su 和 Zerbib ^[ 19 ]證明，對於k 個蛋糕，當有k ( n -1)+1 個代理且每個蛋糕被切成n塊時，EF 分配總是存在（對於某些n 個集合，分配是EF）代理）。

兩個相關的問題是：

多層切餅，^[ 20 ]其中蛋糕按「層」排列，同一代理的各個塊不得重疊（例如，每個蛋糕代表一天中某個設施可用的時間；一個代理不能同時使用兩個設施）。
公平的多塊蛋糕切割，^[ 21 ]，代理商不希望在每個蛋糕上都得到一塊，相反，他們希望在盡可能少的蛋糕上得到一塊。

蛋糕分享

Bei、Lu 和 Suksompong ^[ 22 ]提出了一個模型，在該模型中，代理人不應將一塊蛋糕分給每個代理人，而是應共同選擇一塊他們將共享的蛋糕。這可以看作是委員會選舉的變體，其中候選人是可分割的。有一個候選連續體，由實數區間 [0, c ] 表示，目標是選擇該區間的子集，總長度至多為k，其中 k和c可以是 0< k的任何實數< c .他們將合理表示概念推廣到這種設定。 Lu、Peters、Aziz、Bei 和 Suksompong ^[ 23 ]將這些定義擴展到具有混合可分割和不可分割候選者的環境（參見合理表示）。

參見

公平物品分配－類似的問題，其中要劃分的物品是不可分割的

悠日教會

公平切蛋糕

假設