Even–Pazプロトコル

Even –Pazアルゴリズムは、公平なケーキカットのための計算効率の良いアルゴリズムです。誕生日ケーキなどの特定の異質で分割可能なリソースと、${\displaystyle n}$ケーキのさまざまな部分に対する好みが異なるパートナー。${\displaystyle n}$比例配分を達成するために人々。

ケーキの比例分割に関する最初の公開アルゴリズムは、1948年に公開された最後の縮小アルゴリズムでした。その実行時間複雑度は${\displaystyle O(n^{2})}$1984年、シモン・エヴェンとアザリア・パズは、実行時間計算量がわずかである改良アルゴリズムを発表した。${\displaystyle O(n\log n)}$[ ^{1 ]​}

このアルゴリズムは分割統治戦略を採用しており、時間的に比例分割を実現することが可能です。${\displaystyle O(n\log n)}$。

• 各パートナーは、ケーキを左右に分ける線を引いて、その比率が${\displaystyle \lfloor n/2\rfloor$ :\lceil n/2\rceil } 。カットは交差しないようにする必要があります。これを保証する簡単な方法は、水平線のみ、または垂直線のみを許可することです。
• アルゴリズムは${\displaystyle n}$線を昇順に並べ、線の中央、つまり${\displaystyle \lfloor n/2\rfloor }$th ライン。例えば、5 人のパートナーが線を引く場合${\displaystyle x=1}$、${\displaystyle x=3}$、${\displaystyle x=5}$、${\displaystyle x=8}$そして${\displaystyle x=9}$すると、アルゴリズムはケーキを垂直にカットします。${\displaystyle x=5}$。
• このアルゴリズムは、2つの部分それぞれに、その部分の中に線があるパートナー、つまり最初に線を引いたパートナーを割り当てます。${\displaystyle \lfloor n/2\rfloor }$線は左側に割り当てられ、他の線は右側に割り当てられます。たとえば、線を引いたパートナーは${\displaystyle x=1}$、${\displaystyle x=3}$そして${\displaystyle x=5}$左側の部分に割り当てられたパートナーと、右側の部分に割り当てられるパートナーがいる。各部分は、割り当てられたパートナー間で再帰的に分割される。

ルールに従ってプレイするすべてのパートナーは、少なくとも 1 以上の価値を持つ駒を保証されることが帰納法によって証明できる。${\displaystyle 1/n}$他のパートナーが何をするかに関わらず。

分割統治戦略のおかげで、反復回数はわずか${\displaystyle O(\log n)}$対照的に${\displaystyle O(n)}$ラストディミニッシャー手順では、各反復で各パートナーは 1 つのマークを付ける必要があります。したがって、必要なマークの総数は${\displaystyle O(n\log n)}$。

Even–Pazアルゴリズムの発表から数年後、各人​​に連続したピースを割り当てる決定論的またはランダムな比例分割手順はすべて、${\displaystyle \Omega (n\log n)}$行動。^{[ 2 ]}

さらに、すべての決定論的比例除算手順は、${\displaystyle \Omega (n\log n)}$たとえその手順が各パートナーに連続していないピースを割り当てることを許可していても、またその手順が近似的な公平性のみを保証することを許可していても、アクションは有効である。^{[ 3 ]}

これらの難易度に関する結果は、Even–Pazアルゴリズムが、連続したピースで完全な比例関係を実現するための最速のアルゴリズムであり、部分的な比例関係や、ピースが分離している場合でも、決定論的なアルゴリズムとして最速であることを示唆しています。このアルゴリズムを改善できる唯一のケースは、分離したピースで部分的な比例関係を保証するランダム化アルゴリズムを使用する場合です（Edmonds–Pruhsアルゴリズムを参照）。

ランダム化を用いることで、マークの数を減らすことが可能です。以下の再帰的二分法のランダム化バージョンは、わずか数個のマークのみを使用して比例分割を実現します。${\displaystyle O(n)}$平均してクエリにマークを付けます。^{[ 1 ]}このアイデアは、各反復で、すべてのパートナーに半分の値のマークを付けるように求める代わりに、一部のパートナーにのみそのようなマークを付けるように求め、他のパートナーはどちらの半分を好むかを選択するだけです。パートナーは、それぞれの好みに応じて西または東に送られ、各側のパートナーの数が${\displaystyle n/2}$。次にカットが行われ、各グループの${\displaystyle n/2}$パートナーは再帰的にその半分を分割します。^{[ 4 ]}

最悪の場合でも、私たちはまだ必要としています${\displaystyle n-1}$反復ごとに点数が必要となるため、最悪の場合の必要点数は${\displaystyle O(n\log n)}$しかし、平均すると${\displaystyle O(\log n)}$反復ごとに点数が必要です。漸化式を解くことで、必要な平均点数が次のようになることが示せます。${\displaystyle O(n)}$。

クエリの総数はまだ${\displaystyle O(n\log n)}$各パートナーが半分を選ばなければならないため。