公平分割問題
公平分割問題（こうへいぶんかつもんだい、英: fair division problem）とは、ものを公平に分割する数学の問題のこと。特定タイプの問題はケーキ切り問題（英: cake-cutting problem）と呼ぶ。第二次世界大戦下に数学者シュタインハウスによって提唱され、戦後1947年ワシントンD.C.の計量経済学の国際会議を契機に数学、経済学、情報科学の研究者に広まった。分割に参加する人の価値基準がいろいろな状況で、対象物をどのような方法で分割すれば、参加者全員が公平と感じることができるのか、あるいはそのような分割方法が存在するのかを扱う[1] [2]。
公平分割問題の種類
[編集]分割の対象物には、参加者全員が好きなもの、全員が嫌いなもの、 全体が均質なもの、部分が異質なもの、１個の分割が自由にできるもの、１個の分割が許されないものなど、さまざまな設定がある。
参加者の感じる公平の基準には、各自の価値基準で、自分の分が全体価値の人数分の１以上に思える、どの人も自分の分の価値が他の人の分の価値以上に思える、どの人も自分の分も他の人の分もちょうど全体価値の人数分の１に思えるなどがある。 参加者人数は２人、３人、一般人数の場合がある。意思決定は参加者一人一人が順番に行う場合、全員が連続的に移動する分割案を見ながら同時に行う場合がある。
公平分割問題を解くアルゴリズムは、近似解法も含め、各種開発されているが、多くは公平分割法の存在を示す目的のものが多い。日常の問題を解くために有用な方法も一部開発されている。
公平分割理論以前の方法
[編集]参加者２人が好きな対象物を自由に分割可能な場合の方法として、紀元前から知られる方法に分割と選択法(divide and choose)がある。切る人・選ぶ人法とも呼ばれる。まず一方の切る人が自分の価値基準で対象物を価値の等しい２つの部分に分割し、次に選ぶ人が自分の価値基準で大きい価値の方を選び、最後に残りを切った人が受け取る方法である。この方法はどちらも自分の分の価値が他の人の分の価値以上と感じることができる優れた方法である。分割と選択法は嫌いなものを参加者２人が分割する場合にも利用できる。
日常生活で行われるもう１つの方法に、成分分割体積等分法がある。これは対象物を異なる成分に分割できる場合、成分ごとに分割し、それぞれを人数分の１の等しい体積に分割する。どの参加者も全体価値の人数分の１の価値を得たと感じることができる。ただし、この方法では各自の感じる獲得価値の合計は全体価値の１倍にとどまる。
公平の基準
[編集]対象物を参加者全員が好きな場合で公平の基準を示す。 各自の価値基準で見て自分の分が全体価値の人数分の１以上と感じる状態を割合の公平という。各自の価値基準で見て自分の分の価値が他の人の分の価値以上と感じる状態をうらやましさ無しの公平という。うらやましさ無しの公平の状態では、参加者がみな自分の分が（同点１位の場合も含め）１番よいと感じている。うらやましさ無しの公平が実現できれば、自動的に割合の公平も実現する。この逆は一般に成立しない。割合の公平が実現しても、うらやましさは発生する場合がある。例えば３人でようかんを分割して、自分の分が全体価値の1/3以上と納得できたとしても、誰か他の人の分の価値が自分の分の価値より大きいと感じることは起こるからである。 各自の価値基準で見て自分の分も他の人の分もちょうど全体価値の人数分の１に感じる状態を正確な公平という。正確な公平が実現できれば、うらやましさ無しの公平も割合の公平も自動的に実現する。（正確な公平を完全な公平と呼ぶ流儀がある。この流儀では、正確な公平という用語で、各参加者獲得分の全体価値割合について全員の認識が一致する状況を表す。）
対象物に対する各自の価値評価法はさまざまでよいが、全員好きな対象物の場合、獲得物が全くない場合の評価値は0、一人で全体を獲得した場合の評価値は1、既得分に新規獲得分が追加された場合の評価値は、既得分の評価値と新規獲得分の和となる。獲得する対象物を無い状態から全体の状態までだんだん追加していくと、どの参加者の場合も評価値が0から１に連続的に変化する。
公平分割法
[編集]著名な公平分割アルゴリズムのいくつかを以下に示す。２人以上の一般人数用の方法をn人用と表記する。
割合の公平な分割法
[編集]うらやましさ無しの公平な分割法
[編集]- 2人用 分割と選択法
- 2人用 ブラムズ-テイラーの勝者調整法(英語版)
- 3人用 セルフリッジ-コンウェイ法(英語版)
- 3人用 ストロンキストの４本ナイフ移動法(英語版)
- n人用 ブラムズ-テイラーの絶対的優位法(英語版)
- n人用 シモンズ-スーのスペルナー彩色近似法(英語版)
正確な公平の分割法
[編集]- 2人用 オースティンの２本ナイフ移動法 (英語版)
日常生活への応用
[編集]日常生活上の問題で、分割と選択法や成分分割体積等分法以外に、有用な公平分割法としては、勝者調整法が離婚夫婦用の財産分割法である。どちらも同じリストの複数個の対象項目を合計100点となるように点数評価し、１個以下の項目のみ細分割は許すが、それ以外はまるごとの項目の分割により、どちらも自分の分の獲得点数が相手の分の獲得点数以上に感じることができる。
スペルナー彩色近似法は、一軒家を複数人で賃貸する場合に有用である。例えば異なるタイプの部屋を３つ持つ一軒家を３人で共同で借りる場合の部屋・賃料の割当法となる[3]。スペルナー彩色近似法は連続数学のブラウワーの不動点定理の離散数学版であるスペルナーの補題を利用して、３人の第一希望の部屋がちょうど別々となる割り当てを見つけ出す近似法である。この方法により各自の第一希望の部屋を割り当てることができる。
出典
[編集]- ^ S. J. Brams and A. D. Taylor, Fair Division: from Cake-Cutting to Dispute Resolution, Cambridge University Press, 1996.
- ^ J. Robertson and W. Webb, Cake-Cutting Algorithms: Be Fair If You Can, A K Peters, 1998.
- ^ F. E. Su, Rental harmony: Sperner’s Lemma in Fair Division, American Mathematical Monthly 106 (10), 930 –942, 1999.