組合せ数学特論 ケーキ分割問題 伊藤大雄 京都大学大学院情報学研究科 2008.05.13版 はじめに 古典的な... 組合せ数学特論 ケーキ分割問題 伊藤大雄 京都大学大学院情報学研究科 2008.05.13版 はじめに 古典的なクイズ 太郎と次郎の二人で１つのケーキを切って分け たい。どちらからも文句のでないように切るには どうしたら良いか。ただし、両者の価値観は異な るかもしれない。 回答[切断選択法(cut and choose algorithm)] まず太郎に、自分の価値観から見て公平であるよ うに２つに分けさせる。その後、次郎に好きな方を とらせる。 ケーキ分割問題とは、このクイズを一般化したもの である。 ケーキ分割問題 • １つのケーキをn人で切り分ける。 • 各人が全体の価値の1/n以上の価値をもつピースを得れば 満足する（単純公平分割(simple fair division) ）。 • 各人の価値観は異なるかもしれない。（⇒同じ一切れでも人 によっては1/n以上と考えたり1/n
記事へのコメント0件
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています