LXXXVIII-th stone: fairly division and envy-free division

今日は大勢で物を分けるという事について。一つの物を複数人で分ける。これは実生活でよくあることだ。
しかし、均等に分割するというのはいつもいつもできる訳ではない。遺産相続などがいい例だ。
時価や金額の上だけで均等に分割したとしても納得いく物ではないだろう。
そういう場合に「みんなが納得できるように分ける」という問題がある。

ここに一つのケーキがある。ケーキはどこまでも分割できる（すなわち連続）であると仮定する。
そしてN人でそれを分けるとする。ただしここではN人の主観はそれぞれ異なるとする。
例えば、AさんとBさんがいたとるすとAさんの主観でケーキを二等分してもそれはBさんにとっては二等分になっていない
ということだ。この元でN人でケーキを分けるとき次のような分け方が考えられる。

単純公平(fairly): 誰もが1/N以上のケーキを獲得する。
無羨望(envy-free):誰もが自分が一番多く獲得したと思える。

fairly divisionの手続きについては２人のときは至って単純である。

一人が半分に分けて、もう一人が好きな方を選ぶ。

この単純な手続きでA,Bはそれぞれ1/2以上を獲得できる。が、注意したいのは選ぶ方が断然有利だと言う点だ。
これは3人にも容易に拡張できるので、考えてみてほしい。

通常であれば fairlyに分ける事ができればある程度の人間は納得するだろうが、自分の主観でいって自分より取り分の多い
人間がいたらどうだろう。もしかしたら、文句がでるだろう。
そんな時は無羨望分割をすればよい。が、このenvy-free division。3人のときですら、かなり難しい。

今日半日かけたが、あまり進まなかった。
webには答えが有るようなので、ここには記載しないが。自分で解きたいものだ。
そんな分割ができると知っただけでも今日は収穫だ。実際最初はできないと思ったので、これを聞いたときにはびっくり。

検索キーワード: 無羨望　分割