【話題】NTT、「ケーキ分割問題」を新アルゴリズムで解決　応用として、共同出資した油田の採掘エリアを平等に分割など［10/12/24］

一つのクリスマスケーキを２人で公平に分けるには、どこにナイフを入れたらいいか？。
長年未解決だった、数学の難問「ケーキ分割問題」をＮＴＴが解決した。
ビジネスの取引などに使える実用的なアルゴリズムになるという。
提案したアルゴリズムの正しさを証明し、このほどコンピューターサイエンスに関する
国際会議で発表した。

ＮＴＴが開発したアルゴリズムによる解答は、
（１）ＡとＢがそれぞれ、切りたいケーキの場所を（第三者などを通じて）同時に申告する
（２）切りたい場所が両者で異なっていた場合、そのちょうど中間にナイフを入れる
（３）申告した場所を含む側のケーキを両者が得る
？というもの。もちろん、（１）で申告した場所が両者で一致した場合はそこで切り分ければよい。
この方法で行えば、２人が満足のいく形でケーキを分割することができる。

古典的な解法に、
（１）Ａがケーキを切る
（２）Ｂが好きな方を選ぶ
（３）残りをＡが取る
？という方法がある。Ａは自分が損をしないよう平等に分割し、またＢは優先的に選べるため、
一見、公平な方法のようにみえる。だが、例えばケーキに乗っているイチゴの好き嫌いなど、
ＡとＢの好みが分かれる場合には、最初に選ぶ方が切る方よりも有利になることが分かっている。
すなわち、分ける／選ぶという役割の違いで不公平さが生まれる。

開発手法は、役割を平等にすることでこの本質的な課題を解決した。
ケーキは細長いロール状のものが考えやすいが、丸いホールケーキでも基点を決めて角度を
指標にすれば同じ手順で切り分けられる。
ＮＴＴは今回、２人で分割する場合と、３人で分割する場合（６切れになる）について、
このアルゴリズムが正しいことを証明した。４人以上で分割する場合も今後、証明に取り組む。

実社会への応用では、街頭ディスプレーの表示時間を複数の会社でうまく割り当てたり、
共同出資した油田の採掘エリアを平等に分けたりなど、複数の組織間で一つのものを公平に
共有したい場合に使えるという。

ソースは
http://www.asahi.com/digital/nikkanko/NKK201012240013.html
NTT　http://www.ntt.co.jp/
株価　http://company.nikkei.co.jp/index.aspx?scode=9437

>>共同出資した油田の採掘エリアを平等に分割など

（｀ハ´ ）そんなもの必要ないある

（１）ＡとＢがそれぞれ、切りたいケーキの場所を（第三者などを通じて）同時に申告する
（２）切りたい場所が両者で異なっていた場合、そのちょうど中間にナイフを入れる
（３）申告した場所を含む側のケーキを両者が得る

（４）そしてケーキの持ち主Ｃは泣いた。

「パンが無ければケーキを食べればいいじゃない」

その中間地点を決める際に戦争が起こるんですね分かります

（１）ＡとＢがそれぞれ、切りたいケーキの場所を（第三者などを通じて）同時に申告する
（２）切りたい場所が両者で異なっていた場合、そのちょうど中間にナイフを置く
（３）申告した場所を含む全てのケーキを勝者が得る

（４）ミキサーで撹拌、計量カップで

ごちそうさまでした。ふぅ。

Ａが核武装して、ケーキを全部取る

Ａが「自分は発展途上国でこれまでケーキを食べられなかったのだから
これまでケーキをさんざん食べてきた先進国Ｂは我慢すべきだ」
といってケーキを全部取る。

ロウソクが立ってる時も真ん中で分けるって事か
どんなナイフなんだろう

景気よりケーキ　ｂｙ　民主党

昔からよくある手だが
Ａがケーキに唾をかけてＢが食べられなくして全部取る。

Ａがケーキを持って逃亡し、逃げながら全部食う。
捕まっても胃に入ったものは戻せない。

力関係でＡが負けそうな時は、ケーキを床に落とす。
そうすればＢも食えず引き分け。デタント。

よろしい。ならば戦争だ。

なんか当たり前のアイデアのような気がしないでもない
これって画期的なの？

>>2
まぁそうだろうなｗ
日本人(特に関東人？)は皿に残った最後のカラアゲ一個を遠慮する性質らしいが、
日本が>>1を使って”ジャンケン”しようという相手は最後のカラアゲ巡って取り合いするような国ばかり

Aが1/2、Bが2/3を主張したとして、その中間にナイフを入れてAは納得できるのか？
結局は互いに1/1を主張するので半々に収束するということ？
というか、ケーキのたとえがよろしくないのか？

ケーキの領有権を主張して、相手がひるんでいる隙に全部取る

申告場所の中間にナイフを入れることが両者とも分かっているのなら、
互いに全取りに近い形を申告してくると思うから、イチゴの好き嫌い
の問題はいずれにせよ解決しないのではと思うのだが、俺の理解が
間違っているのかな。

>>18
関東人は遠慮する性質だよねえ

【東京】目黒のさんま祭り、熱々の焼きサンマを６千５００匹無料配布−３４度の炎天下で５０００人が行列
http://kamome.2ch.net/test/read.cgi/newsplus/1283680168/
【東京】銀座　ユニクロに２０００人以上が行列、あんパンと牛乳も無料で配られる
http://www.nikkei.co.jp/news/past/honbun.cfm?i=AT2F2002K+20112009&g=MH&d=20091121
【東京】月2回“10円まつり”を開催する激安スーパー　開店直後には売り場に客が殺到、100人200人の行列は当たり前
http://news.walkerplus.com/2009/1116/3/
【東京】「タダでもらえてうれしい！｣ カップヌードル３万食を無料配布 ２時間待ちの行列-渋谷★４
http://blog.livedoor.jp/caladbolg2/archives/51232113.html
【東京】無料ダイヤ5000人大混乱「仕事休んじゃっているので。駐禁切られています」
http://www.afpbb.com/article/entertainment/fashion/2607580/4215478
【東京】無料のさんまに殺到1万6000人　行列は最大1.5キロメートル　3時間並んで手に入れた人「テレビを見て来た」
http://shinagawa.keizai.biz/headline/718/
【東京】目黒　サンマは無料に限る　前日夜や夜明け前から並ぶ参加者も　行列は最高で２時間待ち、１キロを超す
http://yutori7.2ch.net/test/read.cgi/liveplus/1253666840/
【貰えるに弱い東京人】金が戻ってくる還付金詐欺、東京がﾜｰｽﾄ・最多1083件
http://pc11.2ch.net/test/read.cgi/antispam/1234230074/
【東京】ブランド牛もタダ！激安“肉の祭典”に4000人が行列　無料試食コーナーに朝から長蛇の列
http://yutori7.2ch.net/test/read.cgi/liveplus/1255792795/

Ａが「歴史的に見て、この領域はわれわれのものだ」と言って実効支配する。

ナイフを相手の胸に刺して殺した後で全部取る

>>17
だよなぁ
閉鎖された仕事で、自分の研究が取り残されてる事に気づかないんだろ

これ、申告の時に最大申告値を50％以下にしたらいいのかな

ＡとＢの希望するところが重なってないことが前提じゃないのか？

これで、嘆きの壁もイスラム教徒とユダヤ教徒で仲良く等分出来るんですね

くだらねーことしてるんだったら7万円早く返せよ

>>24
それ、中国だろw

>（１）ＡとＢがそれぞれ、切りたいケーキの場所を（第三者などを通じて）同時に申告する
>（２）切りたい場所が両者で異なっていた場合、そのちょうど中間にナイフを入れる
>（３）申告した場所を含む側のケーキを両者が得る

尖閣諸島問題で当てはめてみると

日本は国際ルールに則り、日本と中国の間の線を国境とする
中国は国際ルールを無視して、日本全土は中国領土とする。

よって、その中間線を領土としたら、日本の大半が中国領土になる

・・・・ダメじゃんw

その第三者が両者とまったく無関係であることを誰が証明するんだよ

お菓子がないなんておかしいじゃない

>>21
俺もそう思った。

>>1の例えが悪いのかもしれんが、これじゃ解決しないと思う。

これが論文の概要
http://www.springerlink.com/content/p26w511604p01173/
これが論文の内容に対応するものだろう
http://www.brl.ntt.co.jp/people/manabe/cutMFCS.pdf

図が全くないので、ぜんぜんわからん

>>31
そういう場合は日本も中国全土を指定すればいいんじゃない。
小さい国が得をする。w

NTTｪ…

まず、ケーキを食べる権利が2人にあることを証明しないとな

>>36
ケーキの大きさを決めるときにもめるな

ケーキの上半分がほしいといった場合はどうなる？

たとえば、ダイヤモンドのように2つに割ると無価値になるものの場合の
問題が全く解決されていない件。
　
大半のものは2つに割ることができないし、割ると不幸になる

>そのちょうど中間にナイフを入れる

これが難しいんだろ

油田も均等に油が埋まっているならいいが
双方が「鉱脈」の部分だけをほしがるものだ
　
「中間に線を引く」という車輪の再発明を褒め称えるほど
世間は甘くない

大人で経験豊富なら　妥当な解だな

自分勝手は交渉の現実になえるものよ

80、90年代の利己主義が大前提になっている
21世紀の日本人ならもうちょっとましな
イデオロギーを見つけろ

ケーキに毒を仕込んで相手に全部渡す

>>2
ケーキを切ろうと箱を開けたら
シナが勝手に食い散らかした後だった…

某ガス田油田のことかｗ

その分割方法に対し拒否権を行使し認めない

プログラムのアルゴリズムとしてなら面白いな。
けど、他の問題の解決には役に立たんだろう。
例えば資産相続とかにも使えそうだが、これで解決出来るとは思えん。
まして油田の採掘エリアを平等に分割とかｗ土人国家相手に理屈なんか通用せんよ。

ナイフについた生クリームは誰がねぶっていいんだ？

前提条件が足りないんだよな。
立場を入れ替えることが出来る場合に限るんだ。

ケーキの右半分と左半分、どちらを選ばれされるかは解らない。

これと同じ事、小学生の時先生に聞かれて、そのＮＴＴの答えだした奴何人か
いたな。

>>52
NTTをバカにするな＞＜

ケーキを二つ買えばいいじゃない

>古典的な解法に、
>（１）Ａがケーキを切る
>（２）Ｂが好きな方を選ぶ

子供の頃、姉にこれをされて、いつも姉にケーキの大きい方を持っていかれたのを思い出した。('A`)

日本人は「どうやって均等に分けるか」を考えるが
欧米人や中国人は「どうやって全部取るか」を考える。

ミキサーで粉にしてから分ければいいじゃない

１時の場所に板チョコ・３時にイチゴ・５時にチェリーの乗ったケーキなら
２人とも１２時と６時のラインで切って、右半分を欲しがるだろう。

それをまた３時の位置でわけても、どちらも板チョコが欲しかったらどうなる？
それをまた・・・なんて、油田でやれねーだろ普通。

一方ロシアでは全員撃ち殺して独り占めした。

完全な円筒状のケーキで、上面の半分にイチゴが乗り、半分はそのままの
ものを考える。Ａ，Ｂともイチゴが好きなので、両者ともイチゴ面と非イチゴ面の
境界線で円筒を切断することを主張する。両者の意見が一致しているので、
その面でカットされる。ついでＡ，Ｂにどちらが欲しいかを聞くと、両者ともイチゴ
が乗った方を選択する。ＮＴＴアルゴリズムでは解決できないことが分かり、
カットしたナイフで勝負をつけて勝者がイチゴ側を取るとルールを変更する。
これでＮＴＴアルゴリズムも完全なものとなり、勝者も最初の希望がかなう。
敗者？資本主義だから敗者がでるのは必然。何の問題も無い。

これは無意味だな
アルゴリズムと呼ぶのも愚かしい
互いに全てを申告して結局半分になりましたという結末で
本来の権利者は大損というパターンしか見えない

ガ板に

ケーキを平等にわけるガイドラインを立てたらいいと思う

６０に追加だが、６０の場合、両者が選択したイチゴ側について同じアルゴリズムを
適用すればよいかもしれない。だが、繰り返しをゆるしたとしても、どのような分割に
おいても不平等が残り続けるようなトッピングがあれば、無限後退を招いてアルゴリズム
が終了しないことになるな。具体例はとっさには思いつかない。

で、結局イチゴはどうすればいいんだ

共同出資して、これから回線が敷かれる部分に関してでしょ
きっと加入しないだろう限界集落や山の中の一軒家に回線敷くのに
NTTが共同出資に関与しなくても良いて事だ

>>64
じゃあオレがもらうよ

>>35
意外と年のいった人だな

真鍋　義文
http://www.brl.ntt.co.jp/people/manabe/index-j.html
1960年12月7日大阪で生まれる。
1983年3月大阪大学基礎工学部情報工学科卒業。
1985年3月同大学院博士前期課程(いわゆる修士課程)修了。
1985年4月日本電信電話株式会社入社。
現在、同コミュニケーション科学基礎研究所協創情報研究部主幹研究員。
2001年4月〜 京都大学大学院情報学研究科社会情報学専攻 客員助教授（准教授）。
2002年〜2004年　大阪大学大学院情報科学研究科　非常勤講師。
1994年〜95年米国The Johns Hopkins大客員研究員。
1993年3月 博士(工学)取得（大阪大学)

岡本 龍明
http://www.ntt.co.jp/RD/OFIS/achievements_okamoto.html
1976.3　東京大学工学部計数工学科卒業
1978.3　東京大学工学系研究科計数工学専門課程修士修了
1988.4　東京大学 博士（工学）取得

1978.4　日本電信電話公社入社
1978.5　横須賀通信研究所データ通信研究部　勤務
1985　　情報通信処理研究所　勤務
1989−1990　カナダ Waterloo大学 客員助教授
1994−1995　AT&T Bell Laboratories 客員研究員
現在　日本電信電話株式会社　情報流通プラットフォーム研究所　情報セキュリティプロジェクト、R&Dフェロー、主席研究員

いっぽうロシアはロシアンルーレットを相手に要求した

パターン認識関係で、そんなアルゴリズムいっぱいあったな。
どこが新しいか、よく読んでみないとよくわからないな

>>21
全取りしようとすると少なくなる。
自分の主張した境界が含まれるほうだから。
Aが1/2で分けて、Bが全取りしようとすれば、Bは1/4しかもらえないことになる。

>>60
同じ体積じゃなくて、同じ価値になるように分ける。
イチゴが大好きならイチゴの数を半分にするとか。
だから、どっちをとってもAもBも不平等はない。

4人以上のときに解無しになったらもっとおもしろんだが

>>70
＞自分の主張した境界が含まれるほうだから。

！！！そういうことか！！！すげー！！！

全部俺のものだ何言ってんだ

>>15
ワロタｗ

>>70
前半>>21へのレスは納得できたけど
後半>>60へのレスが理解できないんだが
馬鹿、つまり私でも分かるような説明を御願いしたいのだが

ところで3人の時の説明もできれば御願いしたい

金銭価値での等価交換にまさるものなし

そもそも均等に分けるというのは
囚人のジレンマでいう（協力・協力）状態だが
この状態はナッシュ均衡ではないから実現されない。

で、３人以上の場合はどうなんの？

論文読んでないが、これ記者が勘違いしてるんじゃないかな？
あるいは例が悪いのかも
実際はこんなにシンプルな話ではないはず

ついでに社会福祉の富の分配もこれでやったらいいのに

え？お前のものは俺のものだろ。

>>75
>>70じゃないが。

それぞれが『価値が均等』と考えるように分ける。

イチゴの乗っている部分がイチゴの載っていない部分の三倍の価値がある、と考える人は、
イチゴ有部分の三分の２か、イチゴ有部分の三分の１とイチゴ無し部分の全部、で切ろうとする。

イチゴには価値が無いと考える人≒イチゴ有りとイチゴ無しが等価と考える人は、中央で切ろうとする。

その間で切ると、イチゴ好きはイチゴ部分の6分の5、イチゴ嫌いはイチゴ無し全部とイチゴ有りの6分の１を得る。

どちらも自分の価値観にとって半分以上を得る。

>例えばケーキに乗っているイチゴの好き嫌いなど、
>ＡとＢの好みが分かれる場合には、最初に選ぶ方が切る方よりも有利になることが分かっている。


公平に切ったんだから、どう選ばれようと文句がでるはずがないのでは？
なんで有利なの？

理解できんぞ。
中間で切るんだったら、最初に沢山申告した方が得じゃないか。

>>83
考えたが、つまり、死んでもイチゴが食いたいという場合、イチゴをとられたら負けだからだな。

>中間にナイフを入れる
これができないから揉めるんじゃないのか？
話がループだ

>>83
右端にイチゴが入った長さ30cmのロールケーキがあるとする。
Aさんはイチゴが好きなので「右から10cmの位置で切るのが公平だ」と考えてケーキを切った。
Bさんはイチゴに何の思い入れも無いので迷わず左側を選んだ。

もしBさんに切らせたとしたら、真ん中にナイフを入れたであろうと考えられる。

つまり好みに差がある場合は切った方が不利。

>>84
両者が申告した中間で切って、自分が申告したラインが含まれる側を貰える。
>>87の例で言えば、Aさんが「右から25cmが公平だ」と多めに主張した場合、
イチゴが入ってない上にサイズも小さい「左端から10cm」のケーキを手にしてしまうことになる。

オークションデザインとかメカニズムデザインとかゲーム理論にも関連してそうだな

考えるのめんどくさいから、ケーキをミキサーに入れて、
重量で均等割すればいいんじゃない？

まあ、食べる気にならないとおもうが。

>>87-88
そういうことか。理解できたわ。ｔｘ

クリスマスケーキって一人で食べると侘しさが募るよ(´・ω・`)

客観的に公平かどうかなんてまったく関係ない
主張ぶつけ合って、俺の意見のほうがあいつより通ったって
全員が思い込める回答を出せってこと

これは結構おもしろいな。
等質なロールケーキで考えて、欲張ると取り分が減ることがあるし、
逆に相手が欲張ることを見計らって少なめの主張をしても、相手も少なめの主張だと取り分が減るし。
こんな駆け引きを外国相手に日本ができるのだろうか。

「なにが公平か」の定義もせずにこの議論をするのは無意味。
俺は嫌いだが、あのサンデルでもその定義から考えるだろうよ。

センとかロールズの議論を読んでから「公平」の議論をしてくれ。話はそれからだ。

公平なんて最初から求めてない、無羨望分割を求めてる

おいさっき買ってきたケーキ、イチゴが二つしか乗ってないのだが…


どうやって四人で分けんだよ！！

お父さんの仕事は切ったケーキの残りカスを集める仕事

結局各自冷蔵庫にあったイチゴを乗せまくることになったよ。

＞一つのクリスマスケーキを２人で公平に分けるには、どこにナイフを入れたらいいか？
ケーキが均質な場合、ちょうど中間だよね。

＞切りたい場所が両者で異なっていた場合、そのちょうど中間にナイフを入れる
その理論だと、この「ちょうど中間」がどこかで、意見が分かれてまた同じ手順がループすると思うんだが。
ここでループしないのなら、最初の最初の段階の「ちょうど中間」で解決してるし。

つうか、ケーキごときのちょっとした差で文句いわないよなフツー。

>>100
ちょうど中間でなくても、両者とも(自分の価値観での)半分以上を得られるから画期的なんだ。

>>95
文系だなお前。この手の議論は、「選好」が厳密な関数として表現できる場合だけを
対象にする議論なの。お前の主張は、サッカーの試合を見ていて「手を使ってゴール
すればいいのに」と言っているようなもの。馬鹿の極みだ。

>>100
「ちょうど中間」も同じく、厳密に定義できる場合のみを議論の対象にするんだよこの手の
議論では。だから最初からそういう議論は埒外にある。

>>82
６０だけど、両者とも完全に同等の価値観を持った話をしているんだけど？

ついでにケーキ回復のアルゴリズムも考えてほしい

これでいいじゃん
ttp://www.nhk.or.jp/medes/quiz/resolve/20100916.html

他の人も書いてるけど
「ちょうど中間」に分けることができるのならば、
最初から全体を「ちょうど中間」に分ければいい

例えば、その中間の部分のどちらかに偏って
いちごがあったらアウト

こまけーことはいいんだよｗｗｗ

ケーキの端にイチゴが1個だけ乗っており、イチゴは分けられないものとする。

Aはイチゴが絶対欲しいので4:6ぐらいの所を指定した。
BはAがイチゴ好きであると知っていて、あえて2：8ぐらいの所を指定した。

結果3：7の分割となり、Bがイチゴ付きの3をAがイチゴなしの7を取ることになった。
ここでBがAに交換を持ちかけると…Aが損してBが得することになってしまうわな。

test

>>107
「イチゴは分割不能で、Aはイチゴが絶対欲しい」
Aはイチゴなしの場合は0点なの?
イチゴの取得の有無が勝ち負けみたいになってしまうなら
それはもう、分けるという概念が通用しないんだから
問題として成立してないんじゃないの。

>>102
>>60の誤りは、二人ともイチゴ面と非イチゴ面の中間で切ろうとする、と言う部分。

このルールでイチゴが載っている方を取るのは、イチゴが載っている側を過大評価(載っている側は小さくする)した側だから。

君のような人が相手なら、俺は半分よりほんの少しイチゴ側を小さく切るのが中間と指示することによって、ほぼ半分のイチゴが載った側を得られる。
決闘なぞ起こらない。

ほとんどの人は、君よりは頭がいいので、>>82で書いたような指示を二人とも出す。

つーか、実際がどうであろうと現実の世界では皆が平等だと思えば平等。
人間が知り得ることは脳が認識したことだけ。
突き詰めて、こうだから平等じゃないんです、
みたいなことを言うやつがいるから皆が平等じゃないと思い始める。

>>102
じゃお前は理系か？そうやって「厳密に定義される」を盾にして、曖昧になりかねない
議論から目をそらしちゃいかんよ。

あ、俺文系だけど一応経済だからこういう問題は「分配の公正」みたいな問題と結びつけて
考えるから。公平とか公正の定義を厳密にしないと話が進まないの。そうすると
どうしても曖昧な部分が出てくるからあまりに厳密に選好を定義すると理論が成り立たなく
なるのがミクロ経済、特に分配を扱う分野の特徴な。

つか、『お前の主張は、サッカーの試合を見ていて「手を使ってゴール
すればいいのに」と言っているようなもの。馬鹿の極みだ。』

この喩えがよくわからん。畑違いのことを言うなと言いたいのか？

>>112
すまん。公平とか公正の定義を「厳密に」じゃなかった。
「論者の考える公平や公正の定義を明確に」しておかないと話が進まないのな。

最初に「公平に分けるには」と書いてあるのだからここでいう「公平」とは何であるのか、
はっきりさせなきゃいけないのは当たり前の話だと思うが。

>>113
逆じゃね？
この選び方で分けた結果が公平なんだよ

中身の質が不均質だが形状が一定のロールケーキがあった。
左から右へ、０から100までの目盛りが刻んである。
ＡとＢが、それぞれ均等と思える分割線（この線ならどちらをとってもいいと思える位置）を決める。
Ａは40の位置、Ｂは60の位置を希望した。
そこで、まずＡは1から40までを、Ｂは60から100までを取り、残の40から60までについて、再び線を出し合った。
すると今度は45の位置で一致したので、円満に分け合った。
希望する線の中間=50で切ってたら、喧嘩になるところだった。

あれ？

油田じゃ無理だろ？平面だと切り方が複雑すぎる。

>>115
最初から中間=50が、平等であるべき地点だと、
第三者の目でみてるから違和感があるんじゃないの。
1回目の試行が終わった時点で、その後の処理を中間点で決めず
もう一回同じ手続きで決めようと、双方合意してるのだから
ゲームは振り出しに戻ってる。

>>117
第一回の試行で残った分を、単純に「中間」で分けられるほどこのケーキが均質なら、初めからややこしい手続きをする必要ないよね。

>>118
1回で決めようの場合は、あまりが出たときの処理を単純な中間点で決めましょうは
決め事としては双方なっとくできるんじゃないかな。
試行回数を無限にできるなら、>>115のように一致する点が求まるまで繰り返すのが
より納得度は高いとは思う。
でもどちらのやり方を採用するかは、1回目の試行結果が出る前に決めておかないといけない。
1回目の結果をみて、このまま中間で決まると自分にとって不利だから、
もう一回やろうぜは、提案として受け入れられないだろう。

>>119
中間線と最初に決めておけば、公正な分割方法ではあるが、結果的にどちらかは相手に多く取られた感を残す。
ほんのわずかでも相手に多く取られるのは絶対いやだ、と考えるなら、この取り決めを飲むことは最初からできない。

イグノーベル賞狙い？

>>112
俺は文系（哲学）→現在理系（人工知能）だ。

＞そうやって「厳密に定義される」を盾にして、曖昧になりかねない
＞議論から目をそらしちゃいかんよ。

＞この喩えがよくわからん。畑違いのことを言うなと言いたいのか？

理系では、厳密に定義される限りにおいて語れるものを語る。もちろんそれでは捕らえ切れない
ものを切り捨てることになるが、それも織り込み済みで議論を進める。言い換えれば意図的
戦略的に「曖昧になりかねない議論から目をそらし」て議論する、それが理系のやり方だ。だから
これに対して「まず〜を厳密に定義してからじゃないと意味内」とか言うのはまったく筋違いだと
言うことだ。だったら永久にそこで足踏みでもしてろということだ。実際哲学は永久に足踏みしている。
まあ少しづつ個別科学へと展開はしているがな。

>>120
1回の試行で決めなければならない場合、AとBの分割地点が一致した場合は双方納得。
そうでない場合残りを中間点でぶった切って、その結果がアンバランス(誰の価値に照らし合わせては置いておいて)
である確率がどれほどあるかわからないが
それは双方がリスクとして取った結果なのだからいいんじゃないの。

Aが切って、Bが選択する式の決め方よりは、双方が同じリスクをとるのだから
よりマシだよねって話じゃないの。

もう寝る。

論文読まずに書くと、ゲーム理論が入ってる話だと思うんだけど、
そんなのが入っててコンピューターサイエンス的に「証明」とかできるのか？
あと、二等分はいいとしてＮ等分は？

>>123
この分割の深刻度によって、そのリスクを取る気になるかが変わると思う。
まあ、その場合は試行を複数回繰り返す取り決めをしておいてリスクを減らせばいいのだろうけど。

だから、>>1 の解法は、ここで終わるのは不親切と思った。

真の平等はケーキがあったらケーキを捨ててしまうことだ
そうすれば誰も得をしないし争いも起きない

この条件の絶対必要条件は、第3者が第3者で無いといけない。
第3者がもしどちらかに寄れば、その時点で不公平が生まれる。
第3者の第3者が必要になってくる。

>>126
損してるじゃないか

え？

フツー、ＡがナイフでＢを刺殺。
で、Ａが丸どりで終了だろ？

俺の言いたいことが>>19に集約されてた

つか、AもＢも全部総取り希望するだろ。このアルゴリズム

>>130
ここまでちゃんとこのスレのレス読んでるか?
総取り希望すると結果的に損するんだよ

ロールケーキを角度をつけずに切るみたいに
分割方法がスカラーで決定できるものは
なんらかの中間を選ぶことができるけれども、
ホールケーキを任意の角度できることができる場合にはどうすればいいんだ？

お互いの評価関数を知らないことが前提なのかな。
評価関数が相手に知られていたら1回の試行ではうまくいかなくて
>>115のようにしないといけないのだろうか。

（第三者などを通じて）

この時点で二人で分けると言う前提に違反しているじゃん

中間と第三者ってのが一般化できてないじゃん

全然論理的でないけど

囚人のジレンマとどう違うんだ？？
教えて、理屈臭い人

均質なケーキなら、各自1/2を主張すれば利益が最大化する

その前提に基づけば、不均一なケーキでどこが中間線か正確に分からなければ
おそらく、両者の主張する境界線が真の中間線付近で交差するから、アルゴリズムが使えない

結局何の役にも立ってないな

イチゴがどうのとか言ってるやつは馬鹿なの？

>>110
>（１）ＡとＢがそれぞれ、切りたいケーキの場所を（第三者などを通じて）同時に申告する
だから
>君のような人が相手なら
などということを事前に知ることはできないんだよ

>>110

＞>>60の誤りは、二人ともイチゴ面と非イチゴ面の中間で切ろうとする、と言う部分。

60で言ったのは、両者の選好基準が全く同一で、かつ双方とも「俺はイチゴ面のみ欲しい」
と希望してイチゴ面と非イチゴ面での切断を希望した場合、このアルゴリズムではどう判定
されるのか、という問題であって、ゲーム理論のような「勝敗」を問題にしているわけじゃない
んだが？中間を切断面に選ぶというのはそもそも「誤り」じゃなく、そう希望するとどうなるか
という議論の出発点なんだが？

>>139
どうも>>110は互いに相手を出し抜いて利益を最大化したいというゲーム理論的な
発想をしているようだ。そのわりに貴方が言うように後だしジャンケンを当然のように
使ったりと全く訳が分からん。

現実のクリスマスパーティーでケーキ分けとか、まず多人数だしね。
二人でしか使えないアルゴリズムって点がイマイチ。

>>142

>1
>ＮＴＴは今回、２人で分割する場合と、３人で分割する場合（６切れになる）について、
>このアルゴリズムが正しいことを証明した。４人以上で分割する場合も今後、証明に取り組む。\\

Cが現れた！

３人テラムズイｗｗｗCカエレｗｗｗｗｗｗ

このアルゴリズムを道州制に応用しよう。
まずは、国会議事堂を通る直線で日本を2分割することにして
もう一方の点をこのアルゴリズムを使って決めよう。

Aは自分の取り分が５割の位置で線を引く
Bは自分の取り分が８割の位置で線を引く
すると、お互いが線を引いた半分で分けるってことだから
Aは3.5割、Bは6.5割のケーキが手に入るってことかな

自分のケーキだってことをどんどん主張しないと
全部相手のケーキになっちゃう気がする

>>147
違う。
自分の取り分を主張するのではなくて、どちらも半分の価値になる位置で線を引く。
あなたが半分の線を決めたのだから、どっちがあなたの分になっても不満はないよねってこと。
そして、自分の選んだ境界が含まれる方を渡す。
そしたら両者ともに、自分で決めた半分の価値以上のケーキがもらえることになる。

２人とも食べられるケーキの量は等しい
けれども、上に乗っているトッピングが異なり好みが違っている
それをどの角度で分割して分ければいいかという問題

簡単な例で、時計の刻みのように１２個のトッピングが等間隔でおかれていて
Ａ，Ｂともに大好きなトッピング１つを得られれば満足で、そうでなければ不満だとする

Ａの好みのトッピングが3時の位置に置かれていたなら、Ａは12時-6時の範囲の3時側が欲しいと申告
Ｂの好みのトッピングが5時の位置に置かれていたなら、Ａは 2時-8時の範囲の5時側が欲しいと申告
この結果から、10時-4時で分割して1時側をＡが7時側をＢが取ることに決める
その結果、Ａが好みの3時はＡに、Ｂが好み5時はＢに分配されて両者満足

従来からある有名な方法では、
Ａが3時-9時の分割を決定して、Ｂが12時側と６時側のうち好みのトッピングがある６時側を取っていた
これによりＡは損も得もせず、Ｂはかならず満足できる

実際の問題は、１２個のトッピングそれぞれに好み加減の点数がつけられていて
Ａ，Ｂ両者にとって点数の和が悪くならないように分割したい

この解釈であってるかな？

>>149
> Ａの好みのトッピングが3時の位置に置かれていたなら、
> Ａは12時-6時の範囲の3時側が欲しいと申告
境界線のどちら側がほしいのかは言わない。
Aが3時を重視するのならば
1時-5時の領域と5時-13時の領域の価値が等しいと主張し
そのどちらか一方が割り当てられても納得すると宣言する。

これ小５の時に見た、誰もが得するカステラの切り方ってのと同じだ

両者の中間にナイフを入れるのも再起処理で中間を決めて残りが
１mmくらい（ナイフの刃先の幅)まで小さくなるまで実行するとかにすればいいのに
ケーキは細切れになると思うが

まずケーキを
相方の合意する部分でわける。
Ａ｜中間｜Ｂ
の３つに切る。
中間のケーキは相手に食われないよう
厳重に監視する。
　
もし少しでも中間を食ベるそぶりを見せたら
ＡはＢのケーキを
ＢはＡのケーキを
完全にたたきつぶす。
　
これが現実的な正解。

>一つのクリスマスケーキを２人で公平に分けるには、どこにナイフを入れたらいいか？。

半分こにすればいいじゃん。何言ってるんだよ？としか思えなかった俺は
あまり頭が良くないようだ。

ケーキきらいだから少しでいいって申請したら、大量のケーキ食わされるアルゴリズムに思えるんだが。

Aが切ったケーキをBが喰い、
Bが切ったケーキをAが喰う。

これで万事終了。

よっぽどニュースナカッたんか?

>>140
＞Ａ，Ｂともイチゴが好きなので、両者ともイチゴ面と非イチゴ面の境界線で円筒を切断することを主張する。
＞ついでＡ，Ｂにどちらが欲しいかを聞くと、両者ともイチゴが乗った方を選択する。

この前提がおかしい。
>>1は
「自分にとって等価値になるように二等分するためのラインを決めろ」と言っている。
自分にとって等価値、つまりどちらを選んでも損は無いという事。

「イチゴ面と非イチゴ面の境界線で円筒を切断」ってのはまったくつりあわない2つに分けることだろう。

>>141
えっ
これってゲーム理論の話じゃないの？

>>107
Aはイチゴありの4とイチゴなしの6が等価だと思って4：6の申告を最初にしたのだろう。

事後にAがイチゴなしの7よりイチゴありの3が価値があると考え交換に応じるのは全く理屈に合わない。
だったら最初にそう申告すべき。

ミキサーにぶち込んでペースト状にすればOk

>>160
バカだな、それだと、
・ミキサーを誰が買うのか
・ミキサーを誰が買ってくるのか（運ぶ）
・ミキサーを誰が選ぶのか
・ミキサーを使う場所は誰が確保するのか
・ミキサーはその後誰が洗うのか
・ミキサーを買ってきた後箱は誰が開けるのか
・ミキサーはその後誰のものになるのか
・ミキサーの開始ボタンを誰が押すのか
・ミキサーの終了ボタンを誰が押すのか
・ミキサーを動かす電気代は誰が払うのか

など新たな問題が山済みなんよ、ばかっ

>>151
カステラってのは基本的にどこ食っても一緒だろ?
関係ないよ
等価値になるのは真ん中で切るって決まってるんだから

>>161
それ言っちゃうとナイフは何で最初からあるんだよって話になっちまう

>>163

＞それ言っちゃうとナイフは何で最初からあるんだよって話になっちまう

なんだ？俺意外のヤツはバカばっかりなのか？
ナイフは問題に組み込まれてるから前提として存在してることになってんだろ、ばかっ

ケーキ食べたいな

俺わかった
お前らみんな馬鹿だ

中国式アルゴリズムは、中国がほとんどを取る。さらに残った部分も
難癖をつけて自分のものにしようとする。

客観的公平とか、みんなが満足とかまったく関係ない
他の奴より俺は損してないってそれぞれが思う解を求めろって
いう無羨望分割のアルゴリズムだって言うのに

>>162
カステラは端っこがうまいんだぞ！羊羹も。
関係ないのは最近の耳を落とした軟弱金太郎飴タイプだけだ。

ウンコをケーキに投げつけて、みんなが放棄した後にウリもらうニダ

日本史上最大の難問、管仙谷問題

>>157
＞>>1は「自分にとって等価値になるように二等分するためのラインを決めろ」と言っている。

具体的に>>1のどの部分が「自分にとって等価値になるように二等分するためのラインを決めろ」
と言う部分なの？

明確には書かれていないが、>>1の問題において相手の選好が不明な状態で
自分の最小期待利益を最大化しようとする場合、「自分にとっての等価値」線での
分割を申請することになるのはゲーム理論からの当然の帰結だな。

一方、禿はそれでも不公平だと言った。

>>169
端っこは2箇所あるから二分割に関しては問題ないだろ

>>109,159
これが論理パズルならAは「これぐらいが等価」と思う位置をちゃんと申請するのかもしれないけど
現実の分割では「イチゴが絶対取れて、ケーキもなるべく多く取りたい」と思って4：6を申請する場合もあるだろう。
要するに「イチゴのような要素が絡む現実の分割ではこの方法は使えませんよ」ということが言いたかったわけだ。

矢とかいう変なコテといい>>173といい、「これはゲーム理論じゃない」何度言ったらwww

>>176
Aが等価ではない4:6を選択したら損をすることもあるというだけの話。
Aが3:7で等価と考えているなら最初からそう指定していれば、
それより大きい7.5を得ることができた。

>>177
いや、誰も「このアルゴリズムが」ゲーム理論だとか言ってないから。

>>178
>>176の前提は、イチゴの取得が絶対条件だから、
必ず切り分けた片側は無価値になる。
だからA的価値観に照らして価値が二等分になる境界は存在しない。
必ず0 or それ以外となる。
>>1のやり方は、側を選べないので、Aは0になるリスクをとらないという前提に立つなら
この方式は採用しないということが言いたいんだろう。

Aの条件を満たして、切り分ける方法があるとするなら
Bが切って、Aが選ぶ方式だが、
Bとの不公平感がある。そもそもBが切る方式をBが飲む前提は
Bはイチゴが必須でないという前提条件付きだけど。
Bもイチゴが欲しいと言い出したら、成り立たないな。

だから、Aみなたいイチゴがなきゃ絶対ヤダみたいな我侭言う子には
ケーキはあげませんが結論になる。

>>180
イチゴが厚みのまったくない0だとしても、Aは単に0に限りなく近い極限を選べばよい。
これが成立しないのは、AとBが共にイチゴ以外無価値と考えている場合のみ。
それがAにとって等価でないと言うなら確かにそうだが。

端にイチゴの乗ったロールケーキを分ける場合
△
□□□□□□□□□□

（１）ＡとＢがそれぞれ、切りたいケーキの場所を（第三者などを通じて）同時に申告する
Ａ「イチゴこそ至上、イチゴ１：その他９で切り分けろ」
Ｂ「イチゴなぞ完全に無価値、５：５で切り分けろ」

（２）切りたい場所が両者で異なっていた場合、そのちょうど中間にナイフを入れる
→イチゴ含む３：その他７

（３）「申告した場所を含む側」のケーキを両者が得る
Ａの取り分
△
□□□
Ｂの取り分
□□□□□□□

Ａ「イチゴ部分にオマケがついてきたぞ、やったー！」
Ｂ「５割より多くもらえたぞ、やったー！」

>>182
申告した場所が中央で一致した場合、どちらがイチゴが乗ったほうを取るの？

>>183
お互いに「完全に無価値」と考えていれば、どちらを選んでもお互い納得できる
（お互いがイチゴ嫌いとかのケースがこれにあたる）

ただ、たいていの人はイチゴに価値を見出すだろうから
Ｃ「ちょっとは価値があるだろう・・・イチゴ４：その他６で」
Ｄ「そこそこは価値があるだろう・・・イチゴ３：その他７で」みたいになると

Ｃがイチゴ含まない６，５
Ｄがイチゴ含む３，５
で分けることになる
イチゴに「より多くの価値を見出したほう」がイチゴをゲットできる
もちろんイチゴ側は、ロールケーキ部分は少なくなる

>>182
手計算なんで間違ってるかもしれないが、
Aはイチゴ1点、土台全体を9点と考えるなら
A切断位置を1/9指定、B切断位置を1/2に指定
>>1のルールに従い中間点が境界になるから、左から11/36の位置で切り分けられる。
すると、
Aの点数は、取得したイチゴ1点と土台の9*(11/36)= 11/4点、合計15/4= 3.75点
Bの点数は、10*(25/36)= 6.94点
よってAが損してる。

>>185
えと、Ａは

↓イチゴ（△の部分）
△
□　｜　□□□□□□□□□
↑
ロールケーキ（□の部分）

こんなかんじに分けたいんです
Ａにとってイチゴはそれぐらい価値のあるものなのです
　

イチゴのみに価値があり、他の価値はゼロ（または限りなくゼロに近い）の場合は
ナイフが入る位置がイチゴの中央辺りになる（イチゴの位置がどこであれ）というだけの話だろう。

イチゴを切ってはいけない（全体の大半の価値を占める部分が不可分である）という条件であれば
それは最初から（この方式以外でも）等分しようがない。


>Aはイチゴ1点、土台全体を9点と考えるなら
であれば、Aにとって全体の価値は10、Aが申告する切断位置は左から5/9（ほぼ真ん中）だね

スマン失敗

>>187の前半は>>180へのレス、
最後2行は>>185へのレス

中間って、２箇所ないか？

ああスマン、左にイチゴがのってるのか。
なら4/9だ

（１）ＡとＢがそれぞれ、切りたいケーキの場所を（第三者などを通じて）同時に申告する 
（２）切りたい場所が両者で異なっていた場合、そのちょうど中間にナイフを入れる 
（３）申告した場所を含む側のケーキを両者が得ようとしたときに

（４）中国が勝手に全部無理やり持っていく

大事なことが抜けている
１の前に「結果について両者とも異議を唱えないことを確認する」

（２）切りたい場所が両者で異なっていた場合、
そのちょうど中間にナイフを入れる

そのちょうど中間が難しいんじゃ

たしかにw
もともとの問題は、半分に切るはずが必ずしも正確に二等分できないから
一歩が切ってもう一方が選ぶんだったよな。

>>187
最初の2行はその通り。

中段で言われている、イチゴを切れない条件のときは、Bが切ってAが選ぶ式がよりマシなやり方かな。
Bが受ける前提だけど。

最後のAが4/9で切るは普通はその通りなんだけど、
Aの価値判断に特別な条件が付いていて、イチゴがなかったらケーキとして価値がないから0点だよ
っていうのが厄介だ(イチゴがあるときだけ価値判断をする)。
だから4/9を指定してAが結果的にイチゴが取れればいいけど、
Bが指定する位置しだいで取れない場合がある(今回の例はたまたま端に乗ってるから取れるけど)。
そういう状況ではこの方法はAにとってリスクが高すぎるから、>>1方式はヤダよと言われてしまう
と言うのが>>176の主張だと思うんだが。

>>1のやり方を採用できる場合は、
切り分けるものは一様に価値があるという前提が付くかな。

>>194
切り分ける物が、AさんとBさんで価値が違う場合
仮にA的価値観で50:50で切った結果でも
B視点でみれば60:40の場合もあり、そうしたときBは60(好物が乗っている方とか)を選択するから
Bが少しお得だね。

Cが相手の弱みを持ち出して全部取る。
その様子を見ていたＲが以前借りパクしていたＣＤを俺のもんだと言い出す。

>>195
＞最後のAが4/9で切るは普通はその通りなんだけど、
＞Aの価値判断に特別な条件が付いていて、イチゴがなかったらケーキとして価値がないから0点だよ
普通はも何も>>185自身が「イチゴの9倍の価値がケーキの土台にあるとした場合」として条件を提示している。
「イチゴ10点、ケーキの土台0点」のケースと混同してるようだけど。

>>188で補足したとおり、>>187は>>185へのレスね。
>>187だけ読んでレスしたのならスマン。

>>198
イチゴが端に乗ってるからその戦略が取れるけど
仮に、真ん中付近に乗ってたらどうする？イチゴをきるって選択肢がない状況で。
イチゴは絶対欲しいといってる奴が。このやり方を採用するだろうか。

Bがどこ切ってるか判らないんだぜ。

Aの評価式は例えば
点数 = F * (土台 +イチゴ)
こんな風になってて土台が最高9点、イチゴが1点、Fはイチゴが取れたら1、とれなかったら0

>>199
それは>>187に書いたとおり。

イチゴのみに価値があり、他の価値はゼロ（または限りなくゼロに近い）の場合は
ナイフが入る位置がイチゴの中央辺りになる（イチゴの位置がどこであれ）というだけの話だろう。

イチゴを切ってはいけない（全体の大半の価値を占める部分が不可分である）という条件であれば
それは最初から（この方式以外でも）等分しようがない。

>>200
イチゴの価値は点数では1なんだって、土台も最高9
イチゴの有無が全体の評価を変えるだけ。イチゴの価値が無限大じゃない。
イチゴが乗ってれば100円の価値があるけど、乗ってなかったら買わない。

>>200
すまん、もう寝るのでこれで失礼。

>>201
言い方を変えただけで、結局「イチゴが含まれてない側であればケーキをどれだけとろうと0点」なんだから
>>187がそのまま当てはまる

>>201
1点=100円じゃないのか？土台の価値は0円なのか900円なのか？
それとも、ボードウォークとパークプレースの両方を集めると価値が
上がるとか、そういうことを言っているのか？

ところがこの理論は第三者がどちらかに買収されていると成立しない。
今の時代、こういう要素も組み込んで答えを出すべき。
たとえば、この三人の中に中国が入っていたらどうなるか

イスラムにはこの問題の解決先が昔からある。

負の平等といって、ケーキにションベンを掛けるっていう手だ。

ソフトバンクにＮＴＴの施設タダで使わせるのは国有財産の侵害だろ。
絶対許すな、国民はまだ間接的な株主なんだから。

絶望先生を連想した人↓

↑
おまえだけだ。このチンカスがっ

お互いの希望の中間って常識じゃないか
その「中間」とやらが双方によって違う位置に見えるから難しいんだって
いろんなバイアスがかかったり、そもそもそのケーキはみたいなことがあったり
正に机上の空論。文字通りケーキの分割くらいにしかつかえない

>>115
0〜1はどうなったんだよ

こういうスレは下手に知ったかぶりで書かない方がいい。
でないとν速のユニバーサルメルカトルと同じような恥をさらすだけ。
>>35の論文を理解した奴だけがマジでレスしてくれ。

切る方よりも、(切ったあとで大きいのを)選ぶほうが有利だ、
という論文の1ページ目までは理解した

利害が大きくなればなるほど
中間点がどこかでひたらすらもめた後
一からやり直しとちゃぶ台返しで
相手が折れるまでｇｄｇｄやり続けるだろなｗ

>>212
ＮＴＴとソフトバンクの光回線にこのアルゴリズムを当てはめてみる

ＮＴＴの主張：光回線は開放しない
ソフトバンクの主張：光回線は開放するべきだ

アルゴリズムの結果：光回線は部分開放する

ＮＴＴはこの答えでいいのか？

んな認識だとひでぇ目に合うと思うよ、多分ね

それにしてもこの問題は３者になると途端に難しさの次元が跳ね上がるな……

>公平
こっから定義しなかy話にならない
ケーキ嫌いが分量的に半分もらっても殺意覚えるだけ

全ての外交トラブルはこの方法じゃ解決しないな。
でもこれコンピューターのプログラムの問題なんじゃないの。
競合するプログラム同士のリソースの使い分けとかの話なのかも。
あまりにもわかりやすく噛み砕いて報道してるから、
本当の意味が伝わってなかったりするのかも。

欲を出した方が勝ちじゃね

ゲーム理論の一種なんだろうけど
AとBが同じ場所を要求した場合どうするの？コレ

特定の領域だけ異常に価値が高くて双方が欲しがっているという話なら、
上で議論されている通り。同じ切断ポイントを指定した場合という話なら、
それはどっちを取っても文句なしということなのでジャンケンででも
決めればよい。

こういうこと？

日本：北方４島一括返還しろ！
ロシア：領土問題はない。

新アルゴリズム：２島返還でOK

日本：？？？？
ロシア：？？？？

日本：北方４島一括変換しろ！
ロシア：領土問題はない。



国民：約束した７万返せ。
ＮＴＴ：７万返すと言った覚えない。

新アルゴリズム：３万５千円でいいんじゃない？

NTT：返さなくいいと、国のお墨付きが出たぞ。
国民：・・・・・


全然解決にならんやん。
NTTもしょうもないことする余裕あったら７万返せよｗ

>>217
お互いの思う「公平」の基準が違っても、双方が「自分が思う公平以上のものを得られる」って話で
公平の基準を問題とする必要が無い。

分量的半分なんて話はどこにも出てないし
一方がケーキ嫌いなら最初から「どういう分け方をするか」なんて話にならない。

>>219
>>222
「分けたいラインを決めなさい、ただし自分がどちらをとるかはわかりません」だよ。
つまり２つのうちどちらを得ることになっても自分にとって差が無いラインを申告しろ、ってこと。

一つ疑問。下の様な長さ４のロールケーキがあったとする。

１２３４
□□■■

Aにとっての価値は
□：１　■：０

Bにとっての価値は
□：０　■：-１
とする

この場合、Aは1と2の間、Bは3と4の間に線を引くので、2と3の間が分割線になると思うが、指定分割線に比べて、Aの利益は増えるがBの利益が減るので不公平だと思うのだがどうだろう。

>>224
このアルゴリズムではマイナスには対応できないね。

ただその例だと「Bはそもそもケーキに価値を認めてないのになぜ分け方が問題となるのか」って話だけど。

>>225
マイナスに対応出来ないというので納得。ただ、
>「Bはそもそもケーキに価値を認めてないのになぜ分け方が問題となるのか」
って話に関しては以下の様に問題を作り変えると回避できそう

長さ６のロールケーキ
○○■■□□

Aの価値
○：+1　■：０　□：０

Bの価値
○：+２　■：-３　□：+２

Aの分割線は1と2の間、Bの分割線は3と4の間。実際は2と3の間。
Aの利益 希望：+1　実際：+2
Bの利益 希望：+1　実際：-2

つまり、ちょうど半分のところを両者が切ろうとすると
ふたりともケ〜キを食べられなくなるってことか・・・

ちがった
1: begin
2: Pi(i = 1; 2) simultaneously declare ci that satisfies i([0; ci]) = 1=2.
3: if c1 = c2 then
4: Cut at c1, coin-flip and decide which party obtains [0; c1] or [c1; 1].
5: else
6: Cut as [0; (c1 + c2)=2], [(c1 + c2)=2; 1]. Pi obtains the piece which contains ci.
7: end.

>>226
Aがどこを切ってくるかは、B視点で同様の確率に写るなら
自分ならBが3|4を指定するのは分が悪いと考える。

この例の場合だと、Bは1|2(あるいは5|6)で切り口を指定すべきではないかな。
Bの価値では、左側が2、右側が0とアンバランスな切り方だけど。
Aがどこ切ってきてもマイナスにならない。
仮にAが同じ場所1|2を切ってくると、Bが2と取れるのか0を取れるのか決まりがないので不定だけど
1/2の確率と考えるなら平均リターンは1だ。
そうするとBが1|2を切ったとき、Aが切る場所(左辺)に対する、Bの得られる結果(右辺)は
1|2 → 1
2|3 → 3
3|4 → 1
4|5 → 2.5
5|6 → 1

>>1のルールは切りたい場所を申告すると書いてあるが
本人にとって、切り口の左右が同等になるように切れとは言ってない。
本人がもっとも得だと思う場所を切ればいい。
どういう式に則って決定すればいいのか、俺にわからんが。

>>226
>>229
いや待て待て、Bの解は三ヶ所あるぞ？
1の半分と、6の半分と、3|4の間だ。

単純な人間が相手なら、このアルゴリズムが有効に機能するだろうけど、人間は複雑だからね。
あっちを立てれば、こっちが立たないなんてことは多々ござんす。

>>229
間違えた以下訂正
> 3|4 → 1
3|4 → 4

>>230
Bの解といってるのは、Bが指定すべき切り口のことを言ってるの?
AB意見が出揃って、最終的に切られる位置のこと？
切り口の指定について、
ケーキの外や、ブロックの真ん中とかは、組み合わせが多くなるから考えたくないな。

仮にBが3|4の位置を指定してきた場合、
Aが切る場所(左辺)に対する、Bの得られる結果(右辺)は
1|2 → -2
2|3 → -0.5
3|4 → 1
4|5 → -0.5
5|6 → -2
俺ならここを選ばないな〜

3次元ロールケーキなら
Bの切り方はこうだろ
--○-○-■-■-□-□--

1次元の紐の話なら知らんｗｗ

東シナ海では使えないことを知らないの？本当に暇な会社だな。

このアルゴリズムって、いかに自分の利益を多くするかではなくて、
「それぞれの価値観での平等」をえるものでしょ。

互いに自分の考える平等を主張すれば
それぞれがそれ以上を得られるが、
総取りを主張するなど利益を多くしようとすると損をする。

>>1
意味がわからない。
Aが縦1/2、Bが横1/2を希望したらどうするんだよ。

斜め1/2でカットするのか？

二人ともイチゴが凄く欲しいって場合はただのチキンレースになるよな。
あと、イチゴを取り合ってるときに二人とも同じ位置の申告をしたら決着がつかないよな。

そのときはくじか競売で決めそうだけど、だったら始めからそれで決めろよって話だし。

>>237
> 二人ともイチゴが凄く欲しいって場合

イチゴの分割にこのアルゴリズムを適用するのだ！

マイナスの場合の>>226が面白い。
要は■がうんこだったらってことだよな。
Aにとってはうんこは気にならないけど、Bは絶対いやって場合ｗｗｗ

この場合、Bは中間線によっては最大-2ってのがあるから、
この分割問題に参加しないのが正解だなｗｗｗ

このアルゴリズム、性善説だよな。

もし中韓みたいな極悪な相手なら、相手は目一杯要求してくるぞ。
こちらが常識的な要求したら、中間線取っても公平にならない。

>>240
ちがうよ
> （３）申告した場所を含む側のケーキを両者が得る

んだから、全取りしようとしたらものすごく小さいほうが得られる

そこでNTTと古典の折衷案

1)Aが切る
2)Bが選ぶ
3)Bが切る
4)Aが選ぶ
5)2と4の中間線で分割する

｜□□□□□｜□□｜□□｜□｜
　　　　　　　　 ↑　　　↑　　　↑
　　　　　　　　日本　　中間　　中国

５つを主張した日本が、中間線左側７つの領土
９つを主張した中国が、中間線右側３つの領土

>>240
その場合、目一杯要求したほうが損をする。
なぜなら「それぞれの価値観で平等」に分けたということは
「目一杯要求した分」と「残りの分」は同じ価値と主張している
ことだから、もう片方が中間線を要求すれば
目一杯要求した分の取り分が
「残りの分」＋「目一杯要求した分と中間線との中間の分」
になり、中間線を要求した方の取り分は
「中間線までの分」+「目一杯要求した分と中間線との中間の分」
になるから。

>>243-244
ありがとう。納得しました。

>>232
分けた線の、どちら側を取っても等価となる線が、通常は一ヶ所。

Bにとってケーキ全体は価値1なので、0.5の価値で切り分けることになる。
マイナス要素が入ることによって、そのラインが三ヶ所になる。

確認だけど、
最終的に自分が要求した部分とは逆側を得ることになるの？
もしそうなら領土分割には使えないね。

Aがケーキを独り占め。

ケーキは余ること無くパレート最適となり、最も経済効率が良い解の一つ。　公平性はともかくとしてな。
公平性を口にするとやれ共産主義だ、社会主義だと言われるご時世だ。
田中角栄がようかんを切って一番弱い奴に一番大きいのをやるなんて言ってたものだが、
今は一番強い奴が一番大きいのをかっさらっていく。　　場合によっては羊羹まるごと。

それを是としてきたのがここ数年の日本。

ケーキ分割問題の新解法が出来たのだから、公平性を維持したままパレート最適を達成できる可能性が生まれたってことだよな。

>>247
どちらかは要求出来ない事になってる。選べないけどどちらも
「半分と見なした以上貰えるんだから文句は無いはず」って理屈。

>>246
理解した。
確かに価値を等分する位置は3つある。

この際、切り分け位置をブロック単位にかかわらず、任意の位置に取れるとして
Bが左端のブロックの+2の半分位置を指定した場合、
当初の意図の通り、Aの出方にかかわらず、Bは少なくとも+1以上を得られるだろうか。
>>226の例の範囲では大丈夫そうだけど、
一般的に価値を2等分する位置が複数ある場合、
そのどれかに正しい解があると言えるのだろうか。
正しいと言ってるのは、全体の半分以上の価値が得られる場所ね。

中国が尖閣とるときは
沖縄本島や九州までが領土だと主張し
分けるケーキ自体を大きくして交渉に入り
その上で半分を主張し尖閣を手に入れる

>>248
これはお前の様に恣意的な平等を主張して揉めない様にする為のもの。
論文の題名が「Meta-Envy-Free Cake-Cutting Protocols」なんで
平等や公平ではなく実際は「妬みのないケーキ切り分け手順」について。
弱者がお涙頂戴でより多く貰えるとか逆に強者が独り占めするとかしない為のもの。

ミキサーにかけたケーキなんかまずくてくえないだけだろ。

まあマイナスの部分は、配分されても
捨てればいいんじゃね？

それも見越して自分の線を設定すると
もっと複雑になるかな？

>>254
現実の問題に当てはめてみると
ここで言ってるマイナスって
土地分割のときのに土壌汚染や爆弾埋まってて処理に金がかかるとか、
遺産相続の負債分だったり、
絶対残したらいけない料理のまずい部分だったり、
まあなんにせよ、コストなしに捨てられない状況ってあるわけで、
そういったケースではこのやり方だとうまくいくのかなってのが
興味があるところ。

>>250
適当に数字入れてグラフ眺めて考えてみたが
以下ケースは、トータル+8で左右4になるように価値二分するラインは二箇所あるんだけど
そのどちらできっても、相手の出方しだいでうまくいかないかもなー。
[+5] [+1] [+1] [+1] [-5] [+5]
なんでマイナス入ると複雑になるんだろう。

マイナスが入ってきたらこの考えじゃ無理だろ
仮に全部マイナスの物だったら中間に近い点選ぶほど損になるし

>>257
AとBお互いの評価関数が全域でマイナスのとき、
つまり嫌なことを押し付けあう状況みたないなとき、
この考えたかで境界を決めてあげて
取得する領域を自分が選んだ切り口と逆にしてやれば上手く行くはず。

>>258
それをやるとどちらも半分以上に嫌なものをもらうことになる
だったら、AがBが得するように半分のうち片方をもらったほうが
いいと思うんだがどうだろう

>>259
ん？半分以下になるよ。
>>1の逆バージョンなんだけど。
＞（３）申告した場所を含む側のケーキを両者が得る
これのやり方をひっくり返すんだ。
申告した場所を含まない領域を得る。

>>260
そうかよく考えてみたらそうだった

あーこれ長方形型ケーキか
ホール型ケーキでイメージしてたからわけわからんことになってたんだ

このアルゴリズムそのものが全員に承認される為には絶対的軍事力が必要。

なんか戦略はゲーム理論っぽいね。ライヤーゲームで採用してくれ

Aが切ってBが好きなほう選んだらいいんじゃね

「矢 ◆gavOvXSRUQ」で愚愚ってみ。痛いレスが続々と現れるぞｗｗｗ

いちごが端っこに置いてあれば、そのいちごの価値とケーキの価値とを
換算して、よりいちごの価値を認めた方のものになると思うけど、
いちごが真ん中近くに置いてあれば、意味が無いよな。

古典的な方が、腑に落ちる。
もっと深いアプローチができなかったか。

>>267
別にイチゴを真っ二つに切っても構わないんじゃない?

>>268
お前が浅過ぎるんだろうな
「古典的な方」だと切るの担当する人は得するということがない
一方で選ぶの担当する人はそうではない

得することがないから
慎重に配分するのでは

中心点を境に、上半分と下半分を双方好きに切れば問題解決
　
お前は上半分を好きに切り分けていいから
俺は下半分を切らせろ
　
これで問題解決不公平なし

来年のイグノーベル賞は確実ですね

>>271
一方が平等でもう一方が得したと思うなら平等じゃないでしょ

実際は二人で「チョコの家だけは譲れない」となって割り切れなくなる事が多いんだよな。

ケーキの分割で争ったらケーキを全部第三者にあげてしまうことにすればいい
これで平等になる

>>275
家を二分割

一応言っておくけど、モデルとしてケーキを使っているだけで、
ほんとにケーキ切るために使うプロトコルじゃないからな。

手っ取り早くWikipediaから「ゲーム理論」を引用するけど、
「ゲーム理論とは、あるルールのもとで各プレイヤーがとると
　考えられる最適な行動の組合せの解を求めることである。」
「ゲーム理論は純粋数学としての解析的研究のみに留まらず、
　工学の各種分野で幅広く応用されている。 とりわけ情報工学
　での応用が盛んであり、次世代通信ネットワークトポロジー構築
　アルゴリズムへの貢献が期待されている。」

NTTがやっているのは上の意味合いが強いんだと思うよ。
・ケーキが欲しい人→ルータ
・ケーキ→ネットワークの帯域
とかに置き換えられるんじゃね？

イグノーベル賞とかいってる奴が、本気で言ってるのか心配に
なったのでマジレスしとく。

だれか北方領土にたとえて説明頼む

>>279
プーチンが全取り

「北方領土は、おいしいケーキじゃない」
　
利尻や礼文島など、既存の北海道の離島すらいろいろ困っているのに
北の最果ての離島(貧乏地域)を抱えて、赤字垂れ流しでインフラ整備するのかな。
そして儲かるのは「国」じゃなくて昆布とかカニを獲る漁師さんだけ。
それも今ではベーリング海のほうまで取りに行くぐらいだから
北方領土周囲だけでは、とても間に合わない。
しかも乱獲で資源消滅は目に見えている。
そもそも昆布嫌い。

>>70さんのおかげでようやく理解できた。
上手く出来てるなぁ。

>>278
空気の読めない人だなあ

>>283
みんなちゃんと理解してるけど空気を楽しんでるんだよと言いたいわけ？
そうは見えないけどw

>>284
君はこのスレに向いて無いね

>>285
俺の質問に答えてよw

＞NTTがやっているのは上の意味合いが強いんだと思うよ。
＞・ケーキが欲しい人→ルータ
＞・ケーキ→ネットワークの帯域
＞とかに置き換えられるんじゃね？

みたいな、>>1を理解できなかった事バレバレな例えを出しちゃうよりは
ケーキの例えのまま話したほうがずっとマシだな

>>286
そんな義務は無いし
消えてくれる?

これって丸いケーキの話だよね？

人のこと空気読めない扱いしておいて、
しっかりした反論もできずに逃げるとか、
>>288はどこまで惨めな人間なのだろうか？

日中が油田の採掘したい場所を申告する
それは後回しとして共同採掘を始める
中国が全ての採掘権を得る

>>291
こんなスレまでそんな話を持ってくるな。
あくまでお互いがそれぞれ別の価値に基づいている時に、
双方が相手より不満が絶対に大きくならないように分けるというだけ。

これ、実体の分割方法じゃなくて「開始時間」とかの時間設定にも
使えるな。ただ、「中間を取る」というのは増減に対する満足度の変動が
単純比例する場合にしか適用できないけど。

（１）ＡとＢがそれぞれｒｙ
（２）切りたい場所がｒｙ
（３）おまえらケーキはもう俺が食べたから

>>289
おいおい>>1くらい最後まで読んでおくれ

AさんとBさんがまともな人前提でしょう
実社会だとこれではすまん

暴力装置が必要