コンセンサス分裂

コンセンサス分割は、正確な分割とも呼ばれ、^{[1] : 127} 連続したリソース (「ケーキ」)をk個の部分に分割し、異なる嗜好を持つn人の各人が各部分の価値について合意することです。たとえば、半分がチョコレート、半分がバニラのケーキを考えます。アリスはチョコレートだけを評価し、ジョージはバニラだけを評価します。ケーキは 3 つの部分に分割されます。1 つ目はチョコレートの 20% とバニラの 20% が含まれ、2 つ目はチョコレートの 50% とバニラの 50% が含まれ、3 つ目はケーキの残りが含まれます。これは正確な分割 ( k  = 3、n  = 2) であり、アリスとジョージの両方が 3 つの部分をそれぞれ 20%、50%、30% と評価します。いくつかの一般的なバリエーションと特殊なケースは、異なる用語で知られています。

• コンセンサスによる半分分割– ケーキは2つの部分に分割され（k  = 2）、すべてのエージェントはそれらの部分が等しい価値を持つことに同意します。^[2]
• コンセンサス1/ k分割（定数k  > 1）– ケーキはk個のピース​​に分割され、すべてのエージェントは各ピースの価値が等しいことに同意する。^[2]別の用語はコンセンサス分割である。^[3]
• 完全な分割- ピースの数はエージェントの数と等しくなります。つまり、ケーキはn個のピース​​に分割され、すべてのエージェントはすべてのピースの価値が等しいことに同意します。
• ${\displaystyle \varepsilon }$ -ほぼ正確な分割では、任意の定数 に対して、エージェントはピースの値について意見が一致しない可能性がありますが、値の差は最大でも になります。同様に、上記の問題の近似的な変種は、-コンセンサス半減、-コンセンサス 1/ k分割または-コンセンサス分割 、および-完全分割 と呼ばれます。${\displaystyle \varepsilon >0}$ ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon }$
• ナイル川の問題– エージェントが無限に存在する。
• ネックレス分割– 分割するリソースは、有限の数の分割できないオブジェクト (「ビーズ」) で構成されています。

nとk が両方とも有限の場合、コンセンサス分割は常に存在します。しかし、離散プロトコル（クエリ数が有限）ではコンセンサス分割を見つけることはできません。場合によっては、ムービングナイフプロトコルによって正確な分割が見つかることもあります。離散プロトコルでは、ほぼ正確な分割が見つかることもあります。

定義

合計が1となるk個の重みをとする。n人のエージェントがいて、全員がケーキCの価値を1と評価するとする。エージェントiの価値尺度はで表され、これはC上の非原子的尺度であると仮定する。比率の正確な分割は、ケーキをk個のピース​​に分割することである：であり、すべてのエージェントiとすべてのピースjについて、次のようになる： ${\displaystyle w_{1},w_{2},\ldots ,w_{k}}$ ${\displaystyle V_{i}}$ ${\displaystyle w_{1},w_{2},\ldots ,w_{k}}$ ${\displaystyle C=X_{1}\sqcup \cdots \sqcup X_{k}}$

${\displaystyle V_{i}(X_{j})=w_{j}}$

これはコンセンサス分割とも呼ばれます。これは、すべてのエージェントの間でピースjの価値がちょうど であるというコンセンサスがあるためです。^{[1] : 127}特殊なケースとしては、次のようなものがあります。 ${\displaystyle w_{j}}$

• コンセンサス 1/ k分割– の特殊なケース。${\displaystyle w_{1}=\cdots =w_{n}=1/k}$
• コンセンサス半減–およびの特殊なケース。${\displaystyle k=2}$ ${\displaystyle w_{1}=w_{2}=1/2}$
• 完全除算–およびの特殊なケース。${\displaystyle k=n}$ ${\displaystyle w_{1}=\cdots =w_{n}=1/n}$

ほぼ正確な除算

任意の について、比のほぼ正確な除算は次のようになります。 ${\displaystyle \varepsilon >0}$ ${\displaystyle \varepsilon }$ ${\displaystyle w_{1},w_{2},\ldots ,w_{k}}$

${\displaystyle |V_{i}(X_{j})-w_{j}|<\varepsilon }$

つまり、すべてのパートナーの間で、ピースjの価値はほぼ で あり、その差は 未満であるというコンセンサスがあります。^{[1] : 127} 特殊なケースとしては、次のものがあります。 ${\displaystyle w_{j}}$ ${\displaystyle \varepsilon }$

• ${\displaystyle \varepsilon }$ -コンセンサス 1/ k分割– という特殊なケース。${\displaystyle w_{1}=\cdots =w_{n}=1/k}$
• ${\displaystyle \varepsilon }$ -コンセンサス半減–およびの特殊なケース。${\displaystyle k=2}$ ${\displaystyle w_{1}=w_{2}=1/2}$
• ${\displaystyle \varepsilon }$ -完全除算–およびの特殊なケース。${\displaystyle k=n}$ ${\displaystyle w_{1}=\cdots =w_{n}=1/n}$

存在

無制限のカット数

エージェントの評価値が区分的に一定である場合、正確な分割の存在は容易に証明できます。これは、ケーキをR個の領域に分割し、各領域における価値密度が均一であることにすべてのエージェントが同意できることを意味します。例えば、4つの4分の1ずつに異なるトッピングが施された円形のケーキを考えてみましょう。エージェントはそれぞれのトッピングを異なる価値評価を持つかもしれませんが、同じトッピングが施された異なるピースを区別しません。つまり、各エージェントにとっての各ピースの価値は、各領域から得られる量のみに依存します。正確な分割は、次のように実現できます。

• 各領域をk 個のサブ領域に分割し、サブ領域jにはちょうど 個の領域が含まれます。${\displaystyle w_{j}}$
• ピースj を、すべてのR領域のj番目のサブ領域の結合とします。

必要なカットの数は であり、Rは領域の数である。このアルゴリズムは区分線形評価に一般化できる。^[4]${\displaystyle k\cdot R}$

エージェントが可算加法的な 非原子測度を持つという、より一般的な設定においては、正確な分割が存在する。これはデュビンス・スパニエの凸性定理の系である（合意に基づく1/ k分割の存在は、以前にイェジ・ネイマン^[5]によって指摘されている）。しかし、この定理は必要なカットの数については何も述べていない。

Woodall ^{[6]は、区間ケーキの正確な分割を区間の}可算な和として構成できることを示した。直感：上で説明した区分的に同質なケーキの分割手順を考えてみよう。一般に、ケーキは区分的に同質ではない。しかし、値の測度は連続しているので、ケーキをどんどん小さな領域に分割して、それらの領域がどんどん同質になるようにすることができる。のとき、このプロセスは合意分割に収束する。しかし、極限で必要なカットの数は無限である。Fremlinは後に、そのような分割を区間の有限和として構成できることを示した。 ${\displaystyle R\to \infty }$

カットの回数制限

ケーキがn個の地区（部分区間）からなる区間であると仮定し、n人のパートナーそれぞれが1つの地区のみを評価するとします。この場合、ケーキをk個の部分集合にコンセンサス分割するには、各地区を、その地区を評価するパートナーの視点から見て等しいk個の部分に分割する必要があるため、カットが必要になります。このことから、常にこのカット回数でコンセンサス分割が成立するかどうかという疑問が生じます。この問題は、主に1次元のケーキ（区間）に焦点を当てて広く研究されてきました。 ${\displaystyle n\cdot (k-1)}$

まず、コンセンサス・ハーフ化の場合を考えてみましょう。そして、重みは等しいです。カット回数の下限は です 。実際、最大でn回のカットを伴うコンセンサス・ハーフ化は常に存在します。^[7]これはホビー・ライス定理の直接的な系です。また、ボルスク・ウラム定理を用いて証明することもできます。^[8]${\displaystyle k=2}$ ${\displaystyle n\cdot (k-1)=n}$

• カットを使用した区間のすべての分割は、長さのベクトルとして表すことができます。ここで、要素はサブ区間の長さです。${\displaystyle n}$ ${\displaystyle n+1}$
• ベクトルの各要素は、正 (ピース #1 に属する場合) または負 (ピース #2 に属する場合) のいずれかになります。
• すべての分割の集合は球面に同相です。${\displaystyle S^{n}}$
• 関数を次のように定義します。すべてのパーティションxについて、はベクトルであり、そのi番目の要素は、パートナーiに従ったそのパーティションのピース #1 の値から1/2 を引いた値です。${\displaystyle V:S^{n}\to \mathbb {R}^{n}}$ ${\displaystyle V(x)}$
• 関数Vは連続である。さらに、任意のxに対して、である。${\displaystyle V(x)+V(-x)=0}$
• したがって、ボルスク・ウラム定理により、となるx が存在する。この分割では、すべてのパートナーはピース#1（およびピース#2）をちょうど1/2と評価する。${\displaystyle V(x)=0}$

エージェントの選好は測度を用いてモデル化されているが、証明では価値関数が部分集合上で正値または加法的である必要はない。価値関数はボレルシグマ代数上で定義された任意の連続集合関数でよい。したがって、ケーキの部分集合上のパートナーの評価が加法的に分離可能である必要はない。^[2]

ここで、コンセンサス1/ k分割の場合（任意のk >1 かつ重みが等しい場合）について考えてみましょう。Noga Alon は、1987年のネックレス分割問題に関する論文で、次の結果を証明しました。区間 には異なる測度があり、すべて長さに関して絶対連続です。測度 によれば、ネックレス全体の測度は です。すると、区間を部分（必ずしも連続している必要はありません）に分割することができ、各部分の測度 によれば、ちょうど になります。最大で回のカットが必要であり、これは最適です。 ${\displaystyle n}$ ${\displaystyle i}$ ${\displaystyle k\cdot a_{i}}$ ${\displaystyle k}$ ${\displaystyle i}$ ${\displaystyle a_{i}}$ ${\displaystyle (k-1)n}$

ここで、 k = 2 で任意の重みを持つ場合を考えてみましょう。ストロムキストとウッドオール^[9]は、パイ（円形のケーキ）の正確な分割が存在し、各ピースが最大でn -1 個の区間を含むことを証明しました。したがって、最大で 2 n -2 回のカットが必要です。ストロムキスト・ウッドオール定理を参照してください。カットの回数は、一般的な重みに対して本質的に最適です。この定理を再帰的に適用することで、任意のk > 1 と任意の重みに対して、O( nk ) 回のカットで正確な分割を得ることができます。

多次元ケーキ、多くのパートナー、多くのサブセット、等しい重量

ストーン・テューキーの定理は、 n次元空間にn個 の測定可能な「物体」があるとすると、それらすべてを単一の( n −1)次元超平面で半分に分割できる（その測度、つまり体積に関して）ことを述べています。

言い換えれば、ケーキが空間 であり、パートナーの価値測度が有限で任意の次元超平面上でゼロであるならば、各パートナーにとって値がちょうど1/2である半空間が存在する。したがって、単一のカットによるコンセンサス分割が存在する。 ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle n-1}$

この定理の元のバージョンは、ケーキの次元数がパートナーの数と等しい場合にのみ有効です。例えば、この定理を用いて3次元のサンドイッチを4人以上のパートナーに分割することはできません。

しかし、そのような分割を可能にする一般化が存在する。それらは超平面ナイフではなく、より複雑な多項式曲面を使用する。^[10]

これらの多次元的結果には離散的な適応も存在する。^[11]

正確な割り算の計算

離散的な手順では不可能

有限個のクエリで正確な除算を計算することは不可能であり、たとえn =2エージェントとk =2ピースしかなく重みが1/2に等しい場合でも不可能である。^{[1] ：103–104}これは、離散アルゴリズムを使用して達成できる最良の方法は、ほぼ正確な除算であることを意味する。

証明：プロトコルがステップkにあるとき、最大でk 個のピース​​の集合を持つ。正確な割り算を行うには、プロトコルは正確な部分集合、つまり両方のパートナーがちょうど 1/2 と評価するピースの部分集合を見つけなければならない。任意のkについて、ステップkで正確な部分集合が存在しない状況があり、そのためプロトコルが無限に継続する可能性が あることを証明しよう。

最初は、両方のパートナーが1と評価するピースは1つだけなので、正確な部分集合は存在しません。1ステップ後、せいぜい片方のパートナー（例えばアリス）がケーキを切る選択肢を持つことになります。アリスがケーキを2つのピースに切ったとしても、彼女にとっては同じ価値であっても、ジョージにとっては異なる価値を持つ可能性があるため、やはり正確な部分集合は存在しません。

今、ステップkにいて、 k個のピース​​があると仮定します。一般性を失うことなく、各ピースは両方のパートナーにとって0以外の価値を持つと仮定できます。これは、例えばアリスが0と評価したピースを切った場合、ジョージも同じピースを0と評価する可能性があるためです。そのため、このピースを捨てて、他のピースの処理を続けることができます。

異なる部分集合の総数は、現在 2 ^kであり、帰納法の仮定により、どれも正確ではない。ステップkで、プロトコルは、アリスかジョージのどちらかに、あるピースを 2 つのピースに切断するように依頼することができる。切断者はジョージであり、彼がピース X を 2 つのサブピース X1 と X2 に切断すると仮定する。ここで、部分集合の総数は 2 ^{k +1}である。その半分はすでに存在しており、仮定によりそれらは正確ではないため、プロトコルが正確な部分集合を見つける唯一のチャンスは、新しい部分集合を調べることである。それぞれの新しい部分集合は、ピース X が X1 または X2 に置き換えられた古い部分集合から作られる。ジョージは切断者であるため、これらの部分集合のいずれかが彼にとって正確な部分集合になるように切断することができる (たとえば、ピース X を含むある部分集合の値が 3/4 だった場合、ジョージは、X1 の値が 1/4 であると判断して X を切断し、新しい部分集合の値がちょうど 1/2 になるようにすることができる)。しかし、ジョージはアリスの値を知らず、カットする際にそれを考慮することができません。したがって、アリスにとって、X1とX2が取り得る値は無数に存在します。新しい部分集合の数は有限であるため、アリスにとって1/2の値を持つ新しい部分集合が存在しないケースは無限にあり、したがって、新しい部分集合はどれも完全ではありません。

可動ナイフ手術

2 人のエージェントは、オースティンのムービングナイフ手順を使用して合意分割を達成できます。

最も単純なケースは、重みが1/2の場合、つまり両者がケーキの価値の半分と合意するピースを切ろうとしている場合です。これは次のように行われます。片方のエージェントが2本のナイフをケーキの上を左から右へ動かし、ナイフ間の価値が常にちょうど1/2になるようにします。ある時点で、ナイフ間のピースの価値がもう片方のパートナーにとってもちょうど1/2になることが（中間値定理によって）証明できます。もう片方のエージェントがその時点で「ストップ！」と叫び、ピースが切られます。

同じプロトコルを用いて、両エージェントがその値がちょうど であると合意するピースをカットすることもできます。このようなピースを複数組み合わせることで、任意の比率が有理数となるようなコンセンサス分割を実現できます。ただし、これには多数のカットが必要になる場合があります。 ${\displaystyle 1/n}$

合意に基づく分割を実現するより良い方法は、ケーキの両端点を特定し、それを円のように扱うことです。つまり、右のナイフが右側に到達したら、すぐに左側に移動し、ナイフの間のピースは実際には右のナイフの右側のピースと左のナイフの左側のピースの和集合になります。この方法により、あらゆる に対して合意に基づく分割を見つけることができます。一方のエージェントは、ナイフをケーキの周りで循環的に動かし、常にナイフ間の価値がちょうどpになるようにします。ある時点で、ナイフ間のピースのもう一方のパートナーにとっての価値もちょうどpになることを証明できます。^[12]その時点でもう一方のエージェントが「ストップ！」と叫び、ピースがカットされます。これには2回のカットのみが必要です。 ${\displaystyle p\in [0,1]}$

上記の手順を繰り返し適用することで、 n =2人のパートナーと任意のk >1のサブセット間で合意に基づく分割を実現できます。カットの数は です。 ${\displaystyle 2(k-1)}$

2015年現在、このムービングナイフ法をn >2エージェントに一般化した方法は知られていない。^[13]

無制限のカット数によるほぼ正確な除算の計算

クラムアンドパック手順

任意の に対して、各パートナーが持っている値の差が 未満であると信じるピースを各パートナーに与えることができる。つまり、すべてのiとすべてのjに対して、次のようになる。^{[1] : 127}${\displaystyle \varepsilon >0}$ ${\displaystyle \varepsilon }$

${\displaystyle |V_{i}(X_{j})-w_{j}|<\varepsilon }$

ほぼ正確な分割手順には、crumbingとpacking の2 つのステップがあります。

クラムステップ：目標は、各パートナーが各クラムに十分小さな価値を割り当てるように、ケーキを小さな破片（「クラム」）にカットすることです。これは次のように行われます。k を特定の定数とします。パートナー #1 に、ケーキをk 個のピース​​に切り分け、各ピースの価値が 1/ k以下になるようにしてもらいます。パートナー #2 には、必要に応じて（最大k -1 回）切り分けてもらい、各ピースの価値が 1/ k以下になるようにします。もちろん、これらの新しいピースは、パートナー #1 にとって依然として最大 1/ k以下です。パートナー #3、#4、…、# nとこれを繰り返します。最後に、n人全員のパートナーが、結果として得られる各クラムの価値を 1/ k以下と評価します。

パッキングステップ：ここでの目標は、各サブセットjの値の合計がw _jに近くなるように、パンくずをn 個のサブセットに分割することです。ここでは、重みが 1/2 の場合の、2 人のパートナー（アリスとジョージ）に対するパッキングステップの直感的な説明を示します。^{[1] : 68–71}

1. 空のボウルを用意します。
2. パン粉を1つボウルに入れます。
3. どちらかのパートナーのボウルの中の値が半分以上になった場合は、そのパートナーにボウルを渡し、残りのパンくずをもう一方のパートナーに渡します。
4. そうでない場合（ボウルの中の値が両方のパートナーにとって1/2未満の場合）、ボウルの中の値がアリスにとっての値がジョージにとっての値よりも大きい場合、ジョージにとっての値がアリスにとっての値よりも大きいクラムを探します（すべてのクラムの合計がアリスとジョージの両方にとって1であるため、そのようなクラムは必ず存在します）。このクラムをボウルに加え、ステップ2に戻ります。

帰納法によって、アリスとジョージの間のボウルの価値の差は常に最大でも1/ kであることが証明できます。したがって、どちらかのパートナーがボウルを受け取った場合、両方のパートナーにとってのボウルの価値は1/2-1/ kから1/2+1/ kの間になります。

形式的には、各駒はパートナーごとに1つの値のベクトルとして表現できます。各ベクトルの長さは有限で、つまり各ベクトルvについて:となります。目標は、各パートナーjについて、すべての要素がw _jに近いベクトルを作成することです。そのためには、ベクトルを部分集合に分割し、各部分集合jのベクトルの和が、すべての要素がw _jであるベクトルに十分近くなるようにする必要があります。これは、V.Bergström の定理^{[14] [1] : 126–128 によって可能になります。}${\displaystyle ||v||\leq {\sqrt {n}}/k}$

Crumb-and-Pack 手続きは、 Robertson-Webb プロトコルのサブルーチンです。Robertson-Webb プロトコルは、ほぼ正確かつ羨望の的にならないケーキカットのような割り算を生成します。

ブラムスとテイラーは、クラム・アンド・パック法について異なる説明をしている。^[15]

制限された数のカットによるほぼ正確な除算の計算

制限されたカット数に関するほとんどの結果は、重みが等しい場合に焦点を当てています。

2つのサブセット（コンセンサス半減）

ε近似のコンセンサス半減法は、タッカーの補題に基づくアルゴリズムによって計算できます。タッカーの補題は、ボルスク＝ウラム定理の離散版です。^[2]このアルゴリズムの適応により、この問題は計算量クラスPPAに属することが示されます。^[16]これは、任意の有界かつ非アトミックな評価値に対しても当てはまります。しかし、このアルゴリズムの実行時間は、問題のパラメータに対して指数関数的に増加する可能性があります。実際、コンセンサス半減法はいくつかの点で計算的に困難です。

まず、ε がnに関して逆指数関数的（つまり、1/ εがnの指数関数的）であることが許されると仮定する。すると、 ε近似のコンセンサス半減法を見つけることはPPA困難となる。以下の追加条件があっても困難性は維持される。^[16]

• エージェントは区分定数評価値を持つ。問題への入力には、各エージェントの区分定数評価値のエンドポイントと値が含まれる。また、すべての数値（近似精度εを含む）は2進数で表現される。

• 区分的に定数的な評価における断片の数はnの多項式です(値自体はnの指数関数的である場合があります)。
• 近似係数εはnの逆多項式となることが許される。^[17]
• エージェントの評価は2つのブロックのみで区分的に均一である（ただし、エージェントが1つのブロックで区分的に均一な評価を持つ場合、問題はnカットではパラメータ化された多項式時間で、任意の定数dに対して2n - dカットでは多項式時間で解くことができる） 。^[18]
• エージェントの数は定数であり、少なくとも3つである（ただし、エージェントが2つの場合は多項式時間で解決できる）。^[19]

次に、 ε が定数（nに依存しない）であると仮定する。すると、ε近似のコンセンサス半減問題を求めることはPPAD困難となり、これは理論的にはPPA困難よりも弱い。証明は、ε近似の一般化回路問題からの帰着によって行われる。以下の条件下においても困難性は成立する。

• 評価は区分的に一定です。
• 定数倍の追加カットを使用することが許されている（つまり、定数dに対してn + dのカットを使用してnエージェントのコンセンサス半減を探索する）。^[20]
• εが定数のとき、 ε近似コンセンサス半減法がPPA困難（PPA困難はPPAD困難よりも強い）であるかどうかは不明である。^[16]
• また、 n -1回のカットによるε近似コンセンサス半減法が存在するかどうかを判定することは、εが定数であってもNP困難である。証明は3SATからの還元によって行われる。^[20]

εが定数の場合、2種類の近似値を多項式時間で計算できます。これらのアルゴリズムは、一般的な加法的な評価値（必ずしも区分定数ではない）に対して機能します。評価値は、ロバートソン・ウェッブクエリモデルのクエリを用いてアクセスされます。これには、 n個の評価値すべての合計を求めるマーククエリも含まれます。^[3]以下の近似値が得られます。

• カットを使用して、各エージェントが各部分を少なくとも 1/ 2nと評価するパーティションを見つけます。${\displaystyle n}$
• オンライン アルゴリズムのカットを使用するか、オフライン アルゴリズムのカットを使用して、各エージェントが各部分を 1/2 ± εと評価するパーティションを見つけます。 ${\displaystyle O((n\log {n})/(\varepsilon ^{2}))}$ ${\displaystyle n\cdot \lceil 2+\log _{2}(1/\epsilon )\rceil }$
  • 任意の定数dに対するn + dカットのPPAD困難性と、 2n +O(log( ε))の多項式時間アルゴリズムとの間にはギャップがあることに注意してください。

• εが定数またはnの逆多項式であるとき、ε近似コンセンサス半分化はネックレス分割問題と計算的に等価であり、それぞれが多項式時間で他方に還元できる（これはネックレス分割がPPAD困難であることを意味する）。^[16]
• 正確な解を求める場合、コンセンサス半減法ははるかに困難です。n回のカットで解を見つけることはFIXP困難であり、 n -1回のカットで解が存在するかどうかを判断することはETR完全です。^[21]
• エージェントの評価が代数回路で表現される場合、ε近似合意半減法は、ボルスク＝ウラム探索問題の正確な解の近似値を計算することと多項式時間で等価である。これは、ボルスク＝ウラム定理によって存在が保​​証される問題の解を含むFIXPのスーパークラスである複雑性クラスBUに対して完全であることを意味する。^[22]

分割する資源がケーキではなく、分割可能な資源の集合である場合、問題はより簡単になります。^[23]

• 加法的効用を持つエージェントの場合、最大でn回のカットで合意半減を計算する多項式時間アルゴリズムと、最大で( k -1) n回のカットで合意k分割を計算する多項式時間アルゴリズムが存在する。
• 与えられたインスタンスに対して、最適なカット数でコンセンサス半減を計算することはNP困難です。さらに、最大でOPT+ n -1回のカットでコンセンサス半減を計算することもNP困難です。ここでOPTはインスタンスに対する最適なカット数です。
• エージェントの効用が確率分布から引き出されるとき、コンセンサス半減にはn回のカットがほぼ確実に必要になります。
• 非加法的な単調な効用を持つエージェントの場合、コンセンサス半減は依然として PPAD 困難ですが、固定数のエージェントに対しては多項式時間アルゴリズムが存在します。

多くのサブセット（コンセンサス1/k分割）

計算の観点から見ると、に対するカットを用いた正確な除算の計算についてはあまり解明されていません。ただし、より多くのカットを使用できることから、この問題は必ずしも に対するよりも難しいわけではないことに注意してください。現在わかっていることは以下のとおりです。 ${\displaystyle (k-1)n}$ ${\displaystyle k\geq 3}$ ${\displaystyle k\geq 2}$

• 問題はPPA- kが任意のkに対して存在することである。^[24]
• この問題はk = 3の場合にはPPA困難であり、1/ εはnの指数関数となる可能性がある。^[18]

ロバートソン・ウェッブクエリの多項式数を使用して2種類の近似値を計算できます。^[3]

• オンライン アルゴリズムで、カットを使用して、各エージェントが各部分を少なくとも 1/ knと評価するパーティションを見つけます。 ${\displaystyle (k-1)n}$
  • 1/ knを改善できるかどうかは未知数である。特に、各エージェントが各部分を少なくとも 1/ c ( k ) と評価するような効率的な（オンラインまたはオフラインの）アルゴリズムが存在するかどうかは未知数である。ここで c(k) はkの関数（ nに依存しない）であり、カットを用いている。${\displaystyle (k-1)n}$
• 各エージェントが各部分を1/ k ± εで評価するようにパーティションを見つける。オンラインアルゴリズムのカットを使用するか、カットを使用する。^{[3] ：Sec.6}${\displaystyle O({\frac {kn\log {(kn)}}{\varepsilon ^{2}}})}$ ${\displaystyle n\cdot (k-1)\cdot \lceil 2+\log _{2}(3k/\epsilon )\rceil }$
  • カット回数を改善できるかどうかは未知数です。オンラインアルゴリズムの場合、 k =2のときのカット回数の下限はであるため、対数ギャップが生じます。${\displaystyle O({\frac {n}{\varepsilon ^{2}}})}$

nエージェント に対するε近似コンセンサス半減法の計算結果

#ピースk	エージェント数n	精度 1/ ε	# カット	評価	状態
2	${\displaystyle n}$	${\displaystyle O({\text{poly}}(n))}$	${\displaystyle n}$	連続した	PPAでは[2] [20]
2	${\displaystyle n}$	${\displaystyle \オメガ (1)}$	${\displaystyle n+d}$ 、${\displaystyle d\geq 0}$	区分定数	PPADハード; [20] PPA がハードかどうか を開きます。
2	${\displaystyle n}$	${\displaystyle \Omega ({\text{poly}}(n))}$	${\displaystyle n+n^{1-d}}$ 、${\displaystyle d>0}$	区分的に均一 2つのブロックで	PPA-hard。[18] (PPAD-hard [20] ; PPA-hard for ; [16]${\displaystyle \varepsilon \in \Omega (2^{n})}$ 区分定数評価ではPPA困難である[17]）。
2	${\displaystyle n}$	${\displaystyle O({\text{poly}}(n))}$	${\displaystyle n}$	区分的に均一 1ブロック	パラメータ化された多項式。[18]
2	${\displaystyle n}$	${\displaystyle O({\text{poly}}(n))}$	${\displaystyle 2n-d}$ 、${\displaystyle d\geq 0}$	区分的に均一 1ブロック	多項式[18]
2	${\displaystyle n}$	${\displaystyle \Omega (1)}$	${\displaystyle n-1}$	区分定数	NP困難であり、存在を決定することができない。[20]
2	${\displaystyle n}$	${\displaystyle \Omega (1)}$	${\displaystyle 2n}$	区分定数	オープン。[20]
2	${\displaystyle n}$	?	${\displaystyle n}$	代数回路	強近似はBU a完全である。[22]
2	${\displaystyle n}$	∞ [正確]	${\displaystyle n}$	代数回路	FIXP困難。[21]
2	${\displaystyle n}$	∞ [正確]	${\displaystyle n-1}$	代数回路	ETRは存在を決定するために完全である。[21]
n固定:
2	2	${\displaystyle O({\text{poly}}(n))}$	${\displaystyle n}$	単調	多項式; 多項式#クエリ。[19]
2	3	${\displaystyle O({\text{poly}}(n))}$	${\displaystyle n}$	単調	PPA困難; 少なくとも指数関数的なクエリ数。[19]
2	2	${\displaystyle O({\text{poly}}(n))}$	${\displaystyle n}$	一般的な	PPA困難; 少なくとも指数関数的なクエリ数。[19]
k >2:
3	${\displaystyle n}$	${\displaystyle O({\text{poly}}(n))}$	${\displaystyle 2n}$	区分定数	PPADハード。[18]
プライムパワー	${\displaystyle n}$	${\displaystyle O({\text{poly}}(n))}$	${\displaystyle (k-1)n}$	区分定数	PPA- kでは[24]

他の基準との比較

均等な重み付け（ ）による正確な分割は、特に比例的であり、嫉妬がなく、公平である。しかし、必ずしもパレート効率的であるわけではない。なぜなら、多くの場合、主観的な評価を利用して、すべてのパートナーが公平な取り分よりも多くを受け取るように資源を分割することが可能だからである。 ${\displaystyle 1/n}$ ${\displaystyle 1/n}$

異なる重さの正確な分割は必ずしも公平ではありません。冒頭の例に戻ると、20%のピースをアリスに、残りの2つのピース（50%と30%）をジョージに与えるとしたら、これは明らかにアリスにとって不公平です。しかし、このような分割は、公平なケーキカットのサブルーチンとして使用できます。

全会一致の比例性

家族間のケーキカット問題^[25]では、n人のエージェントがk人の家族にグループ化されており、目標はケーキをk個に分割し、各家族に1個ずつ割り当てることである。この設定における自然な公平性の基準は全員一致の比例性であり、これはすべての家族のすべてのメンバーが自分の家族の取り分を少なくとも1/ kと評価することを意味する（他の基準と関連問題については、グループ間の公平な分割を参照）。この問題は、次の意味で正確な分割と同等である。

• 任意のnとkに対し、k個のファミリーにグループ化されたn ( k -1)+1 個のエージェント間の全会一致比例分割の解は、 k個のピース​​（および等しい重み）を持つn個のエージェント間の正確な分割の解を意味する。特に、全会一致比例分割には少なくともn -1 回のカットが必要であり、近似的な全会一致比例分割を求めることは PPA 困難であることを意味する。
• 任意のnとkに対し、 n 個のエージェントとk 個のピース​​間の正確な分割の解は、 k個のファミリーにグループ化された n+1 個のエージェント間の全会一致比例分割の解を意味する。特に、これは正確な全会一致比例分割が ( n -1)( k -1) 回のカットで実行可能であり、近似的な全会一致比例分割を求めることが PPA に含まれることを意味する。カットの数はk =2 ファミリーではタイトであるが、k >2 ではタイトではない。^[25]

真実のメカニズム

合意に基づく分割アルゴリズムは、パートナーが報告する価値尺度に依存します。パートナーがアルゴリズムの仕組みを知っていれば、自分の重み以上のものを得るために、価値尺度について嘘をつくインセンティブを持つ可能性があります。これを防ぐには、真実に基づくメカニズムを使用する必要があります。^{[4] [26]}

最も単純で真実味のある分割のメカニズムは、パートナーを一人ランダムに選び（確率は重みによって決まる）、ケーキを丸ごと渡すというものである。このメカニズムは、質問をしないため、自明に真実である。さらに、これは期待値のコンセンサスである。つまり、各パートナーの期待値はまさにその重みであり、これはあらゆる価値尺度において真である。しかし、結果として得られる分割は、もちろんコンセンサス分割ではない。

すべての重みが 1/ nの場合に機能する、より真実性の高いメカニズムは、コンセンサス分割を見つけるための既存のアルゴリズム (またはオラクル) があれば構築できます。

1. 各パートナーに価値尺度を報告してもらいます。
2. 既存のアルゴリズム/オラクルを使用して、パートナーによって報告された値関数に従って、n 個の部分すべてが正確に 1/ nとなるパーティションを生成します。
3. コンセンサス パーティションに対してランダムな順列を実行し、各パートナーにピースの 1 つを渡します。

ここで、各パートナーの期待値は、報告された価値関数に関わらず1/ nのままであるため、メカニズムは依然として真実である。つまり、嘘をつくことでパートナーが得るものは何もない。さらに、真実を語るパートナーは、確率1で正確に1/ nの値が保証される（期待値だけでなく）。したがって、パートナーは真の価値関数を明らかにするインセンティブを持つ。

参照:誠実なケーキカット。

要約表

名前	タイプ	ケーキ	評価[27]	#パートナー ( n )	#サブセット ( k )	#カット	重み
オースティン	移動ナイフ手術	間隔	欠点	2	多くの	${\displaystyle 2(k-1)}$ （最適）	どれでも
区分的に同質な	離散手順	区分的に同質な	コン+追加+引き	多くの	多くの	地区数	どれでも
デュビンス・スパニエ	存在証明	どれでも	コン+追加	多くの	多くの	無制限	どれでも
コンセンサス半減	無限の手順	間隔	欠点	多くの	2	n（最適）	等しい
ネックレス分割	存在証明	間隔	欠点(+追加?)	多くの	多くの	${\displaystyle n(k-1)}$ （最適）	等しい
ストロムクイスト・ウッドール	存在証明	丸	コン+追加	多くの	2	${\displaystyle 2n-2}$ （一部の重量には最適）	どれでも
ストーン・テューキー	存在証明	n次元	欠点(+追加?)	n	2	1つの半平面	等しい
クラムアンドパック	ほぼ正確な手順	どれでも	コン+追加	多くの	多くの	無制限	どれでも

参照

• ナイル川の問題

参考文献

1. ロバートソン、ジャック、ウェッブ、ウィリアム (1998). 『ケーキカットアルゴリズム：できるなら公平に』 マサチューセッツ州ネイティック：AKピーターズ社. ISBN 978-1-56881-076-8LCCN 97041258. OL  2730675W  .
2. シモンズ、フォレスト W.;スー、フランシス・エドワード (2003)。 「ボルスク・ウラムとタッカーの定理によるコンセンサス二分化」。数学社会科学。45 : 15–25。CiteSeerX 10.1.1.203.1189 。​​土井：10.1016/S0165-4896(02)00087-2。 
3. Alon, Noga ; Graur, Andrei (2020-06-30). 「小節とネックレスの効率的な分割」. arXiv : 2006.16613 [cs.DS].
4. Chen, Yiling ; Lai, John K.; Parkes, David C.; Procaccia, Ariel D. (2013). 「真実、正義、そしてケーキカット」. Games and Economic Behavior . 77 (1): 284– 297. doi :10.1016/j.geb.2012.10.009. S2CID  2096977.
5. ジェルジのネイマン (1946 年 1 月)。 「存在の理論」。科学アカデミーのコンテス。222 : 843–845 .
6. Woodall, DR (1980). 「ケーキを公平に分ける」. Journal of Mathematical Analysis and Applications . 78 : 233–247 . doi : 10.1016/0022-247x(80)90225-5 .
7. Goldberg, Charles H.; West, Douglas B. (1985). 「円彩色の二分法」. SIAM Journal on Algebraic and Discrete Methods . 6 : 93–106 . doi :10.1137/0606010.
8. Alon, Noga; West, Douglas B. (1986). 「ボルスク・ウラム定理とネックレスの二分法」(PDF) . Proceedings of the American Mathematical Society . 98 (4): 623. doi : 10.1090/s0002-9939-1986-0861764-9 .
9. Stromquist, Walter; Woodall, DR (1985). 「複数の測度が一致する集合」. Journal of Mathematical Analysis and Applications . 108 : 241–248 . doi :10.1016/0022-247x(85)90021-6.
10. B. Grünbaum (1960). 「超平面による質量分布と凸体の分割」. Pacific J. Math . 10 (4): 1257– 1261. doi : 10.2140/pjm.1960.10.1257 . MR  0124818.
11. de Longueville, Mark; Živaljević, Rade T. (2008). 「多次元ネックレスの分割」. Advances in Mathematics . 218 (3): 926– 939. arXiv : math/0610800 . doi : 10.1016/j.aim.2008.02.003 .
12. フィッシャー、ダニエル. 「ケーキを2人で任意の比率で分ける合意」. Math.SE. 2015年6月23日閲覧。
13. n人のパートナーそれぞれに、ちょうどその価値の駒を与える一般化があります。しかし、これは合意に基づく分割ではありません。なぜなら、パートナーは自分に割り当てられた駒以外の駒の価値について合意しない可能性があるからです。オースティンのムービングナイフ法#パートナーが多数いる場合を参照してください。${\displaystyle 1/n}$
14. V. バーグストロム (1930)。 「Zwei Sätze uber ebene Vectorpolygone」。ハンブルギッシェ・アブハンドルンゲン。8 : 205–219 .
15. Brams, Steven J.; Taylor, Alan D. (1996). Fair Division [ From cake-cutting to dispute resolution ]. Cambridge University Press. pp.  131– 133. ISBN 978-0-521-55644-6。
16. Filos-Ratsikas, Aris; Goldberg, Paul W. (2018-06-20). 「コンセンサス半減はPPA完全である」.第50回ACM SIGACTコンピューティング理論シンポジウム議事録. STOC 2018. ニューヨーク、ニューヨーク州、米国: Association for Computing Machinery. pp.  51– 64. arXiv : 1711.04503 . doi :10.1145/3188745.3188880. ISBN 978-1-4503-5559-9. S2CID  8111195。
17. Filos-Ratsikas, Aris; Goldberg, Paul W. (2019-06-23). 「ネックレスの分割とハムサンドイッチの二等分に関する計算の複雑さ」. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. STOC 2019. ニューヨーク、ニューヨーク州、米国: Association for Computing Machinery. pp.  638– 649. doi :10.1145/3313276.3316334. ISBN 978-1-4503-6705-9. S2CID  44085263。
18. Filos-Ratsikas, Aris; Hollender, Alexandros; Sotiraki, Katerina; Zampetakis, Manolis (2020-07-13). 「コンセンサス半減期：今後、より容易になる可能性はあるか？」第21回ACM経済・計算会議議事録. EC '20. ニューヨーク州ニューヨーク：Association for Computing Machinery. pp.  381– 399. arXiv : 2002.11437 . doi :10.1145/3391403.3399527. hdl :1721.1/146185. ISBN 978-1-4503-7975-5. S2CID  211505917。
19. Deligkas, Argyrios; Filos-Ratsikas, Aris; Hollender, Alexandros (2021-07-18). 「二人は仲良し、三人は群集：一定数のエージェントに対するコンセンサス半減法」.第22回ACM経済・計算会議議事録. EC '21. ニューヨーク州ニューヨーク：米国計算機協会. pp.  347– 368. arXiv : 2007.15125 . doi :10.1145/3465456.3467625. hdl :20.500.11820/f92c933a-c6bd-4f93-b56f-de38970860e7. ISBN 978-1-4503-8554-1. S2CID  220871193。
20. フィロス＝ラツィカス、アリス;フレデリクセン、ソーレン・クリストファー・スティル。ゴールドバーグ、ポール W.張潔 (2018-08-08)。 「コンセンサス半減の硬度結果」。arXiv : 1609.05136 [cs.GT]。
21. Deligkas, Argyrios; Fearnley, John; Melissourgos, Themistoklis; Spirakis, Paul G. (2021-05-01). 「コンセンサス半減法とBorsuk-Ulam定理の正確な解の計算」. Journal of Computer and System Sciences . 117 : 75–98 . arXiv : 1903.03101 . doi :10.1016/j.jcss.2020.10.006. ISSN  0022-0000. S2CID  228908526.
22. Batziou, Eleni; Hansen, Kristoffer Arnsfelt; Høgh, Kasper (2021-03-07). 「強い近似コンセンサス半減期とBorsuk-Ulam定理」. arXiv : 2103.04452 [cs.GT].
23. Goldberg, Paul W.; Hollender, Alexandros; Igarashi, Ayumi; Manurangsi, Pasin; Suksompong, Warut (2022). 「アイテム集合のコンセンサス半減法」.オペレーションズ・リサーチ数学. 47 (4): 3357– 3379. arXiv : 2007.06754 . doi :10.1287/moor.2021.1249. S2CID  246764981.
24. Filos-Ratsikas, Aris; Hollender, Alexandros; Sotiraki, Katerina; Zampetakis, Manolis (2021-01-01)、「Modulo-p 引数の位相的特徴付けとネックレス分割への影響」、2021 ACM-SIAM 離散アルゴリズムシンポジウム (SODA) の議事録、産業応用数学協会、pp.  2615– 2634、doi : 10.1137/1.9781611976465.155、ISBN 978-1-61197-646-5、S2CID  214667000
25. Segal-Halevi, Erel; Nitzan, Shmuel (2019-12-01). 「家族間の公平なケーキカット」. Social Choice and Welfare . 53 (4): 709– 740. arXiv : 1510.03903 . doi :10.1007/s00355-019-01210-9. ISSN  1432-217X. S2CID  1602396.
26. Mossel, Elchanan; Tamuz, Omer (2010). 「真実かつ公正な分割」.アルゴリズムゲーム理論. コンピュータサイエンス講義ノート. 第6386巻. pp.  288– 299. arXiv : 1003.5480 . doi :10.1007/978-3-642-16170-4_25. ISBN 978-3-642-16169-8. S2CID  11732339。
27. パートナーの価値関数に関する前提条件。前提条件が少ないほど、結果はより一般化されます。Con=連続が最も一般的であり、Con+Add=加法はそれほど一般的ではありません。Con+Add+Pwl=区分線形は最も一般的ではありません。