異なる権利に基づく比例配分されたケーキカット

公平なケーキカット問題では、パートナー間で権利が異なることがよくあります。たとえば、リソースが2人の株主に属していて、アリスが8/13、ジョージが5/13を保有している場合などです。これは加重比例性（WPR）の基準につながります。つまり、複数の重みがあります。${\displaystyle w_{i}}$合計が1になるもの、そしてすべてのパートナー${\displaystyle i}$少なくとも一部を受け取るべきである${\displaystyle w_{i}}$資源を独自の評価に基づいて評価する。

対照的に、より単純な比例的なケーキカットの設定では、重さは等しい。${\displaystyle w_{i}=1/n}$すべての人々のために${\displaystyle i}$

WPRの区分を見つけるには、いくつかのアルゴリズムを用いることができる。

すべての重みが共通分母を持つ有理数であると仮定します。${\displaystyle D}$なので、重みは${\displaystyle p_{1}/D,\dots ,p_{n}/D}$、 と${\displaystyle p_{1}+\cdots +p_{n}=D}$各プレイヤーについて${\displaystyle i}$、 作成する${\displaystyle p_{i}}$同じ値尺度を持つクローン。クローンの総数は${\displaystyle D}$彼らの間でケーキを比例配分する。最後に、各パートナーにケーキを渡す。${\displaystyle i}$彼の${\displaystyle p_{i}}$クローン。

ロバートソンとウェッブ^{[ 1 ]： 36は}、2人のパートナーのためのより簡単な手順を示しています。アリスはケーキを切ります${\displaystyle D}$彼女の目には同等のピース。ジョージは${\displaystyle p_{G}}$彼にとって最も価値のある品々、そしてアリスは残りのものを受け取る${\displaystyle p_{A}}$ピース。（これは分割選択手順の応用例です。）

この簡単な手順には D ピースが必要です。${\displaystyle D-1}$分割回数は非常に多くなる可能性があります。例えば、アリスが8/13、ジョージが5/13を受け取る権利がある場合、最初の分割では13-1=12回の分割が必要になります。

必要なクエリ数は${\displaystyle D\lceil \log _{2}(D)\rceil .}$

アリスとジョージでケーキを分けなければならないとします。アリスは8/13、ジョージは5/13を受け取る権利があります。ケーキは次のように分けることができます。

• アリスはケーキを5:3:2:1:1:1の評価比率で6切れに切り分けます。
• ジョージは、アリスが言及した以上の価値があると彼自身が考えるピースに印をつける。

さて、ここで2つの「良い」ケース、つまり、これらの要素を用いて、異なる権利を尊重した加重比例配分を実現できるケースがあります。

それぞれのピースに適切な分け前を与える組み合わせはいくつか存在する。

ケース1：ジョージが3のピースと3つの1のピースのうち2つに印を付けると、合計が5になるピースのサブセットが作成されます。このサブセットはジョージに与えられ、残りはアリスに与えられます。これでジョージは少なくとも5/13、アリスは約8/13のピースを持つことになります。

ケース2：アリスが5サイズのピースと3サイズのピースに印を付けると、合計が8になるピースのサブセットが生成されます。次に、このサブセットがアリスに渡され、残りがジョージに渡されます。これでアリスは8/13、ジョージは少なくとも5/13のピースを持つことになります。

良いケースが唯一可能なケースであることを証明できます。つまり、5:3:2:1:1:1 の任意の部分集合には、合計が 5 になる部分集合が存在するか、その補集合には合計が 8 になる部分集合が存在するかのどちらかです。したがって、上記のアルゴリズムは常に、指定された比率の WPR 配分を見つけます。使用されるカットの数は 5 つだけです。（5 つのカットは 6 つのピースを形成し、それぞれが比例したサイズの組み合わせを構成して各ピースにそれぞれの取り分を与えるため、「分割して選択する」手順を柔軟に使用できます。）

McAvaney、Robertson、Webb ^{[ 1 ] : 36–41 [ 2 ]}は、 Ramsey 分割の概念( Ramsey 理論にちなんで名付けられた) を使用してこのアイデアを一般化しています。

正式には：${\displaystyle k_{1}}$そして$\displaystyle k_2}}$は正の整数であり、分割${\displaystyle P}$の${\displaystyle k_{1}+k_{2}}$ペアのラムゼイ分割と呼ばれる${\displaystyle k_{1},k_{2}}$サブリストの場合${\displaystyle L\subseteq P}$サブリストがあるか、${\displaystyle L}$つまり、${\displaystyle k_{1}}$または、サブリストがあります${\displaystyle P\setminus L}$つまり、$\displaystyle k_2}}$。

上記の例では、${\displaystyle k_{1}=8}$そして${\displaystyle k_{2}=5}$そして分割は5:3:2:1:1:1となり、これはラムゼー分割です。さらに、これはこの場合最短のラムゼー分割であるため、少ない数のカットで済みます。

ラムゼー分割は常に存在する。さらに、常に一意の最短ラムゼー分割が存在する。これは、ユークリッドの互除法の単純な変形を用いて見つけることができる。このアルゴリズムは、次の補題に基づいている。^{[ 1 ]： 143-144}

もし${\displaystyle p_{1}<a<b}$、 そして${\displaystyle P=(p_{1},\dots ,p_{n})}$は分割です${\displaystyle b}$、 そして${\displaystyle P'=(b,p_{1},\dots ,p_{n})}$、 それから${\displaystyle P'}$は分割です${\displaystyle a+b}$。 さらに、${\displaystyle P'}$これはペアのための最小限のラムジー分割です${\displaystyle a,b}$条件付き条件${\displaystyle P}$これはペアのための最小限のラムジー分割です${\displaystyle a,ba}$。

この補題は、以下の再帰アルゴリズムにつながる。

${\displaystyle FindMinimalRamsey(a,b)}$:

1. 入力を次のように並べ替える${\displaystyle a<b}$。
2. 押す${\displaystyle a}$。
3. もし${\displaystyle a=ba=1}$押して${\displaystyle 1,1}$そして終了。
4. もし${\displaystyle ba\neq 1}$、 それから${\displaystyle FindMinimalRamsey(a,ba)}$。

最小限のラムジー分割が見つかれば、それを用いて権利を尊重したWPR分割を見つけることができる。

アルゴリズムには少なくとも${\displaystyle \log _{\phi }\min(a,b)}$カット、 ${\displaystyle \phi =(1+{\sqrt {5}})/2}$は黄金比です。ほとんどの場合、この数値は、${\displaystyle a+b-1}$カット。しかし、もし${\displaystyle a=1}$、 それから${\displaystyle b=a+b-1}$カットが必要です。なぜなら、ペアのラムジー分割は${\displaystyle b,1}$は、${\displaystyle b+1}$1つ。

アリスが8/13、ジョージが5/13を受け取る権利があると仮定します。ケーキは次のように分割できます。

• ジョージはケーキを7対6の比率で2つに切り分けた。
• アリスは、少なくとも表示価格以上の価値があるピースを1つ選びます。次の2つのケースを考えてみましょう。
  • アリスは7を選びます。すると、アリスはさらに1つ受け取る権利があり、残りのピースは5:1の比率で分割されます。
  • アリスは6を選びます。すると、アリスはさらに2つ受け取る権利があり、残りのピースは5：2の比率で分割されます。
• どちらの場合も、残った部分は小さくなり、比率も小さくなります。最終的には比率が 1:1 になり、残ったケーキはカットして選ぶことで分割できます。

基本的な考え方はEven-Pazプロトコルと同様である：^{[ 1 ]： 42-44}${\displaystyle CutNearHalves(a,b)}$:

1. 入力を次のように並べ替える${\displaystyle a<b}$アリスは、${\displaystyle b/(a+b)}$そしてジョージには${\displaystyle a/(a+b)}$。
2. ジョージにケーキをほぼ半分に切ってもらうように頼む。つまり：
   • もし${\displaystyle a+b}$それでもジョージはケーキを、彼にとって等しい2つのピースに切り分けます。
   • もし${\displaystyle a+b}$奇妙なことに、ジョージはケーキを2つに切り分け、その評価比率は${\displaystyle (a+b-1)/2:(a+b+1)/2}$彼の目にはそう映っていた。
3. 少なくとも1つの品物は、ジョージが申告した以上の価値をアリスに与える。その品物をアリスに渡す。
4. アリスが取ったピースが価値のピースだと仮定します${\displaystyle c/(a+b)}$、 どこ${\displaystyle c\in \{(a+b-1)/2,(a+b)/2,(a+b+1)/2)}$。 電話${\displaystyle CutNearHalves(b,ac)}$。

ほぼ半分にカットするアルゴリズムは最大で${\displaystyle \log _{2}\min(a,b)}$カット数が少ないため、ラムゼイ分割アルゴリズムよりも常に効率的です。

ほぼ半分に分割するアルゴリズムは、常に最適とは限りません。たとえば、比率が7:3の場合を考えてみましょう。

• ほぼ半分ずつに分ける場合、少なくとも4回の切り分けが必要になるかもしれません。まず、ジョージが5:5の比率で切り分け、アリスは5つ取ります。次に、アリスが3:2の比率で切り分け、ジョージが2つを選ぶとします。次に、ジョージが2:1の比率で切り分け、アリスが1つを選ぶとします。最後に、残りの部分を分け合って選びます。
• ジョージに6:4の比率で切ってもらうと、より良い結果が得られます。アリスが4を選んだ場合、比率は3:3になり、すぐにカットアンドチョイスを行うことができます。アリスが6を選んだ場合、比率は3:1になります。アリスは2:2の比率で切り、ジョージは2を選び、カットアンドチョイスをもう1ステップ行う必要があります。結局、最大で3回のカットで済みます。

各受給資格率に対して最適な初期カット額をどのように見つけるかは、未解決の問題である。

このアルゴリズムはn個のエージェントに一般化でき、必要なクエリ数は${\displaystyle n(n-1)\lceil \log _{2}(D)\rceil .}$

CsehとFleiner ^{[ 3 ]}は、任意の数のエージェントと任意の権利（非合理的な権利を含む）の間で多次元ケーキを有限回のクエリで分割するアルゴリズムを発表した。彼らのアルゴリズムは、${\displaystyle 2(n-1)\lceil \log _{2}(D)\rceil }$ロバートソン・ウェッブ・クエリ・モデルにおけるクエリ。そのため、エージェント・クローニングやカット・ニア・ハーフよりも効率的である。彼らは、この実行時複雑性が最適であることを証明している。

権利が有理数でない場合、分母が無限大になるため、クローンに基づく方法は使用できません。宍戸と曽は、マークカットチョースと呼ばれるアルゴリズムを発表しました。これは、無理数の権利も処理できますが、カットの回数に制限がありません。^{[ 4 ]}

CsehとFleinerのアルゴリズムは、有限個のクエリで非合理的な権限を扱うようにも適応させることができる。^{[ 5 ]}

必要なクエリの数に加えて、分割が過度に細分化されないように、必要なカットの数を最小限に抑えることも重要です。宍戸・曾アルゴリズムは、最大で$2 ⋅ 3ⁿ⁻²$削減、そして最大で非常に公平な分割 $4 ⋅ 3ⁿ⁻²$カット。^{[ 4 ]}

最悪の場合、少なくとも${\displaystyle 2(n-1)}$分割が必要になる場合がある。Brams 、Jones、Klamler ^{[ 6 ]}はn = 2の例を示している。4 つの連続した領域からなるケーキを、評価が次のようになっているアリスとジョージの間で分割する必要がある。

両方のパートナーのケーキの合計価値は8であることに注意してください。${\displaystyle w_{A}\geq 0.75}$すると、アリスは少なくとも 6 の価値を持つ権利があります。アリスに連結したピースで正当な分け前を与えるには、左端の 3 切れまたは右端の 3 切れのいずれかをアリスに与える必要があります。どちらの場合も、ジョージは 1 の価値しかないピースを受け取りますが、これは彼の正当な分け前である 2 より少ないです。この場合、WPR 分割を実現するには、ジョージにケーキの中央で正当な分け前を与える必要があります。中央では彼の価値が比較的大きいですが、そうするとアリスは 2 つの連結していないピースを受け取ることになります。^{[ 7 ]}

Segal-Halevi ^{[ 8 ]}は、ケーキが円形（つまり、両端が同一）であれば、2人分の連結したWPR分割が常に可能であることを示しています。これは、Stromquist–Woodallの定理から導かれます。この定理を再帰的に適用して正確な分割を見つけることで、最大で を使用したWPR分割を得ることができます。${\displaystyle 2n\cdot (\log _{2}n-1)+2}$nが2のべき乗の場合、切断回数は1回であり、 nが一般的な場合も同様の数となる。

Crew、Narayanan、Spirkle ^{[ 9 ] は}、以下のプロトコルを使用してこの上限を 3 n -4 に改善しました。

• 各エージェントiに、 V _i (0, x )=1/2となるようなxをマークするように指示します。
• エージェントを、獲得したターゲットの強さの昇順に並べ、同点の場合は任意の方法で順位を決定する。
• 上記の順序で薬剤をセットPに追加します。セットP内の薬剤の総重量が1/2を超える直前で停止します。
• Pに追加されなかった最初のエージェントをtと呼び、 t以降のエージェントの集合をQと呼ぶ。さて、
  • P値(0, x )内のすべてのエージェントは少なくとも1/2であり、それらの合計重量は最大で1/2です。
  • Q値( x,1 )内のすべてのエージェントは少なくとも1/2であり、それらの合計重量は最大で1/2です。
  • エージェントt は(0,x) と ( x,1 ) の両方をちょうど 1/2 と評価します。
• PとQの両方が空でない場合、エージェントtはPとQに分割され、各セットの合計重量がちょうど1/2になります。ケーキはxでカットされ、手順は再帰的に進行します。これにより、次の漸化式が得られます（ここでkはエージェントtのクローンを含まないP内のエージェントの数です）。${\displaystyle {\text{Cuts}}(n+1)\leq \max _{1\leq k\leq n-1}(1+{\text{Cuts}}(k+1)+{\text{Cuts}}(n-k+1))}$初期条件を追加する ${\displaystyle {\text{カット}}(2)=2}$主張された数値が得られる $\displaystyle \text{カット}}(n)\leq 3n-4}$。
• より難しいケースは、Pが空の場合です ( Qが空の場合も同様です)。これは、 tの重みが少なくとも 1/2 であり、すべてのエージェントが (0, x ) を最大 1/2 と評価することを意味します。この場合、エージェントt が(0, y )をw _tと正確に評価するようなyを見つけ、以前と同様にエージェントをPとQに分割しようとします。これらのセットのいずれかが再び空の場合、すべてのエージェントが (0, y ) を少なくともw _tと評価することがわかっています。したがって、中間値の定理により、 tではないエージェントの 1 人が(0, z ) をtとまったく同じと評価するような値z が( x , y ) の中に存在しなければなりません。次に、 zでケーキを切り分け、最初のケースと同様に再帰的に処理できます。

必要なカットの正確な回数は未解決の問題である。最も単純な未解決ケースは、エージェントが3人で、重みが1/7、2/7、4/7の場合である。必要なカットの回数が4回（下限値）なのか5回（上限値）なのかは不明である。

Zeng ^{[ 10 ]}は、異なる権利を持つ羨望のないケーキカットの近似アルゴリズムを提示した。

Dall'AglioとMacCheroni ^{[ 11 ]：定理3は} 、エージェントの選好が非加法的な選好関係で記述されている場合でも、特定の公理を満たす限り、異なる権利を持つ比例的なケーキカットの存在を証明した。