パスワードを忘れた? アカウント作成
285132 story

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

ストーリー by hylom
分割する相手を見つけるアルゴリズムをお願いします 部門より

あるAnonymous Coward 曰く、

NTTが「一つのクリスマスケーキを2人で公平に分けるには、どこにナイフを入れたらいいか」という「ケーキ分割問題」を正しく解くアルゴリズムを開発したそうだ(日刊工業新聞)。

「ケーキ分割問題」とは、2人で1つのケーキを分割する際に、両者が満足するように分割するにはどうすれば良いか、という問題。2人が異なる価値観を持っているというのがポイント。今回発表された新アルゴリズムは「両者が同時に切りたい場所を申告し、その中間でカット、申告した場所を含むケーキを分配する」というものだそうだ。

今日・明日とケーキを食べる機会は多いかと思うが、さっそく応用してみてはいかがだろうか。しかし、3人以上で分割する場合はどうすれば良いのだろうか?

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • by TarZ (28055) on 2010年12月24日 18時30分 (#1879227) 日記

    これっぽい。読み中…。

    Meta-Envy-Free Cake-Cutting Protocols [ntt.co.jp] (PDF)

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

    # 私なら、選ぶほうになりたいな。

  • by phason (22006) <mail@molecularscience.jp> on 2010年12月24日 18時42分 (#1879235) 日記

    ・わかりやすくケーキとして書いてありますが,(現在では)現実のケーキを直接対象とする研究ではありません.
    ・カットと書いてありますが,文字通り包丁で切り分けるとかそう言う話でもありません.
    ・そのため切る際の技術だ何だの問題は存在しません.

    京大の伊藤先生 [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]

  • by nekurai (6253) on 2010年12月24日 18時13分 (#1879209) 日記

    少なくとも 1 人が「全部くれ」と主張する場合、このアルゴリズムでは解決しません

  • by 0.1uF (3815) on 2010年12月24日 19時41分 (#1879287) 日記

    1.Aがどちらも平等(均等)になるように2つに分割します。
    2.Bが自分の好きなほうを選び、残った方をAが取ります。

    これでお互い文句なく2つの分割できます。子供が二人いる場合は特に有効。
    苺が載っている場合は苺が載っている側のケーキを大きくするか小さくするかはAの判断ですが、Aは自分のとりたい方を選べないので…

    • Re:二人の場合 (スコア:2, 参考になる)

      by greentea (17971) on 2010年12月24日 20時42分 (#1879321) 日記

      #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, すばらしい洞察)

        by Anonymous Coward on 2010年12月25日 0時58分 (#1879424)
        この分け方は「公平」ではなく、二人から不満が出ない切り方です。
        切り分けるほうは自分が公平になると思うところで切るため、どちらが残っても同じ。
        選ぶほうが自分が得だと思うほうを選ぶ。
        切り分けるほうにリスクがあるが、選ぶほうにはリスクがない。

        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が選べば、二人とも満足。
        できがいいアルゴリズムだと思うけど?
        親コメント
  • 飲み物とまとめてミキサーにぶっこんで、液体換算すると皆が見分けやすくなるんじゃない?
    所詮カロリーは変わんないんだし……とか考えた。
    --
    fj.jokes出身:
  • by digoh (17917) on 2010年12月24日 18時12分 (#1879208) 日記

    2人で分けるアルゴリズムの一つに「片方が分割線を引き、もう片方が選ぶ」というものがありますよね。
    (これは両者がほぼ同じ価値観を持つ前提ですが)

    これを3人に拡張すると
    ・一人目が分割し
    ・二人目が選び
    ・三人目が食べる
    これで万全!
    問題は、アツアツおでんに適用した場合、大体たまごやこんにゃくやモチきんちゃくが選択されるというところでしょうか。

  • by Anonymous Coward on 2010年12月24日 18時13分 (#1879210)
    両者が同じ切り口を申告しかつ同じ側を欲したらどうなるのでしょうね。
  • by bAwo 5UoMYoA (13278) on 2010年12月24日 18時15分 (#1879212)

    ふたりのうち、正直者は「だいたい真ん中だろう」というラインを指定。
    もうひとりは、「どうせ、ふたりの引いたラインの中間になるのだから」といって、
    自分:相手=99.9:0.1くらいになるようなラインを指定。
    結果、正直者は約25%、もうひとりは約75%のケーキをもらいましたとさ。

    • by SNT (23129) on 2010年12月24日 18時22分 (#1879218)
      逆、正直者が75%を得る。
      親コメント
  • by Cellea (37481) on 2010年12月24日 18時19分 (#1879216) 日記

    「切りたい場所」の申請の結果、その線が交わった時の処理が決まってないから仕様漏れだと思いまーす!

    #円形のケーキだと普通に起きそう

  • by Anonymous Coward on 2010年12月24日 18時38分 (#1879233)

    2つ買えばいいじゃない

  • 一方…… (スコア:1, おもしろおかしい)

    by Anonymous Coward on 2010年12月24日 19時06分 (#1879254)

    「ケーキを公平に切る」

    この命題の為にNTTは少なからぬ人材と時間を使い、不完全ながらも2人に対して公平に分割するアルゴリズムを作成した。
    これにより、条件さえ揃えばそれなりに公平にケーキが切れるようになった。

    一方、ソフトバンクはケーキを人数分買ってきた。

    • Re:一方…… (スコア:5, すばらしい洞察)

      by Anonymous Coward on 2010年12月24日 21時00分 (#1879332)
      > 一方、ソフトバンクはケーキを人数分買ってきた。
      「一方、ソフトバンクはケーキを人数分用意するのがNTTの役目だと主張した。」じゃない?
      親コメント
      • by wilodp (39794) on 2010年12月24日 21時41分 (#1879343)

        >> 一方、ソフトバンクはケーキを人数分買ってきた。
        >「一方、ソフトバンクはケーキを人数分用意するのがNTTの役目だと主張した。」じゃない?
        「一方、ソフトバンクはそのケーキが嫌いだったので、新作ケーキを人数分用意するのがNTTの役目だと主張した。」とか

        長すぎてゴロが悪いね

        親コメント
  • …フフ、こんなこともあろうかとずっと独り身でいたのさ!

  • これはNTT東日本と西日本の管轄が調整される前触れとみていいのだろうか
    • NTTご本尊が「俺は公平だからな」「俺がいないとお前ら、パイをちゃんと公平に分けられないだろ?」と主張している、ということではないでしょうか?

      で、それに対して東西が「いや、おれたちは cut and choose 戦略でいいよ」「俺ら、価値観一緒だし」「もう上納金はなしな」とか逆らい始めると面白いという…。

      --
      fjの教祖様
      親コメント
  • 「両者が同時に切りたい場所を申告し、その中間でカット、申告した場所を含むケーキを分配する」

    うん? それはつまり 両者が同時に切りたい場所を申告するための公平な環境が必要だよね。話を簡単にするために「中間でカット」することは実現できたと仮定するとしても。

    それを2者だけで実現可能なのか?

    ちなみに3者を導入すると「裏で取引」が発生する余地が出るので、「公平な第3者」前提は一般には使えないはずなのだが…。

    一方で、「同時」とかの条件って、順序性を保証する場合と違って確認が難しかったはずだが…。
    # 難しいからこそ手品ができる。

    なんか一番大事な部分が説明されていない気がする。

    --
    fjの教祖様
typodupeerror

私は悩みをリストアップし始めたが、そのあまりの長さにいやけがさし、何も考えないことにした。-- Robert C. Pike

読み込み中...