エドモンズ・プルースプロトコル

エドモンズ・プルース・プロトコルは、公平なケーキカットのためのプロトコルです。その目的は、異質な資源をn人の間で部分的に比例的に分割し、各人が全体の少なくとも1/ anに相当すると評価するケーキの部分集合を受け取るようにすることです。${\displaystyle a\geq 10}$は十分に大きな定数です。これは、実行時間が確率1に近いO( n )のランダム化アルゴリズムです。このプロトコルは、ジェフ・エドモンズとカーク・プルースによって開発され、後にジャイシン・ソランキとの共同研究で改良されました。

ケーキを比例的に分割するには、再帰的半分分割アルゴリズムを使用すれば、O( n  log n ) の時間で実現できます。いくつかの困難性の結果から、この実行時間はさまざまな仮定の下で最適であることが示されています。特に、再帰的半分分割は、ピースが連続していなければならない場合に完全な比例性を実現するための最速のアルゴリズムであり、部分的な比例性やピースが分離していても構わない場合でも、可能な限り最速の決定論的アルゴリズムです。困難性の結果でカバーされていないケースの 1 つは、部分的な比例性のみを保証し、ピースが分離している可能性があるランダム化アルゴリズムの場合です。Edmonds–Pruhs プロトコルは、このケースに対して実行時間 O( n )のアルゴリズムを提供することを目的としています。 

一般的な構成は次のとおりです。^{[ 1 ]}

1. 各パートナーは、ケーキを主観的に等しい価値を持つn個のピース​​に個人的に分割します。これらのn 個のピース​​は候補ピースと呼ばれます。 
2. 各パートナーは、重複を許して、 2d個の候補ピースを均等にランダムに選択します（dは後で決定される定数です）。候補ピースはd個のペアにグループ化され、パートナーはそれをアルゴリズムに報告します。これらのn⋅d個のペアは、準々決勝ブラケットと呼ばれます。
3. 各準々決勝トーナメント表から、アルゴリズムは1つのピースを選択します。これは、他の候補ピースの中で最も少ない数のピースと交差するピースです。これらのn  ⋅ d個のピース​​は準決勝ピースと呼ばれます。 
4. 各パートナーに対して、アルゴリズムは1つのピースを選択します。これらは「最終ピース」と呼ばれます。最終ピースは、ケーキの各ポイントが最大2つの最終ピースで覆われるように選択されます（下記参照）。これが成功した場合は、ステップ5に進みます。失敗した場合は、ステップ1からやり直します。
5. ケーキが1つの最終ピースにのみ属する部分は、そのピースの所有者に渡されます。ケーキが2つの最終ピースに属す部分は、任意の決定論的な比例分割アルゴリズムによって比例的に分割されます。

このアルゴリズムは、各パートナーが少なくとも候補ピースの半分を受け取る確率が高いことを保証しており、これは（値が加算される場合）少なくとも 1/2の値を意味します。

ステップ5にはO( n )個の候補ピースとO( n )個の追加分割があり、それぞれO(1)の時間で完了します。したがって、アルゴリズム全体の実行時間は O( n )となります。

この計画における主な課題は、ステップ4で最終的なピースを選択することです。

まず、含意グラフを作成します。これは、準決勝のピースをノードとするグラフで、ピース I がパートナー j のもう一方のピースと交差する場合に、パートナー i のピース I からパートナー j のピース J へのエッジが存在します（したがって、ピースIを選択して交差を避けたい場合は、ピースJも選択する必要があります）。

まだピースを受け取っていない任意のパートナーiを選択し、そのパートナーの任意のピースI を最終ピースとして選択します。次に、含意グラフのリンクをたどり、 Iから到達可能なすべてのピースを最終ピースとして選択します。良いシナリオは 2 つあります。各パートナーに 1 つの最終ピースを割り当てて終了するか、出力リンクのないピースに到達するか (これは、他のピースと交差しないことを意味します)。後者の場合、残りのパートナーのいずれかの別のピースを選択して続行します。悪いシナリオは、たどった結果、同じパートナーの 2 つの異なるピース、または同様に、開始したパートナーiのもう 1 つのピースに到達することです。パートナーiの 1 つのピースから同じパートナーの別のピースに至るこのようなパスは、ペア パスと呼ばれます。含意グラフにペア パスが含まれていない場合、上記の選択アルゴリズムは、重複しないn個の最終ピースのコレクションを返し、処理は完了します。あとは、含意グラフにペア パスが含まれている確率を計算するだけです。

まず、すべてのパートナーが同じ価値関数（したがって同じ候補ピースの集合）を持つ特殊なケースを考えてみましょう。この場合、ペアパスの確率は簡単に計算できます。各エッジの確率は 1/ anであり、すべてのエッジは独立しているため、長さkの特定のペアパスの確率は 1/( an ) ^kであり、任意のペアパスの確率は最大で次のようになります。

${\displaystyle \sum _{k}{\frac {(2dn)!}{(2dn-k)!(an)^{k}}}=O\left({\frac {1}{a^{2}}}\right)}$

d =1と十分大きなaを選択することで、この確率をいくらでも小さくすることが可能です。これは、準決勝選考段階（#3）を省略し、準々決勝進出者全員を準決勝進出者とみなす場合でも同様です。

このケースは、ボールをビンに入れるモデルと類似していることに注意してください。各ボールに対してd個のビンをランダムに選択する場合、各ボールに対して1つのビンを選択することで、すべてのビンが異なるものになる（最大積載量が1になる）ことが証明されます。

価値関数が異なる一般的なケーキモデルでは、含意グラフのエッジの確率は依存します。しかし、準決勝選考段階のおかげで、含意グラフに長さが3以上のペアパスが含まれる確率は最大で${\displaystyle {\frac {32d^{5}}{a^{2}\cdot (a-4d^{2})}}}$。

残る課題は、長さ2のペアパスの処理です。残念ながら、含意グラフにこのようなペアパスが存在する確率は無視できません。しかし、高い確率でパートナーを2つのグループに分割し、各グループに長さ2のペアパスが存在しないようにすることが可能です。したがって、最終ピース選択アルゴリズムを2回実行できます。各グループに対して1回ずつ実行します。交差は異なるグループの最終ピース間でのみ発生するため、ケーキの各ポイントにおける重なりは最大で2です。このような2分割が不可能な確率は最大で${\displaystyle {\frac {16d^{3}}{a^{3}}}+{\frac {8d^{2}}{a^{2}}}}$。

上記の2つの式を合計し、d  =  2とすると、失敗の確率は依然として${\displaystyle O\left({\frac {1}{a^{2}}}\right)}$。ここで、aは比例比率であることを思い出してください。各パートナーに保証したい価値が高ければ高いほど、分割が失敗し、ステップ1からやり直さなければならない可能性が高くなります。

同じアルゴリズムは、カットが近似値の場合にも機能します。つまり、パートナーはピースにまったく同じ値を付ける方法を知りません。必要な値よりpパーセント高い値または低い値でピースを付ける可能性があり、正確な誤差はランダムに選択されます。^{[ 1 ]}

以下の方式を用いることで、故障の確率をさらに低減できる可能性がある。^{[ 2 ]}

• 元のプロトコルを2回、それぞれ独立して実行する。
• 各実行において、ペアパスの先頭に現れるパートナーをすべて削除し、元のプロトコルと同様に、残りのパートナーにのみ最終的なピースを割り当てます。
• すべてのパートナーについて、少なくとも1つの実行でそのピースが取り除かれなかった場合、すべてのパートナーが少なくとも1つの最終ピースを保持していることになるので、処理は完了です。

各試行で特定のパートナーを取り除く確率は${\displaystyle O\left({\frac {1}{n}}\right)}$両方の試行で特定のパートナーを削除する確率は${\displaystyle O\left({\frac {1}{n^{2}}}\right)}$したがって、失敗の確率は${\displaystyle O\left({\frac {n}{n^{2}}}\right)=O\left({\frac {1}{n}}\right)}$これは、部分比例比aを一定に保った場合でも、 nが増加すると 0 になります。

ケーキモデルは、ボールをビンに分割するモデルの一般化と見なすことができます。このモデルは、負荷分散などの分野で広く応用されています。このような状況では、ボールはさまざまなビン/マシンに割り当てることができるジョブを表します。大まかに言えば、同一のマシンの負荷分散はボールとビンに相当し、無関係なマシンの負荷分散はケーキカットに相当します。したがって、ケーキモデルとエドモンズ-プルースプロトコルは、無関係なマシンの負荷分散を含む設定で興味深い応用が可能であることは妥当です。^{[ 1 ]}