ブラムス・テイラー法

Brams–Taylor 手順( BTP) は、羨望のないケーキカットの手順です。これは、任意の正の整数数のプレイヤー間でケーキを羨望なく分割する最初の有限手順を明示しました。^{[ 1 ]} ただし、この手順の実行時間はプレイヤーの数の関数によって制限されず、評価関数に応じて任意に長い (ただし常に有限) 時間を要します。2016 年に、Aziz と Mackenzie は、プレイヤーの数によって制限されるプロトコルを発見しました。詳細については、こちらを参照してください。

1988年、BTPが発見される前に、ソル・ガーファンケルは、この定理によって解決される問題、すなわちn人による羨望のないケーキカットの問題は、20世紀の数学における最も重要な問題の一つであると主張した。^{[ 2 ]}

BTPは、スティーブン・ブラムスとアラン・D・テイラーによって発見されました。これは、1995年1月号のAmerican Mathematical Monthly誌に初めて掲載され[ ^{3 ] 、}その後1996年に著者らの著書にも掲載されました^{[ 4 ] 。}

ブラムスとテイラーは、BTPに関連する1999年の米国共同特許を保有している。 ^{[ 5 ]}

BTPはケーキを部分ごとに分割します。BTPの典型的な中間状態は次のとおりです。

• ケーキの一部、例えば${\displaystyle X}$は、すべてのパートナー間で嫉妬のない方法で分配されます。
• 残りのケーキは、${\displaystyle Y}$分割されずに残っているが、
• 一方のパートナー、例えばアリスは、もう一方のパートナー、例えばボブに対して、以下の点に関して取り消し不能な優位性（IA）を有している。${\displaystyle Y}$これは、${\displaystyle Y}$分割されている、たとえ${\displaystyle Y}$アリスはボブのことを全く羨ましいとは思っていない。

IAがどのように生成されるかの例として、Selfridge–Conway離散手順の最初の段階を考えてみましょう。

• アリスはケーキを3等分します。${\displaystyle A,B,C}$。
• ボブは、自分が一番大きいと思う部分を切り取ります（例えば、${\displaystyle A}$）それを2番目に大きいものと等しくするために、トリミングを${\displaystyle Y}$そしてトリミングされたピース${\displaystyle A\setminus Y}$。
• チャーリーは${\displaystyle (A\setminus Y),B,C}$;次にボブは選択する（彼は取らなければならない）${\displaystyle (A\setminus Y)}$（もし利用可能であれば）そして最後にアリス。

この段階が終わると、ケーキは${\displaystyle Y}$嫉妬のない方法で分割されています。さらに、アリスは今、誰であろうと、それを奪った者に対してIAを持っています。${\displaystyle (A\setminus Y)}$なぜ？アリスはどちらかを選んだから${\displaystyle B}$または${\displaystyle C}$、そして両方とも等しい${\displaystyle A}$彼女の意見では。つまり、アリスの意見では、誰が${\displaystyle (A\setminus Y)}$また、${\displaystyle Y}$―これは彼女を嫉妬させることにはならないだろう。

アリスが特定のプレイヤー（例えばボブ）に対してIA（投資優位）を確実に得るためには、はるかに複雑な手順が必要となる。この手順では、ケーキを次々と小さなピースに分割し、常にアリスがボブよりも価値の高いピースを与えることで、IAが維持されるようにする。この手順には、アリスとボブの正確な評価に応じて、無限の時間を要する可能性がある。

IA手順を使用すると、メインのBTP手順は、すべての順序付きパートナーペアに対してIAを作成します。たとえば、パートナーが4人いる場合、12組の順序付きパートナーペアが存在します。各ペア(X,Y)に対して、パートナーXがパートナーYに対してIAを持つことを保証するサブプロシージャを実行します。すべてのパートナーが他のすべてのパートナーに対してIAを持った後、残りを任意のパートナーに与えるだけで、結果としてケーキ全体が羨望のない形で分割されます。

• ブラムス・テイラー・ズウィッカー法– 4人のパートナーのための移動ナイフ法であり、有限回のカットを使用する。
• 嫉妬を招かないケーキカット― 同じ問題に対する、従来型と新型の手法。
• 調整済み勝者決定手続き– ブラムスとテイラーによって考案された手続きで、2人の代理人の間で商品を分割するという、類似しているが異なる問題に対処するものです。