NTT、「1つのケーキを2人で公平に分割する」アルゴリズムを開発 | スラド サイエンス

NTTが「一つのクリスマスケーキを２人で公平に分けるには、どこにナイフを入れたらいいか」という「ケーキ分割問題」を正しく解くアルゴリズムを開発したそうだ（日刊工業新聞）。 「ケーキ分割問題」とは、2人で1つのケーキを分割する際に、両者が満足するように分割するにはどうすれば良いか、という問題。2人が異なる価値観を持っているというのがポイント。今回発表された新アルゴリズムは「両者が同時に切りたい場所を申告し、その中間でカット、申告した場所を含むケーキを分配する」というものだそうだ。 今日・明日とケーキを食べる機会は多いかと思うが、さっそく応用してみてはいかがだろうか。しかし、3人以上で分割する場合はどうすれば良いのだろうか？

[wtatsuru]

2人で，ね...

[nokihd]

両者とも半分だと思った量より多くもらえるわけね。

[llil]

ケーキ分割問題/

[A2MKNT]

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

[mobanama]

"「（2人の場合）1人がケーキカットしてもう1人が好きなほうを選ぶ」というよく知られた方法は、実は公平ではないよね、ってのは最初のほう(1. Introduction)に書いてあります"

[rti7743]

ミキサーにかけて分量で配布すれば(ry

[bunoum]

東シナ海でいうと、日「中間線」中「大陸棚あるから中７：日３の線で」→中６：日４の位置で分割し線の中国側を日本のものに、日本側を中国のものにします。…となるのでこういうケースには適用できないわけか。

[toaruR]

2人ともまるっきり同じ申告をしたら……

[yowa]

ケーキ分割問題 ／ これが論文らしい http://bit.ly/h5aPfP ／ 問題の入門記事 http://bit.ly/eJcr62

[kazkaz03]

アルゴリズム…なの？

[hiromark]

これ論文読んでみたい。

[jt_noSke]

すけ゛ー気がする

[SiroKuro]

ジャイアニズムが邪魔をする

[toshikaz55]

"NTT、「1つのケーキを2人で公平に分割する」アルゴリズムを開発 - スラッシュドット・ジャパン" " "

[dankogai]

cf. http://j.mp/efqvaS

[nanoha3]

切り分けずに、食べさせあいっこすればいいじゃん。

[UDONCHAN]

今日も平和です