公平分割問題
公平分割問題(こうへいぶんかつもんだい、英: fair division problem)とは、ものを公平に分割する数学の問題のこと。特定タイプの問題はケーキ切り問題(英: cake-cutting problem)と呼ぶ。第二次世界大戦下に数学者シュタインハウスによって提唱され、戦後1947年ワシントンD.C.の計量経済学の国際会議を契機に数学、経済学、情報科学の研究者に広まった。分割に参加する人の価値基準がいろいろな状況で、対象物をどのような方法で分割すれば、参加者全員が公平と感じることができるのか、あるいはそのような分割方法が存在するのかを扱う 。
2人用 分割と選択法
2人用 ブラムズ-テイラーの勝者調整法(英語版)
3人用 セルフリッジ-コンウェイ法(英語版)
3人用 ストロンキストの4本ナイフ移動法(英語版)
n人用 ブラムズ-テイラーの絶対的優位法(英語版)
n人用 シモンズ-スーのスペルナー彩色近似法(英語版)
参加者2人が好きな対象物を自由に分割可能な場合の方法として、紀元前から知られる方法に分割と選択法(divide and choose)がある。切る人・選ぶ人法とも呼ばれる。まず一方の切る人が自分の価値基準で対象物を価値の等しい2つの部分に分割し、次に選ぶ人が自分の価値基準で大きい価値の方を選び、最後に残りを切った人が受け取る方法である。この方法はどちらも自分の分の価値が他の人の分の価値以上と感じることができる優れた方法である。分割と選択法は嫌いなものを参加者2人が分割する場合にも利用できる。
日常生活で行われるもう1つの方法に、成分分割体積等分法がある。これは対象物を異なる成分に分割できる場合、成分ごとに分割し、それぞれを人数分の1の等しい体積に分割する。どの参加者も全体価値の人数分の1の価値を得たと感じることができる。ただし、この方法では各自の感じる獲得価値の合計は全体価値の1倍にとどまる。