「NTT、「1つのケーキを2人で公平に分割する」アルゴリズムを開発」記事へのコメント

ええと・・・

[Anonymous Coward]

申告した場所を含むケーキを分配する

某所にも出てました。
ここが重要だと思うのですがこの説明がよくわからないのは自分だけ？

Re:ええと・・・

[phason (22006)]

これは「ケーキ分割問題」（とか無羨望分割問題）という有名な問題で，ケーキ（というかより一般的に分割される何か）は均一ではありません．ケーキの例で言うなら，苺がいっぱい入っている部分もあればチョコの家が乗っている部分もある，さらには人によって苺が好きな人もいればクリームが好きな人もいる，そう言うものを誰からも文句が出ないように分割するにはどうすればいいか？と言うような問題です．

そのため，「申告した場所」というのは例えば，Aという人物が苺の多い部分を含む領域を指定し，Bという人物がクリームの多い部分を含む領域を指定したら，アルゴリズムに基づいて分割線を決定した後，Aは苺の多いパート，Bはクリームの多いパートを取る，とかまあそんな分け方です．

各人が異なる価値評価関数を持っているため，例えば「2人で分割したとき，各人が（それぞれの価値観において）ケーキの価値の1/2以上を所持している」という状況を目指すわけです．これがさらに3人，4人と増えていくと大変なことになります．
どういうアルゴリズムを使えば各人にとっての価値が最高になるか，公平になるか，など，今でも研究している人がいますし学会発表もあった……はず．

Re:ええと・・・

[bit (41221)]

>ケーキの例で言うなら，苺がいっぱい入っている部分もあればチョコの家が乗っている部分もある

ところで水平方向に切るというのは、ありなのかな？

以前、ケーキを、「切ってください、体積が大きい方をわたしが貰います」とかいうのに、そうやって、上のクリームとイチゴがたっぷりのところと、土台に切り分けて土台をあげたらむくれていた。

Re:ええと・・・

[phenix (31258)]

人でなしがいる・・・

Re:ええと・・・

[Emc2 (14960)]

その発想はなかった…

--
RYZEN始めました