比例したケーキカット

最後の減少手順は、 n人に対して開発された最も初期の比例除算手順です。

• パートナーの一人が、少なくとも$\textstyle {\frac {1}{n}}}$。
• 他のパートナーは、現在の作品が実際にはそれ以上の価値があると主張する選択肢がある。$\textstyle {\frac {1}{n}}}$; その場合、残りの値が$\textstyle {\frac {1}{n}}}$彼ら自身の評価によると。
• 最後に現在のピースを減らしたパートナーが、そのピースを受け取ります。
• 残りのケーキは、残りの人たちに同じように分けられます。${\textstyle n-1}$人々。

帰納法により、ルールに従う各パートナーは、以下の値を確実に得られることが証明できる。$\textstyle {\frac {1}{n}}}$他のパートナーが何をするかに関係なく。これは順番にプレイできる離散的な手順です。最悪の場合、${\displaystyle n\times (n-1)/2=O(n^{2})}$アクションが必要です: プレイヤー1人につき1ターンに1つのアクション。ただし、これらのアクションのほとんどは紙上で実行できます。${\textstyle n-1}$ケーキを切り分けることは実際には必要である。したがって、特定の状況下では、すべてのピースが連続していることも可能である。

移動ナイフ法は、最終減少法の連続時間バージョンである。^{[ 1 ]}

• ナイフをケーキの上で、進行方向に対して垂直に、左端から右端に向かって滑らせる。
• 人は、$\textstyle {\frac {1}{n}}}$ケーキの半分はナイフの左側にあります。（コールによって、コールした人が公平だと思うところでナイフが止まります。コールが遅れると、相手はそれまでに多すぎる量を取ってしまう可能性があります。）その後、ケーキがカットされ、その一切れを受け取ります。
• 残りのケーキとパートナーで同じ手順を繰り返します。最後に残ったパートナーが残りのケーキを受け取ります。

フィンクプロトコルは、分割を連続的に小さな「等しい」部分に分割し続けるアルゴリズムである。

• 最初のパートナーは、資源を自分たちが等しいと考える半分に分割する。
• 次に、2番目のパートナーが半分を選び、残りは1番目のパートナーが受け取ります。
• その後、この2人のパートナーはそれぞれ自分の取り分を3分の1ずつに分けます。
• 3人目のパートナーは、結果として得られた部分のうち2つを選びます。1つは1人目のパートナーから、もう1つは2人目のパートナーから選びます。
• パートナーが4人いる場合、最初の3人のパートナーはそれぞれ自分の持ち分を4等分し、このプロセスが続きます。

このプロトコルの利点は、オンラインで実行できることです。新しいパートナーが参加すると、既存の分割が調整され、分割プロセス全体をやり直す必要がありません。欠点は、各パートナーが単一の連結されたピースではなく、多数の連結されていないピースを受け取ることです。

単独分割方式は、単一のエージェントによる均等分割に基づいています。その利点は、対称的で公平なケーキカットを実現するために一般化できる点です。

分割統治戦略を用いることで、O( n  log n )の時間で比例分割を達成することが可能です。^{[ 2 ]}ここでは簡略化のため、偶数人のパートナーの場合の手順を説明しますが、任意の数のパートナーにも容易に適用できます。 

• 各パートナーは、ケーキを2つの等しい価値を持つと考える部分に分ける線を引くように求められます。切り込みは交差してはいけません。これを保証する簡単な方法は、水平線のみ、または垂直線のみを許可することです。
• このアルゴリズムは、 n本の線を昇順に並べ替え、線の中央値でケーキを切ります。例えば、 x  =  1、x  =  3、x  =  5、x  = 9の位置に線を引く4人のパートナーがいる場合、アルゴリズムはx = 4 の位置でケーキを垂直に切ります。  
• アルゴリズムは、2つの半分それぞれに割り当てます。${\textstyle {\frac {n}{2}}}$パートナー – その半分の中に線を引いたパートナー。たとえば、x  =  1 とx  =  3 に線を引いたパートナーは左半分に割り当てられ、他の 2 人のパートナーは右半分に割り当てられます。各半分は、${\textstyle {\frac {n}{2}}}$それを担当するパートナー。

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

分割選択戦略のおかげで、反復回数はO(log n )のみとなり、最後の減少手順におけるO( n )とは対照的です。各反復において、各パートナーは1つのマークを付ける必要があります。したがって、必要なマークの総数はO( n log n )となります。

このアルゴリズムには、点数を減らすために使用できるランダム化バージョンがあります。Even -Pazアルゴリズムを参照してください。

ケーキカットの別の方法としては、 n人の参加者それぞれがn個のピース​​を引いて、各参加者に引いたピースのうち1つを、選ばれたピースが重ならないように渡すという方法がある。

選択手順の簡単な例として、ケーキが1次元の区間であり、各パートナーが連続した1つの区間を受け取りたいと仮定します。以下のプロトコルを使用してください。

1. 各パートナーは、ケーキを自分が等しい価値があると考えるn 個の区間に個人的に分割します。これらは候補ピースと呼ばれます。
2. プロトコルは、${\textstyle n^{2}}$候補となるピースを右端点の昇順（左から右へ）で並べ、右端点が最も左にある区間を選択します。この区間を最終ピースと呼びます。
3. プロトコルは最後のピースを所有者に渡し、それと交差するすべての候補を削除します。次に、ステップ2を残りの区間に対して繰り返します。${\textstyle n-1}$パートナー。

ステップ2の選択ルールは、各反復において、各パートナーの区間が最大で1つしか削除されないことを保証します。したがって、各反復後もパートナーごとの区間の数はパートナーの数と等しく、すべてのパートナーが区間を受け取るまでプロセスは続行できます。^{[ 3 ]}

このプロトコルでは、各パートナーがn 個のクエリに回答する必要があるため、クエリの複雑さは O( n ² ) であり、最後の減少手順と同様です。

比例性基準は、パートナーの権利が均等でない状況にも一般化できます。たとえば、資源が2人の株主に属し、アリスが8/13、ジョージが5/13を保有している場合などです。これは加重比例性（WPR）基準につながります。つまり、合計が1になる複数の重みw _iが存在し、各パートナーiは、自身の評価に基づいて、資源の少なくとも割合w _iを受け取る必要があります。WPR分割を見つけるために、いくつかのアルゴリズムを使用できます。主な課題は、パートナーが2人しかいない場合でも、分割の数が多くなる可能性があることです。

超比例分割とは、各パートナーが厳密に100%を超える金額を受け取る分割のことである。$\textstyle {\frac {1}{n}}}$資源を、彼ら自身の主観的な評価に基づいて判断する。

もちろん、このような区分が常に存在するとは限りません。すべてのパートナーがまったく同じ価値関数を持っている場合、私たちができる最善のことは、各パートナーに正確に$\textstyle {\frac {1}{n}}}$したがって、超比例分配が存在するための必要条件は、すべてのパートナーが同じ価値尺度を持っていないことである。

驚くべき事実は、評価が加算的で非原子的な場合、この条件は十分条件でもあるということです。つまり、価値関数がわずかに異なるパートナーが少なくとも2人いる場合、すべてのパートナーが100%を超える超比例分配が行われます。$\textstyle {\frac {1}{n}}}$。

すべてのピースが繋がっていなければならないという通常の制約に加えて、場合によっては追加の制約が課されることがあります。特に、分割する「ケーキ」が複数の国にまたがる係争地である場合、各国に割り当てられるピースが現在の位置に隣接していることが求められることがあります。このような性質を持つ比例分割は常に存在し、最終縮小プロトコルと等角写像を用いた幾何学的トリックを組み合わせることで見つけることができます。

分割される「ケーキ」が土地や印刷媒体または電子媒体の広告スペースなどの二次元である場合、連結性に加えて、各ピースがいくつかの幾何学的制約を満たすことが求められることがよくあります。たとえば、各ピースが正方形、太い長方形、または一般的に太いオブジェクトであることが求められる場合があります。このような太さの制約がある場合、比例分割は通常存在しませんが、部分比例分割は通常存在し、効率的なアルゴリズムによって見つけることができます。^{[ 7 ]}

比例配分であることに加えて、多くの場合、経済的に効率的であること、つまり社会福祉（すべての主体の効用の合計として定義される）を最大化することも必要となる。

例えば、チョコレート500グラムとバニラ500グラムが入ったケーキを2人のパートナーで分け合う場合を考えてみましょう。片方はチョコレートだけを、もう片方はバニラだけを欲しがっています。多くのケーキの分け方では、各パートナーにチョコレート250グラムとバニラ250グラムを与えます。この分け方は、各パートナーが自分の総価値の0.5を受け取るため比例的であり、正規化された社会的厚生は1になります。しかし、この分け方は非常に非効率的です。なぜなら、チョコレートを片方のパートナーに、バニラをもう片方のパートナーにすべて与えることで、正規化された社会的厚生を2にすることができるからです。

最適な比例配分問題とは、考えられるすべての比例配分の中で、社会福祉を最大化する比例配分を見つける問題です。この問題は現在、ケーキが1次元区間であり、効用密度関数が線形である（つまり、${\textstyle u(x)=Ax+B}$) 一般的にこの問題はNP 困難です。効用関数が正規化されていない場合 (つまり、各パートナーがケーキ全体に対して異なる値を持つことを許容する場合)、この問題は の係数の範囲内で近似することさえ NP 困難です。${\textstyle {\frac {1}{\sqrt {n}}}}$[ ^{8 ]​}

真実性は分割の性質ではなく、むしろプロトコルの性質である。比例分割に関するすべてのプロトコルは弱真実性​​を持つ。なぜなら、各パートナーが自身の真の評価に従って行動すれば、少なくとも$\textstyle {\frac {1}{n}}}$（または${\textstyle {\frac {1}{an}}}$（部分比例議定書の場合）他のパートナーが何をするかに関わらず。たとえ他​​のすべてのパートナーが彼に危害を加えることだけを目的として連合を組んだとしても、彼は保証された割合を受け取ることになる。^{[ 9 ]}

しかし、ほとんどのプロトコルは必ずしも真実性が高いとは言えず、一部のパートナーは保証された分け前よりも多くを受け取るために嘘をつく動機を持つ可能性がある。これは単純な分割選択プロトコルにも当てはまる。切り分け役が選択役の好みを知っていれば、選択役が半分よりわずかに少ないと評価する部分を、切り分け役自身は半分よりはるかに多いと評価する可能性がある。

完全除算を実現するための正当な仕組みが存在する。完全除算は比例除算であるため、これらの仕組みは比例除算を実現するための正当な仕組みでもある。

これらのメカニズムは、超比例除算が存在する場合にそれを提供できるように拡張できます。^{[ 10 ]}

1. 各パートナーに、自身の評価指標全体を報告してもらうように依頼してください。
2. ランダムなパーティションを選択します（詳細は^{[ 10 ]を参照）。}
3. 報告された値尺度に基づいてランダム分割が超比例的である場合は、それを実装する。そうでない場合は、完全な分割を提供するための真実性を備えたメカニズムを使用する。

超比例分割が存在する場合、ステップ 2 でそれが選択される可能性はプラスになります。したがって、すべての正直なパートナーの期待値は厳密に以下よりも大きくなります。$\textstyle {\frac {1}{n}}}$メカニズムが真実であることを確認するために、次の 3 つのケースを検討します。(a) 選択された分割が本当に超比例である場合、嘘をつくことによって起こり得る唯一の結果は、メカニズムが超比例ではないと誤解することです。これにより、メカニズムは完全な分割を実行することになり、嘘をついた人を含むすべてのパートナーにとって不利になります。(b) 選択された分割が超比例ではないのは、嘘をついた人にのみ値を与えるためです。$\textstyle {\frac {1}{n}}}$またはそれ以下であれば、嘘をつくことによる唯一の効果は、メカニズムが分割が超比例的であると認識してそれを実行することであり、これは嘘をついた本人にしか害を与えません。(c) 選択された分割が、他のパートナーに値を与えるため、実際には超比例的ではない場合$\textstyle {\frac {1}{n}}}$またはそれ以下であれば、いずれの場合も分割は実施されないため、嘘をついても全く効果はありません。

分配する資源が望ましくない場合（家事分担など）、比例分配は、各人に最大で$\textstyle {\frac {1}{n}}}$資源の（つまり、不等号の符号が反転する）。

比例配分のためのアルゴリズムのほとんどは、家事分担にも簡単に適用できる。