NTT、「1つのケーキを2人で公平に分割する」アルゴリズムを開発 101
ストーリー by hylom
分割する相手を見つけるアルゴリズムをお願いします 部門より
分割する相手を見つけるアルゴリズムをお願いします 部門より
あるAnonymous Coward 曰く、
NTTが「一つのクリスマスケーキを２人で公平に分けるには、どこにナイフを入れたらいいか」という「ケーキ分割問題」を正しく解くアルゴリズムを開発したそうだ（日刊工業新聞）。
「ケーキ分割問題」とは、2人で1つのケーキを分割する際に、両者が満足するように分割するにはどうすれば良いか、という問題。2人が異なる価値観を持っているというのがポイント。今回発表された新アルゴリズムは「両者が同時に切りたい場所を申告し、その中間でカット、申告した場所を含むケーキを分配する」というものだそうだ。
今日・明日とケーキを食べる機会は多いかと思うが、さっそく応用してみてはいかがだろうか。しかし、3人以上で分割する場合はどうすれば良いのだろうか？
元ネタ見つけました (スコア:5, 参考になる)
これっぽい。読み中…。
Meta-Envy-Free Cake-Cutting Protocols [ntt.co.jp] (PDF)
「（2人の場合）1人がケーキカットしてもう1人が好きなほうを選ぶ」というよく知られた方法は、実は公平ではないよね、ってのは最初のほう(1. Introduction)に書いてあります。
# 私なら、選ぶほうになりたいな。
OK，まずは落ち着け (スコア:5, 参考になる)
・わかりやすくケーキとして書いてありますが，（現在では）現実のケーキを直接対象とする研究ではありません．
・カットと書いてありますが，文字通り包丁で切り分けるとかそう言う話でもありません．
・そのため切る際の技術だ何だの問題は存在しません．
京大の伊藤先生 [kyoto-u.ac.jp]のところの関連する一般向けの読み物．
http://www.lab2.kuis.kyoto-u.ac.jp/~itohiro/Puzzle/cake_cutting/Lv1_Q.html [kyoto-u.ac.jp]
http://www.lab2.kuis.kyoto-u.ac.jp/~itohiro/Puzzle/cake_cutting/Lv2_Q.html [kyoto-u.ac.jp]
http://www.lab2.kuis.kyoto-u.ac.jp/~itohiro/Puzzle/cake_cutting/Lv3_Q.html [kyoto-u.ac.jp]
http://www.lab2.kuis.kyoto-u.ac.jp/~itohiro/lecture/Cake-cutting.pdf [kyoto-u.ac.jp]
Re:OK，まずは落ち着け (スコア:2)
いやー、この時期にこんな発表されたら大騒ぎになりますって。
# 微妙な時期になんつー発表するんだ、NTTは。せめてクリスマス外せゴルァ。
Re:OK，まずは落ち着け (スコア:2)
日刊工業新聞の記事がどの結果のことを指しているか知りませんが、この結果 [srad.jp]は今年 8 月の MFCS 2010 [fi.muni.cz] という会議で発表されていたものです。
世の中にはジャイアンという奴がいてだな… (スコア:4, おもしろおかしい)
少なくとも 1 人が「全部くれ」と主張する場合、このアルゴリズムでは解決しません
Re:世の中にはジャイアンという奴がいてだな… (スコア:1)
中国とか韓国ですね。わかります。
Re:世の中にはジャイアンという奴がいてだな… (スコア:1, すばらしい洞察)
二人の場合 (スコア:2)
１．Ａがどちらも平等（均等）になるように２つに分割します。
２．Ｂが自分の好きなほうを選び、残った方をＡが取ります。
これでお互い文句なく２つの分割できます。子供が二人いる場合は特に有効。
苺が載っている場合は苺が載っている側のケーキを大きくするか小さくするかはＡの判断ですが、Ａは自分のとりたい方を選べないので…
Re:二人の場合 (スコア:2, 参考になる)
#1879227に、実はそれは公平じゃないと書いてあるとの指摘がありました。
なんで公平じゃないのか読んで見たところ、こうありました。
例えば、長さが1のケーキがあって、0に近い方がチョコレートがたっぷりついているとする。
Bobはチョコレートが好きで、チョコレートがいっぱいついた部分が貴重だと思っているので、
0～1/4と、1/4～1で切り分けるのが公平だと思っている。
一方Aliceは、チョコレートは気にせず、単純に長さだけを考えるので、
0～1/2と、1/2～1で切り分けるのが公平だと思っている。
もしもBobが切り分けてAliceが選ぶならば:
Alice: 1/4～1 Bob: 0～1/4
もしもAliceが切り分けてBobが選ぶならば:
Alice: 1/2～1 Bob: 0～1/2
この結果を見ると、Aliceから見ても、Bobから見ても、自分が切り分けるよりも相手に切り分けさせた方が得だということが分かる。なので、どっちが切り分けるかで揉めることとなる。
# けど、これは、両者が互いの好みをしらないのが前提なので、2人きょうだいで、互いの好みを知っている場合は、逆に、自分が切った方が得になるのかなぁ。
1を聞いて0を知れ!
Re:二人の場合 (スコア:2, すばらしい洞察)
切り分けるほうは自分が公平になると思うところで切るため、どちらが残っても同じ。
選ぶほうが自分が得だと思うほうを選ぶ。
切り分けるほうにリスクがあるが、選ぶほうにはリスクがない。
Bobが1/4より少し大きいところで切った場合と、Aliceが1/2より少し小さいところで切った場合は二人とも満足。
Bobが1/4で切った場合と、Aliceが1/2で切った場合は、切ったほうは予定どおり、選んだほうは満足。
Bobが1/4より少し小さいところで切った場合と、Aliceが1/2より少し大きいところで切った場合は切ったほうが不満。
今回のアルゴリズムは、1/2と1/4の間である3/8で切って、0のほうをBob, 1のほうをAliceが選べば、二人とも満足。
できがいいアルゴリズムだと思うけど？
計測の軸を変えると楽になるかも (スコア:2)
所詮カロリーは変わんないんだし……とか考えた。
fj.jokes出身:
3人で分ける場合 (スコア:1)
２人で分けるアルゴリズムの一つに「片方が分割線を引き、もう片方が選ぶ」というものがありますよね。
（これは両者がほぼ同じ価値観を持つ前提ですが）
これを３人に拡張すると
・一人目が分割し
・二人目が選び
・三人目が食べる
これで万全！
問題は、アツアツおでんに適用した場合、大体たまごやこんにゃくやモチきんちゃくが選択されるというところでしょうか。
Re:3人で分ける場合 (スコア:1, おもしろおかしい)
3人でかつアツアツおでんの場合はダチョウメソッドが最適ではないかと思われます。
国境線そのままで、東ドイツいらないor北朝鮮いらない (スコア:1, 興味深い)
正直者がばかをみる (スコア:1)
ふたりのうち、正直者は「だいたい真ん中だろう」というラインを指定。
もうひとりは、「どうせ、ふたりの引いたラインの中間になるのだから」といって、
自分：相手＝99.9：0.1くらいになるようなラインを指定。
結果、正直者は約25%、もうひとりは約75%のケーキをもらいましたとさ。
Re:正直者がばかをみる (スコア:2)
Re:正直者がばかをみる (スコア:4, 参考になる)
価値観の違いというのはこの場合、「ケーキのどの部分に価値を見出すか」が各人によって違うという意味で、伊藤先生の資料(PDF) [kyoto-u.ac.jp]にありますがこの問題の前提として、「各人が全体の価値の1/n以上の価値を持つピースを得れば満足する」という仮定があります。
ご指摘の場合では強欲な方が全体の0.1%を残りの99.9%と同等の価値と認めて境界を区切った事になるので、その0.1%を含む約25%を得ることになるので満足するはずです。また正直者も自分が50%と思った領域以上を貰えるので満足です。
駄目ぢゃん (スコア:1)
「切りたい場所」の申請の結果、その線が交わった時の処理が決まってないから仕様漏れだと思いまーす！
＃円形のケーキだと普通に起きそう
一方かの王女様は・・・ (スコア:1, すばらしい洞察)
2つ買えばいいじゃない
Re:一方かの王女様は・・・ (スコア:2, すばらしい洞察)
そうするとその二つのどちらを取るかで同じ問題が……
Re:一方かの王女様は・・・ (スコア:1)
王女様なんだから、ふたつくらい食べちゃうのでは？
一方…… (スコア:1, おもしろおかしい)
「ケーキを公平に切る」
この命題の為にＮＴＴは少なからぬ人材と時間を使い、不完全ながらも２人に対して公平に分割するアルゴリズムを作成した。
これにより、条件さえ揃えばそれなりに公平にケーキが切れるようになった。
一方、ソフトバンクはケーキを人数分買ってきた。
Re:一方…… (スコア:5, すばらしい洞察)
「一方、ソフトバンクはケーキを人数分用意するのがNTTの役目だと主張した。」じゃない？
Re:一方…… (スコア:1)
>> 一方、ソフトバンクはケーキを人数分買ってきた。
>「一方、ソフトバンクはケーキを人数分用意するのがNTTの役目だと主張した。」じゃない？
「一方、ソフトバンクはそのケーキが嫌いだったので、新作ケーキを人数分用意するのがNTTの役目だと主張した。」とか
長すぎてゴロが悪いね
シングルベルはケーキ分割問題の対象GUY (スコア:1)
…フフ、こんなこともあろうかとずっと独り身でいたのさ！
言い忘れたが (スコア:1)
売れ残り投げ売りを残業帰りにホールで頂くのがメタボ・ガイの生き様さ！
Re:言い忘れたが (スコア:2)
応用問題：ワンホールのケーキを買い、1人では食べきれないので一部を明日に残しておくとする。今日の自分と明日の自分で、もっとも満足が大きくなるような切り分け方は何か。
（註）「今日の自分はクリームこってりOK、明日は二日酔いなので脂肪分は軽めに」といったように、今日と明日で評価関数は異なるものとする。
# チキンでも応用可。（手羽を今日食べるか、胸肉を明日にまわすか）
今日を生きるメタボ・ガイ、明日は明日の飯を食う (スコア:1)
メタボ・ガイの辞書に食べきれないという文字はないのさ…。
Re:今日を生きるメタボ・ガイ、明日は明日の飯を食う (スコア:1)
4つではなくてふたつで充分な理由は？
Re:言い忘れたが (スコア:1)
ですので、食べるまで、もしくは食べた後にどれだけ満足を増やせるかがポイントです。
ということで、まず買ってきた日は食べません。
買ってきたことに満足し、明日食べることを楽しみにして寝てください。
翌日の朝も食べません。おいしい物は待てば待つほどおいしくなる物です。
昼もまだ食べません。いつか食べる時を待ち、味を想像し、
それを食べて至福の時を味わう自分を想像して満足してください。
そして、もうこれ以上は無理という状況まで待ってから、
一気に食べ尽くすのです。
これだけ食事を抜けば、ワンホールぐらい朝飯前です。
# 妄想は力だ！
答えはある。それを見つける能力が無いだけだ。
Re:言い忘れたが (スコア:1)
このアルゴリズムの致命的な問題：
目の前にあるケーキを食さず寝られるような人はメタボにならない。
パイに応用すれば (スコア:1)
Re:パイに応用すれば (スコア:1)
NTTご本尊が「俺は公平だからな」「俺がいないとお前ら、パイをちゃんと公平に分けられないだろ?」と主張している、ということではないでしょうか?
で、それに対して東西が「いや、おれたちは cut and choose 戦略でいいよ」「俺ら、価値観一緒だし」「もう上納金はなしな」とか逆らい始めると面白いという…。
fjの教祖様
ん？その前提は成り立つの?? (スコア:1)
うん？ それはつまり 両者が同時に切りたい場所を申告するための公平な環境が必要だよね。話を簡単にするために「中間でカット」することは実現できたと仮定するとしても。
それを2者だけで実現可能なのか?
ちなみに3者を導入すると「裏で取引」が発生する余地が出るので、「公平な第3者」前提は一般には使えないはずなのだが…。
一方で、「同時」とかの条件って、順序性を保証する場合と違って確認が難しかったはずだが…。
# 難しいからこそ手品ができる。
なんか一番大事な部分が説明されていない気がする。
fjの教祖様
Re:ん？その前提は成り立つの?? (スコア:1)
箱に入れるとき、箱に入っている間は問題ないとしましょう。それでも箱から取り出すときにすり替えることができる。
もちろん、常にすり替える事ができるとは限りませんが、すり替えることができてすり替える価値がある場合は、すり替えることができる、というのであれば「公平な場」とは言えますまい。「確率的に」すり替えのチャンスが発生する場合があるなら、その段階で「公平な場」とはいえないはずです。
一方で、「たまたますり替えられない状態」だった場合には、その回の交渉を決裂させて再度1からやり直しにすることで「すり替えのチャンス」を作る、という戦略があり得るはずです。
.
たとえば。文字通り同じ動作を二人が同時に行っていることを証明することができないとしましょう。ジャンケンですら、微妙に後出しをすることができますよね？あのように厳密な同時性を証明できない世界を考えてください。というか、厳密な同時性を証明できるなら、その段階で問題は解決していますが、厳密な同時性の証明は他のアルゴリズムでは前提としていないので、ここでもないことにしましょう。
この場合、自分の要求を紙に書いて箱に入れる所までは、紙に何を書いたのか互いに秘密にするとしましょう。で、箱の中に紙がある間、紙をすり替えることは不可能だとします。
しかし、同時性が保証されていない世界では、紙を取り出すときに1つづつ取り出すしかありません。また「二人で一緒に１つの紙を取り出す」のも難しいでしょうから、「どちらかが1つを選んで取り出す」事になるはずです。この場合、1つ目の紙を取り出した段階で「その1つ目の紙に書いてある情報」は両者で共有することになります。仮にこの紙がAさんの主張だったとしましょう。
- 箱の中にはBさんの主張が書いてある。
- Bさんは紙になんと書いたのか判っている。
- BさんはAさんの主張を知っているので、紙をすり替えることで有利な立場に立てる。またそのための紙は用意してある
という条件が揃った。Bさんの戦略は次のとおりになります。
a) Aさんが取り出した場合は、Bさんは紙になんと書いてあろうが「そんな記述をした覚えはない」と交渉を破棄する
b) Bさんが取り出した場合は、紙をすり替える
.
b が実施可能な場合、この場は「公平な場」とは言えません。
しかし、a のせいで「公平に分割する」に至りません。「千日手」状態が起こるだけです。この場合も「公平な場が設置できた」とは言えない。
cut and choose のような戦略はこのような「千日手」状態が発生しません。なので cut and choose よりも「よい」戦略であるためには、「千日手」状態を発生させないような「場」の提示が不可欠のような気がするのですよ。
.
この問題の厄介なところは「ハッシュ」などの確率論的な同一性証明は「証明になっていない」という点です。たとえ 1/2^128 の確率であろうとも、「一方の紙の中身だけがすり替える前とすり替えた後が同じハッシュ値になる(もう一方は同じ値にならない)」なら、公平な場とは言えない。なので、紙に書いた内容のハッシュ値を、箱から髪を取り出す前に宣言する、という手は使えない。
じゃぁ、自分が紙に書いた内容を事前に宣言するなら? 同時性が保証されないのなら、「後で宣言する」側が有利になる。つまり、Aさんが先に宣言し、Bさんが後に宣言するとして、今Bさんが箱の中にある内容よりも有利な条件を思いついたなら、宣言の際にわざと紙に書いたのと違うことを言って、交渉を決裂させる事ができる(もちろん、ハッシュを使っていても同じこともできます)。もし、万が一にもBさんの紙を箱から取り出す際にすり替えが可能だった場合は、「宣言したのと同じ内容を書いた紙」とすり替えればよい。
「千日手」状態を発生させない条件が見当たらないわけです。
fjの教祖様
Re:一人が切って、もう一人が選ぶ (スコア:3, 参考になる)
今回のネタは「二人が異なる価値観を持っている」ことです。
例えば、一方は、とにかくたくさん食べたい、もう一方は、おいしいを少しだけ（カロリーを気にしている？）とかのばあい、タイトルのような分け方は公平とは言えないのです。
Re:ダッチオークション (スコア:2)
手順
1.くじ引きで1人を選ぶ
2.選ばれた人は、自分が1/ｎであると思うところに印をつける
3.残されたｎ-1人に異論がなけば、それを切って自分のものにする
4.異論がある人は、印よりも少ない価値で新たな印をつける
繰り返し。
Re:ダッチオークション (スコア:2)
異論がある人が、それじゃ多すぎる、もうチョット少なくとオークションしていくわけです。
不満のない人は残りの方が取り分が多くなるので、オークションから降りておきます。
価値観が異なるときも、方法は同じで、
価値観ａの人がＡポーション、価値観ｂの人がＢポーションというように印をつけます。
残された人は、それぞれの価値観に従って、ＡもＢも不満があるかどうかを評価します。
何十年か前の多湖輝さんの「頭の体操」で、ジュースの分配問題として出題されていたと思います。
Re:ええと・・・ (スコア:5, 参考になる)
これは「ケーキ分割問題」（とか無羨望分割問題）という有名な問題で，ケーキ（というかより一般的に分割される何か）は均一ではありません．ケーキの例で言うなら，苺がいっぱい入っている部分もあればチョコの家が乗っている部分もある，さらには人によって苺が好きな人もいればクリームが好きな人もいる，そう言うものを誰からも文句が出ないように分割するにはどうすればいいか？と言うような問題です．
そのため，「申告した場所」というのは例えば，Aという人物が苺の多い部分を含む領域を指定し，Bという人物がクリームの多い部分を含む領域を指定したら，アルゴリズムに基づいて分割線を決定した後，Aは苺の多いパート，Bはクリームの多いパートを取る，とかまあそんな分け方です．
各人が異なる価値評価関数を持っているため，例えば「2人で分割したとき，各人が（それぞれの価値観において）ケーキの価値の1/2以上を所持している」という状況を目指すわけです．これがさらに3人，4人と増えていくと大変なことになります．
どういうアルゴリズムを使えば各人にとっての価値が最高になるか，公平になるか，など，今でも研究している人がいますし学会発表もあった……はず．
Re:ええと・・・ (スコア:1)
>ケーキの例で言うなら，苺がいっぱい入っている部分もあればチョコの家が乗っている部分もある
ところで水平方向に切るというのは、ありなのかな？
以前、ケーキを、「切ってください、体積が大きい方をわたしが貰います」とかいうのに、そうやって、上のクリームとイチゴがたっぷりのところと、土台に切り分けて土台をあげたらむくれていた。
Re:ええと・・・ (スコア:2)
人でなしがいる・・・
Re:ええと・・・ (スコア:1)
分けた後の選択基準が分からないんですよね。
「チョコレートプレートが乗ってる方」と「イチゴが多く乗ってる方」で分けろ、とすると両方乗ってる部分と両方ない部分に分割された場合合意できない。
「それぞれの要求物が分割されるように線を引く」「あくまで面積（体積）は２等分とする」とかいう前提条件でもあるのかな。
２つの要求が排他的ならまだ分かるんですけどね。
「イチゴがたくさん欲しい人」と「イチゴがまったく要らない人」で欲望のままに分割させたらだいたい５割づつイチゴが分配されて……
あれ、両方ともイマイチ不幸じゃね！？
Re:ええと・・・ (スコア:2, すばらしい洞察)
>「イチゴがたくさん欲しい人」と「イチゴがまったく要らない人」
イチゴがケーキの上にだけある場合はケーキを上下に二分割(幽霊綺譚)
らじゃったのだ
Re:ええと・・・ (スコア:1, おもしろおかしい)
チョコレートプレートなら場所動かせばいいじゃん。
Re:応用問題 (スコア:1, すばらしい洞察)
Re:応用問題 (スコア:1, すばらしい洞察)
日本以外が「日本とその国の間の何処か」ではなく「日本をその内側に含めるような何処か」に線を引いてしまう気がする。
Re:ジョークRFC? (スコア:1)
-- 哀れな日本人専用(sorry Japanese only) --
Re:ジョークRFC? (スコア:1)
いえ、この部分に関しては、「ちょうど中間合意問題」に帰着しただけです。別に本当に中間である必要性はない。両者が納得していさえすれば。
# そして、この問題はすでに解決している。
fjの教祖様
Re:ジョークRFC? (スコア:1)
空気の読めない男がせっかく掴んだチャンスを無残な結果に終わらせないようにという、
NTTからのクリスマスプレゼントに違いない。
Re:我が家の回答 (スコア:1)
>小さなケーキを人数分買う。
各自に好みの小さいケーキを買ってきたはずなのだが、
なぜか家に着くと、あっちの方がいいということで紛糾したりする。
次回、同じショートケーキにしても、あっちの方がいちごが大きいとか紛糾する。
文句があるなら、やらないよ..と全部食べてあげたら泣いていた。