ナイフ移動法

ナイフ移動法（ないふいどうほう、英: moving-knife procedure）は公平分割問題を解くための数学的手法の1つで ある。 公平分割問題を解くナイフ移動法には、1本ナイフを使うもの、2本ナイフを使うもの、4本ナイフを使うものなどがあるが、 本項目では最も基本的な、DubinsとSpanierにより考案された1本ナイフ移動法を主に説明する。

1本ナイフ移動法では、分割可能な1個の対象物の上を、参加者全員が見ながら、カット位置の案を示す1本のナイフ が連続的に移動する。結果として参加者は誰も全体人数分の1以上の価値を得ることができる。

1本ナイフ移動法

直方体のようかんを3人以上で分割する場合で示す。

ようかんの左端から右端に向けてカット位置の案を示すナイフが連続的に移動する。 自分の基準で左端からカット位置までが全体人数分の1の価値と思ったら参加者は「ストップ」と言う。 最初に「ストップ」と言った人は、ナイフで切り、左端からそのカット位置までの部分を得て退場する。 もしも同時に2人以上が「ストップ」と言った場合は、くじで誰か一人を選ぶ。

上記を繰り返し、2人が1人になったら、最後の1人が残った部分を得て終了する。

1本ナイフ移動法の原理

1本ナイフ移動法で各自が全体人数分の1の価値が得られる理由は以下である。

最初の1人が「ストップ」と言った瞬間、この人は左端からカット位置までを、 全体人数分の1の価値と思っている。残りの人は「ストップ」と言わなかったので、 全体人数分の1未満の価値と思っている。つまり残りの人全員は、カット位置から右端までの部分を、 (全体人数分の1)×(残りの人数)の価値以上と考えている。つまりどちら側の人も全体人数分の1以上の価値の確保が 保証されている。上記を繰り返し、最後の1人になると、どの人も全体人数分の1以上の価値を得ている。

1本ナイフ移動法の離散版

連続版である1本ナイフ移動法を離散版に直すと、次のように最後に切った人法(英語版)となる。

参加者に順番をつけ、1番目の人、2番目の人、...　と呼ぶ。 まず1番目の人が自分1人分のカット位置の案を示す。残りの人は順番にチェックして、 もしも左端からカット位置の部分が全体人数分の1の価値を超えていると思った場合は、カット位置を ちょうど全体人数分の1の価値と思える位置まで左端側に戻す。 残りの人のチェックがすべて終了したら最も左端に近いカット位置を設定した人が、 その位置でナイフで切って、左端からカット位置の部分を得て退場する。 上記を繰り返し、2人になったら、1番目の人が2分割し、2番目の人が 価値の大きいと思う方を選び、1番目の人が残りを得る。

ナイフ移動法の近似法

2本や4本のナイフを使うナイフ移動法の場合、全参加者が同時に連続的に変化する複数種類のカット位置の案を 瞬時に判断することが必要である。このため現実に行うにはほんの少し動かしては止めるを繰り返す離散的近似法となる。