自動ニュース作成G
NTT、「ケーキ分割問題」を新アルゴリズムで解決
http://www.asahi.com/digital/nikkanko/NKK201012240013.html
2010-12-25 23:18:50
>NTTが開発したアルゴリズムによる解答は、(1)AとBがそれぞれ、切りたいケーキの場所を(第三者などを通じて)同時に申告する(2)切りたい場所が両者で異なっていた場合、
>そのちょうど中間にナイフを入れる(3)申告した場所を含む側のケーキを両者が得る―というもの。もちろん、(1)で申告した場所が両者で一致した場合はそこで切り分ければよい。
一方が切り一方が選択する手法だと、切った方は決して得しないが選択する方は得する可能性があるとか、色々問題ありますしね。Fair division(英文wikipedia)◇
・AB両者の価値観が同じとは限らないという前提が書かれていないから「何言ってんの?」って感じのニュースになるな。・丁度中間がムズイのだ・この問題の意味がわかんない・ああ思いっきり自分に得な切り分け位置示せば良いんじゃねとか思ってしまった。示した位置を含む断片を得るってのがミソか。・ナイフで相手を刺せばいいんじゃない?・真ん中を示すのが自分にとって一番損の少ない切り分け位置になる、ということにしばらく考えてからようやく気づいた。直感的にはちょっと分かりづらいかも。・#4 同じくそこで困惑した。これケーキで平易な比喩をしたつもりだろうけど、むしろ街頭ディスプレーや油田の採掘権を複数で分割する例の方が分かりやすい。・「ケーキ」と聞いてホールケーキを想像するからなかなかわかりにくいんだな。元記事にあるようにロールケーキの長さで考えるとわかりやすい。・ロールケーキなんかカステラにも劣るのだ・なんだと?・新たな対立が生まれようとしているな・問題の切断面が違っているが。・トランスアキシャル面とサジタル面?・頭の体操で良く見るクイズと同じ種類の問題では? ケーキ切り分けに適応するのは無問題だが、二国間の領土決定には使えない手法だなと思ってしまった。・いちごケーキにも応用できるのか?・応用は可能だが、中間の解釈自体が難しいだろう。・#16 だったら最初から端と端の中間で切ればいいってことだよね……・一つ疑問が・・・申告した切り場所が同じで、双方が同じ端を希望したら問題が起きないかな?・全部と主張すれば少なくとも半分は確保できると言うことか?なに、この糞理論。昔から裁判所の調停でやられていることだよね。・>>1の人と被るけど、片方が強欲で全部を選択して、もう片方が普通に真ん中を選択すると3:1になっちゃうな。どこが公平なんだと思った・#20 それは強欲な人じゃなくて(3)の条件を理解できてない人でしょ・多く切ろうとした人が多くもらえるとは限らないでしょ。欲張っても小さいほうをもらうハメになったら損する。切りたい場所を決めてるだけだし。・#21 うーん、よくわからない。例えば10センチのロールケーキがあった場合、Aが0から5センチまでを宣言、Bが1センチから10センチまでを宣言した場合、どこで切られてそれぞれどれだけ得られるの?・#20 それで全部を要求した人は1/4を得て、半分でお腹いっぱいの人は3/4も来てしまい、ルール理解しないやつの暴挙で、双方1/4の損。・#23 切りたい場所を宣言するルールなのに、なんで欲しい範囲を申告しているの?・あああ。3を理解。「含む」っていうのがエリアと勘違いしてた。アスペで申し訳ない。でもどっちかにイチゴがあると困るね。・#16の意図が分かり難そうなので補足。長さ10のロールケーキで0~5までの価値が1(例えば苺が乗っている)、5~10までの価値が0(例えばスポンジのみ)の時に双方5の場所での切り分けを主張したらどうなるのだろうと云う意味。この場合どちら側を取るか選択出来る側が有利になるので、不公平じゃないかって意味です。長文スマソ・↑#16じゃなくて#18でした。すいません・苺が乗ってる方が価値が高いと認識してるならど真ん中で両者が切り分け線入れないでしょう。真ん中で切ったら苺がある方が価値あがっちゃうんだし。お互い損しないように動くから苺がないほうが長くなる。・あぁなるほど、双方がどちらをとっても良いと考えるところで線を入れると云うことですね。わかりました。・土木工事とかにも使えそうだな。地盤が硬かったり川があったりしたときに公平に選べるように。談合する時にいいな・単純なルールなんで今までも思いつきそうな感じやけれど、無かったのが何か不思議。・県境とか揉めて、結局真ん中ってよくある話じゃない?3者まで適用できるアルゴリズムに新規性があるんか?・#33 これを県境の解決に使えると思っている時点で勘違い、それだと飛び地だらけになる。それに双方の間を勝手に取るのが重要じゃなくて、欲張ると損するので戦略的に妥協したラインを提案させる方法がポイントなの。・では せかいの はんぶん やみのせかいを さずけよう!