最後の減少

最後の減額手順は、公平なケーキカットのための手順です。これは、誕生日ケーキのような、ある種の異質で分割可能な資源と、ケーキのさまざまな部分に対する好みが異なるn人のパートナーを対象とします。この手順により、 n人は比例配分、つまり、各人が自身の主観的な評価に基づいて、全体の価値の少なくとも1/ nに相当する価値を持つピースを受け取るようにケーキを分割することができます。例えば、アリスがケーキ全体を100ドルと評価し、パートナーが5人いる場合、アリスは他のパートナーの考えや行動に関係なく、少なくとも20ドルと評価するピースを受け取ることができます。

第二次世界大戦中、ナチスから身を隠していたポーランドの数学者フーゴ・シュタインハウスは、資源を公平に分配する方法という問題に取り組んでいた。2人の兄弟の間でケーキを分ける分割選択の手順に触発され、彼は教え子のステファン・バナッハとブロニスワフ・クナスターに、任意の人数に適用できる手順を見つけるよう依頼し、彼らの解決策を発表した。^{[ 1 ]}

この出版物は、さまざまな分野の多くの研究者によって研究されている新しい研究テーマを提起しました。公平な分配を参照してください。

以下は、著者による分割プロトコルの説明です。

「参加者はA、B、C、…、Nと並び、Aがケーキから任意の一片を切り取ります。Bは切り取った一片を減らす権利を持ちますが、義務はありません。Cは、すでに減らされた（または減らされていない）一片をさらに減らす権利を持ちますが、義務はありません。Nまで同様に続きます。ルールでは、「最後に減らした人」は、最後に触れた一片を自分の分として受け取る義務があります。この参加者が除外された後、残りのn -1人が残りのケーキを使って同じゲームを始めます。参加者が2人になったら、残りのケーキを半分に分ける古典的なルールを適用します。」

各パートナーは、少なくとも 1/ nの値が付くスライスを受け取ることを保証する方法を持っています。その方法は、常に現在のスライスを切り分け、残りのスライスの値が 1/ nになるようにすることです。選択肢は 2 つあります。1 つは自分が切り分けたスライスを受け取るか、もう 1 つは他の人が自分にとって 1/ nより小さい値になるスライスを受け取るかのどちらかです。後者の場合、残りのパートナーはn −1 人となり、残りのケーキの値は ( n −1)/ nより大きくなります。したがって、帰納法により、受け取る値が少なくとも 1/ nであることを証明できます。

ラストディミニッシャープロトコルは離散的で、順番にプレイできます。最悪の場合、n × (n−1) / 2 = O ( n ² )のアクションが必要です。つまり、1ターンにプレイヤー1人あたり1つのアクションが必要です。

しかし、これらのO ( n ² ) のアクションのほとんどは実際のカットではありません。つまり、アリスは紙に希望するスライスをマークし、他のプレイヤーに同じ紙上でそれを縮小してもらうことができます。実際にケーキをカットする必要があるのは「最後に縮小した人」だけです。したがって、必要なカットはn -1 回だけです。

この手順では、切断に関して非常に自由度が高い。パートナーが行う切断はどのような形状でも構わないし、切断箇所が分離していてもよい。一方で、部品の形状を美しく保つために、切断を制限することも可能です。具体的には、以下のとおりです。

• 元のケーキが繋がっている場合、各ピースが繋がっている（連続している）ことを保証できる。
• 元のケーキが凸集合である場合、各ピースが凸集合であることを保証できる。
• 元のケーキが長方形であれば、切り取った各ピースも長方形であることを保証できる。
• 元のケーキが三角形であれば、切り取った各ピースも必ず三角形になることが保証できる。

このプロトコルの連続時間バージョンは、Dubins-Spanier移動ナイフ手順を使用して実行できます。^{[ 2 ]}これは、公平な分割における連続手順の最初の例でした。ナイフはケーキの左端から右端まで渡されます。どのプレイヤーも、自分がそう思うときに停止を言うことができます。 ${\displaystyle 1/n}$ケーキの半分がナイフの左側にある場合、ケーキを切り、発言したプレイヤーがその部分を受け取ります。残りのケーキとプレイヤーでこれを繰り返し、最後のプレイヤーが残りのケーキを受け取ります。最後の縮小手順と同様に、各プレイヤーのためにケーキを連続した部分に切り分けるために使用できます。

パートナーが3人以上いる場合、最後の減少者方式で得られる分配は必ずしも羨望のない分配になるとは限りません。例えば、最初のパートナーであるアリスが1つの分け前を受け取り（アリスはそれを全体の3分の1と評価します）、残りの2人のパートナーであるボブとチャーリーが、自分たちの意見では公平な方法で分け合ったとします。しかし、アリスの意見では、ボブの分け前は3分の2の価値があり、チャーリーの分け前は0の価値しかありません。この場合、アリスはボブを羨むことになります。

簡単な解決策^{[ 3 ]}は、再参加を許可することです。つまり、最後の減少者としてピースを獲得したパートナーは、ゲームから退出する必要はなく、むしろゲームに留まり、次のステップに参加することができます。再び勝利した場合、現在のピースを解放しなければならず、それはケーキに戻されます。プロトコルが確実に終了するように、特定の定数を選択します。${\displaystyle \epsilon }$そして、各パートナーが最大で${\displaystyle 1/\epsilon }$回。

再入可能バージョンでは、各パートナーは、少なくとも最大値マイナスのスライスを受け取ることを保証するメソッドを持っています。${\displaystyle \epsilon }$方法は次のとおりです。常に現在のスライスを切り取り、残りの値が次の値になるようにします。${\displaystyle \epsilon }$プラス現在の価値。これにより、価値が確実に増加します。${\displaystyle \epsilon }$勝つたびに、そして勝てなかった場合、勝者の価値は最大で${\displaystyle \epsilon }$自分の価値よりも高い。したがって、嫉妬のレベルは最大で${\displaystyle \epsilon }$（加法定数）

実行時間は最大で${\displaystyle n^{2}/\epsilon }$最大で${\displaystyle n/\epsilon }$ステップごとに、${\displaystyle n}$パートナー。

近似的に羨望のない方式の欠点は、ピースが常にケーキに戻されて再分割されるため、ピースが必ずしも繋がっているとは限らないことです。この問題に対する他の解決策については、「羨望のないケーキカット#繋がったピース」を参照してください。

最後の減少手順は、後に様々な点で改良されました。詳細は比例除算を参照してください。