フィンクプロトコル

フィンクプロトコル^{[ 1 ]}（連続ペア^{[ 2 ]}またはローンセレクタ^{[ 3 ]}としても知られる）は、ケーキを比例的に分割するためのプロトコルです。

このシステムの最大の利点は、事前にパートナーの人数を把握していなくても、オンラインで運用できる点です。新しいパートナーが参加すると、既存の分配比率が調整され、新規参加者にも公平な分配が行われます。既存のパートナーへの影響は最小限に抑えられます。

その主な欠点は、各パートナーに連結された単一のピースを与えるのではなく、各パートナーに多数の「パンくず」を与えることである。

我々は、パートナーの数を増やしていく場合について、帰納的にプロトコルを説明する。

パートナー1がパーティーに来ると、彼はケーキを全部持って行ってしまう。したがって、彼の価値は1である。

パートナー2が到着すると、パートナー1はケーキを自分にとって同等の2つのピースに切り分けます。新しいパートナーは、自分にとってより良いピースを選びます。こうして、各パートナーの価値は少なくとも1/2になります（分割して選ぶプロトコルと同様です）。

パートナー3が参加すると、パートナー1とパートナー2は、それぞれが平等だと思う3つのピースに自分の持ち分を切り分けます。新しいパートナーは、各パートナーから1ピースずつ選びます。パートナー1とパートナー2のそれぞれの持ち分の価値は、以前の価値（1/2）の少なくとも2/3です。したがって、新しい価値は少なくとも1/3です。パートナー3は、パートナー1とパートナー2の持ち分を次のように評価します。${\displaystyle v_{1}}$、${\displaystyle v_{2}}$、 どこ${\displaystyle v_{1}+v_{2}=1}$パートナー3の価値は少なくとも${\displaystyle {\frac {v_{1}}{3}}}$1番目の作品から少なくとも${\displaystyle {\frac {v_{2}}{3}}}$2番のケーキから、彼は少なくとも全体のケーキの3分の1を手に入れることになる。

一般的に、パートナーi がパーティーに参加すると、前のi -1 人のパートナーは自分の取り分をi等分し、新しいパートナーはそれぞれの山から 1 つずつ取ります。ここでも、各パートナーの価値は全体の少なくとも 1/ nであることを証明できるため、分配は比例的です。

アルゴリズムをそのまま使用すると、${\displaystyle n!}$ピースですが、実際には約${\displaystyle n^{3}/3}$各パートナーが実際に行う必要があるのは${\displaystyle n-1}$カットするとき${\displaystyle n}$^{パートナー}がやってくる。

フィンクのプロトコルは、他のケーキカットプロトコルのサブルーチンで使用されている。

• n人のプレイヤーに対する超比例分割のためのウッドールのプロトコル。
• オースティンのムービングナイフ手順、各パートナーに彼が正確に${\displaystyle 1/n}$合計のうち。