強い比例配分

b _xとa _xの間の有理数p/qを見つけ、b _x > p/q > a _xとなるようにします。これは、b _y < (qp)/q < a _yを意味します。ボブに X を p 等分し、Yをqp 等分するように依頼します。

我々の仮定によれば、ボブはXの各ピースをb _x /p > 1/ q、Yの各ピースをb _y /(qp) < 1/ qと評価している。しかしアリスにとっては、 Xの少なくとも1つのピース（例えばX _{0 ）は1/} qより小さい値を持ち、 Yの少なくとも1つのピース（例えばY _{0 ）は1/} qより大きい値を持つ必要がある。

これで、次の2つの部分X ₀とY ₀が得られました。

V_ボブ（X ₀）>V_アリス（X ₀）

V_ボブ(Y ₀ )<V_アリス(Y ₀ )

アリスとボブは、残りのC \ X ₀ \ Y _{0 を} 比例配分で分け合います (例えば、割り算と選択法を使用します)。アリスの取り分にY ₀を加え、ボブの取り分にX _{0を加えます。}

さて、各パートナーは自分の割り当てが相手の割り当てよりも明らかに優れていると考えているため、その価値は1/2よりも明らかに大きい。

このアルゴリズムをn人のパートナーに拡張したものは、フィンクの「Lone Chooser」アルゴリズムに基づいている。

すでにi -1 人のパートナー ( i ≥ 3の場合)に対して強い比例配分が行われているとします。ここで、パートナー # i がパーティーに参加し、新しい配分が依然として強い比例配分となるように、最初のi -1 人のパートナーそれぞれから小さな分け前を彼に与える必要があります。

例えば、パートナー1を考えてみましょう。dをパートナー1の現在の値と(1/( i -1))の差とします。現在の分割は強く比例しているので、 d>0であることがわかります。

正の整数qを次のように選択する。 ${\displaystyle d>{\frac {1}{(i-1)i(q(i-1)-1)}}}$

パートナー1に自分の取り分を分けてもらうよう頼む${\displaystyle qi-1}$彼が同等の価値があると考えるピースを選び、新しいパートナーに選ばせる${\displaystyle q}$彼が最も価値があると考える作品。

パートナー1は、${\displaystyle {\frac {(qi-1)-q}{qi-1}}={\frac {q(i-1)-1}{qi-1}}}$彼の以前の価値は${\displaystyle {\frac {1}{i-1}}+d}$（ dの定義による）。最初の要素は次のようになる。${\displaystyle {\frac {q(i-1)-1}{(i-1)(qi-1)}}}$そしてdは${\displaystyle {\frac {1}{i(i-1)(qi-1)}}}$それらを合計すると、新しい値は以下よりも大きくなります。${\displaystyle {\frac {(qi-1)(i-1)}{(i-1)i(qi-1)}}={\frac {1}{i}}}$ケーキ全体の。

新しいパートナーは、最初のi -1 人のパートナーからそれぞれq個のピース​​を取った後、少なくとも以下の合計値になります。${\displaystyle {\frac {q}{qi-1}}>{\frac {1}{i}}}$ケーキ全体の。

これは、新しい区分も強い比例関係にあることを証明している。

Julius Barbanel ^{[ 1 ] は}、Woodall のアルゴリズムを、不合理な権利を含む、さまざまな権利を持つエージェントに拡張しました。この設定では、各エージェントiの権利は重みによって表されます。${\displaystyle w_{i}}$、 と${\displaystyle W:=\sum _{i}w_{i}}$強い比例配分とは、各エージェントiに対して、次のようになる配分のことである。

${\displaystyle V_{i}(X_{i})>w_{i}\cdot V_{i}(C)/W}$。

JankoとJoo ^{[ 8 ]}は、異なる権利を持つエージェントのためのより単純なアルゴリズムを提示した。実際、彼らは、強い比例配分問題（等しい権利または異なる権利）を、異なる権利を持つ2つの比例配分問題に還元する方法を示した。

• 作品Xについて、アリスのタイトルを次のように変更します。${\displaystyle w_{A}-1/a_{x}}$そしてボブの権利${\displaystyle w_{B}+1/b_{x}}$b _x > a _xなので_、新しい権利の合計は厳密に以下より小さい。${\displaystyle w_{A}+w_{B}}$したがって、 n個の権利の合計( W _Xで定義) は、厳密にWより小さくなります。
• 作品Yについては、アリスのタイトルを次のように変更します。${\displaystyle w_{A}+1/a_{y}}$そしてボブの権利${\displaystyle w_{B}-1/b_{y}}$ここでも、by _< a _{yなので、}すべての権利の新しい合計 ( W _Yで区切られた) はWより厳密に小さくなります。
• アリスの価値は少なくとも$${\displaystyle {\begin{aligned}&(w_{A}-1/a_{x})\cdot a_{x}/W_{X}+(w_{A}+1/b_{y})\cdot b_{x}/W_{Y}=\\=&(w_{A}a_{x}-1)/W_{X}+(w_{A}a_{y}+1)/W_{Y}\\>&(w_{A}a_{x}-1)/W+(w_{A}a_{y}+1)/W\\=&w_{A}V_{A}(C)/W\end{aligned}}}$$
• 同様に、ボブの価値は少なくとも$${\displaystyle {\begin{aligned}&(w_{B}+1/b_{x})\cdot b_{x}/W_{X}+(w_{B}-1/b_{y})\cdot b_{y}/W_{Y}=\\=&(w_{B}b_{x}+1)/W_{X}+(w_{B}b_{y}-1)/W_{Y}\\>&(w_{B}b_{x}-1)/W+(w_{B}b_{y}+1)/W\\=&w_{B}V_{B}(C)/W\end{aligned}}}$$
• 他のすべてのエージェントiの値は少なくとも$${\displaystyle {\begin{aligned}&w_{i}\cdot V_{i}(X)/W_{X}+w_{i}\cdot V_{i}(Y)/W_{Y}\\>&w_{i}\cdot V_{i}(X)/W+w_{i}\cdot V_{i}(Y)/W\\=&w_{i}V_{i}(C)/W\end{aligned}}}$$つまり、その比率は非常に比例的である。

Janko、Joo、Segal-Halevi、Yuen ^{[ 9 ]}は、各ピースが接続されていなければならない場合の、強く比例したケーキカットのアルゴリズムと困難性の証明を提示しています。