オースティンのムービングナイフ手術

オースティンのムービングナイフ手順は、ケーキを公平に分割するための手順です。n人のパートナーそれぞれに、そのパートナーがケーキとまったく同じ価値を持つケーキの一部を割り当てます。これは、各パートナーに少なくともケーキの一部を与えるが、一部のパートナーにはより多くのケーキを与える可能性がある比例分割手順とは対照的です。 ${\displaystyle 1/n}$ ${\displaystyle 1/n}$

のとき、オースティンの手順によって生成される分割は正確な分割であり、また、嫉妬なしの分割です。さらに、両方のパートナーがちょうど 1/ kとして評価する任意の個数kのピースにケーキを分割することができます。したがって、パートナー間でケーキを任意の分数で分割することができます (たとえば、アリスに 1/3、ジョージに 2/3 を与えるなど)。 ${\displaystyle n=2}$

のとき、各パートナーは自分の駒を としてのみ評価し、他の駒を として評価する可能性がある ため、分割は正確ではなく、嫉妬のない分割でもありません。${\displaystyle n>2}$${\displaystyle 1/n}$

オースティンの手順で使用される主な数学的ツールは中間値定理（IVT）である。^{[1] [2] [3] : 66}

基本的な手順は、パートナーがケーキをそれぞれがちょうど半分ずつ取れるように分割することです。 ${\displaystyle n=2}$

説明のために、2 人のプレーヤーをアリスとジョージと呼び、ケーキは長方形であると仮定します。

• アリスは、ケーキの左側にナイフを 1 本置き、ケーキを 2 つに分けると思われる右側に、ナイフと平行に 2 本目のナイフを置きます。
• アリスは、2 本のナイフの間の部分にケーキの価値の半分が常に含まれるように、両方のナイフを右に動かします (ナイフ間の物理的な距離は変わる可能性があります)。
• ジョージは、ケーキの半分がナイフの間にあると思ったときに「ストップ!」と言います。ジョージがどこかの時点で「ストップ」と言うことができると、どうすれば確信できるでしょうか。アリスがケーキの端まで到達した場合、彼女は右のナイフが始まった場所に左のナイフを置いているはずです。IVTは、ジョージがケーキがどこかの時点で半分になったと確信しなければならないことを確立します。
• コインを投げて、2 つの選択肢から選択します。ジョージがナイフの間のピースを受け取り、アリスが側面の 2 つのピースを受け取るか、またはその逆です。パートナーが正直であれば、ナイフの間のピースの価値がちょうど 1/2 であることに同意し、分割は正確になります。

1 本のナイフを使用しても同じ効果が得られます。

• アリスはケーキの上でナイフを180度回転させ、両側に半分ずつ切ります。
• ジョージは同意しながら「やめて！」と言います。

もちろん、アリスはナイフを開始したのと同じラインで終了する必要があります。また、IVT により、ジョージが 2 つの半分が等しいと感じるポイントが存在する必要があります。

オースティンが指摘したように、2人のパートナーは、任意の整数 に対して、両者が正確に と評価するケーキを1つ見つけることができます。^[2]上記の手順を呼び出します。 ${\displaystyle 1/k}$${\displaystyle k\geq 2}$${\displaystyle \mathrm {カット} _{2}(1/k)}$

• アリスはケーキに平行な印を付け、その印が正確に の値を持つようにします。${\displaystyle k-1}$${\displaystyle k}$${\displaystyle 1/k}$
• ジョージも として評価している作品があれば、それで終わりです。${\displaystyle 1/k}$
• それ以外の場合は、ジョージが より小さいと評価するピースと、ジョージが より大きいと評価する隣接するピースが存在する必要があります。${\displaystyle 1/k}$${\displaystyle 1/k}$
• アリスが 2 本のナイフをこれらのピースの 1 つの 2 つのマークの上に置き、ナイフ間の値がちょうど になるように平行に動かして、もう一方のピースのマークと出会うまで動かします。IVT により、ナイフ間の値がちょうど であることにジョージが同意する点が存在するはずです。${\displaystyle 1/k}$${\displaystyle 1/k}$

を再帰的に適用することで、2人のパートナーはケーキ全体を、それぞれが両者にとってちょうど同じ価値を持つように分割することができます。^[2]${\displaystyle \mathrm {カット} _{2}}$${\displaystyle k}$${\displaystyle 1/k}$

• 両方のパートナーにとってちょうど価値のあるピースをカットするために使用します。${\displaystyle \mathrm {カット} _{2}(1/k)}$${\displaystyle 1/k}$
• これで、残ったケーキは両方のパートナーにちょうど合う分になりました。 を使用して、両方のパートナーにちょうど合う分の別のケーキを切り取ります。${\displaystyle (k-1)/k}$${\displaystyle \mathrm {カット} _{2}(1/(k-1))}$${\displaystyle 1/k}$
• ピースができるまでこれを続けます。${\displaystyle k}$

2人のパートナーは、少し複雑な手続きを踏むことで、権利の合理的な比率で正確な分割を達成することができます。 ^{[3] : 71}

フィンクプロトコルと組み合わせることで、各パートナーが自分にちょうど見合った価値のケーキを受け取るようにケーキをパートナーに分割することが可能になります。 ^{[1] [4]}${\displaystyle \mathrm {カット} _{2}}$${\displaystyle n}$${\displaystyle 1/n}$

• パートナー #1 と #2 は、それぞれにちょうど 1/2 の価値があるピースを 1 つずつ渡します。${\displaystyle \mathrm {カット} _{2}(1/2)}$
• パートナー #3 は、パートナー #1 と一緒に を使って自分の取り分のちょうど 1/3 を獲得し、次にパートナー #2 と一緒に を使って自分の取り分のちょうど 1/3 を獲得します。最初のピースはパートナー #1 にとってちょうど 1/6 の価値があり、パートナー #1 はちょうど 1/3 を保持します。パートナー #2 についても同様です。パートナー #3 については、各ピースは 1/6 より多くても少なくてもかまいませんが、2 つのピースの合計はケーキ全体のちょうど 1/3 でなければなりません。${\displaystyle \mathrm {カット} _{2}(1/3)}$${\displaystyle \mathrm {カット} _{2}(1/3)}$

の場合、ピースの価値はその所有者にのみあり、他のパートナーには必ずしも価値がないため、生成される分割は正確ではないことに注意してください。2015 年現在、パートナーの正確な分割手順は知られておらず、ほぼ正確な分割手順のみが知られています。 ${\displaystyle n>2}$${\displaystyle 1/n}$${\displaystyle n>2}$

• オースティンの手順は、ブラムス・テイラー・ツヴィッカーの手順で使用されます。
• 公平分割と厳密分割に関するその他の手順と結果。

• フィッシャー、ダニエル。「2 人でのケーキの合意分割、任意の比率で」。Math.SE。2015年6 月 23 日閲覧。