ケーキ分割問題

今日の特別講義の内容。

  • 同じ大きさのケーキでも個々人が感じる価値は異なる
  • ケーキを分割したとき、元のケーキの価値と分割されたケーキ片の価値の総和は等しい
  • どのような大きさのケーキ片も非負の価値を持つ
  • どのような大きさのケーキも分割することができる

という条件でルールを守った人全員が満足するようにケーキを分割するという問題。
二人なら単純で、一人が自分がちょうど半分だと思うように分割してもう一方が好きなほうを選択すればよい。
で、条件を複雑にすればするほどどんどん難しくなる。無羨望分割(全員が自分が一番大きく取っていると感じる分割)で4人以上になると本当にすごいことになる。途中のステップで n 人に対して pow(2, 2 * n - 6) 以上のピースに分割することに。
アルゴリズム/ゲーム理論の分野では有名な問題らしいのだが、あまり応用はないらしい。まぁ、面白かったけど。