asahi.com（朝日新聞社）：ＮＴＴ、「ケーキ分割問題」を新アルゴリズムで解決 - 日刊工業新聞ニュース - デジタル

一つのクリスマスケーキを２人で公平に分けるには、どこにナイフを入れたらいいか―。長年未解決だった、数学の難問「ケーキ分割問題」をＮＴＴが解決した。ビジネスの取引などに使える実用的なアルゴリズムになるという。提案したアルゴリズムの正しさを証明し、このほどコンピューターサイエンスに関する国際会議で発表した。 ＮＴＴが開発したアルゴリズムによる解答は、（１）ＡとＢがそれぞれ、切りたいケーキの場所を（第三者などを通じて）同時に申告する（２）切りたい場所が両者で異なっていた場合、そのちょうど中間にナイフを入れる（３）申告した場所を含む側のケーキを両者が得る―というもの。もちろん、（１）で申告した場所が両者で一致した場合はそこで切り分ければよい。この方法で行えば、２人が満足のいく形でケーキを分割することができる。 古典的な解法に、（１）Ａがケーキを切る（２）Ｂが好きな方を選ぶ（３）残りをＡが取る―

[nyop]

これって、両者が同じ部位を欲するケースはどうすればよいんだろう？人によって効用が異なる前提であるなら、申告部位を含む領域を得ることができる、というのが腑に落ちない。そこは考えないのかな？

[yasumo]

おおすげぇ

[NAT]

このアルゴリズム、コンピュータが第3者になって調整できるところに応用の幅を感じる。限られた資源を公平に分割する話って、よくある話だし。

[mobile_neko]

おばあちゃんの知恵袋的な解決方法で良いなぁ。

[mrkn]

論文情報 http://www.springerlink.com/content/p26w511604p01173/ とPDF http://www.brl.ntt.co.jp/people/manabe/cutMFCS.pdf

[kojosan]

２者の好みをどのように数学的にモデル化したのかが気になる "asahi.com（朝日新聞社）：ＮＴＴ、「ケーキ分割問題」を新アルゴリズムで解決 - 日刊工業新聞ニュース - デジタル"

[ysks]

NTTもケーキ分割問題に取り組んでたのか… RT @hrjn2: って、なんか10時間前にケーキ分割問題のニュースが出てた。これで話題になってたのかな？