公平分割問題

公平分割問題とは

公平分割問題（fair division problem）は、複数の関係者が持つ多様な価値基準の下で、共有する物や財産をいかにして「公平に」分割するか、その理論や具体的な手法を数学的に探究する分野です。この問題は、特定の状況においては「ケーキ切り問題」とも呼ばれることがあります。その起源は第二次世界大戦中、数学者シュタインハウスによって提起されたことに遡ります。戦後、1947年にワシントンD.C.で開催された計量経済学の国際会議を機に、数学者だけでなく、経済学や情報科学など幅広い分野の研究者の関心を集めるようになりました。この分野では、さまざまな価値観を持つ参加者それぞれが、自身の分け前に対して納得できるような分割のやり方が存在するのか、また実際にどのように分割すればそれが実現できるのかを解明することを目指します。

問題設定の多様性

公平分割問題には様々な設定が考えられます。まず、分割の対象となる物については、全ての参加者が価値を認めるもの、全員がむしろ負担と感じるもの、全体が均質な性質を持つもの、部分ごとに価値が異なるものなどがあります。また、対象物が自由に細かく分けられるものか、あるいは一個単位でしか分割できないかといった特性も重要です。

参加者が感じる「公平」の基準にも多様性があります。例えば、自身の受け取った分の価値が、その人自身の価値観で見た全体価値の人数分の一以上であると感じられる状態、あるいは、自分の受け取った分の価値が、他の誰かの受け取った分の価値と比べて劣っていないと感じられる状態、さらには、全ての参加者が自分の分も他の人の分も、それぞれの価値観で見てちょうど全体価値の人数分の一に等しいと感じられる状態などがあります。

参加者の人数も、2人という単純なケースから、3人、あるいはより一般的な多数の参加者を想定する場合があります。さらに、分割方法の決定プロセスも、参加者が一人ずつ順番に選択や分割を行う逐次的な方法や、全員が同時に提案される分割案を検討しながら進める方法など、様々なシナリオが考慮されます。

このような多岐にわたる問題設定に対して、公平な分割を実現するためのアルゴリズムが数多く開発されています。これらのアルゴリズムの中には、厳密な解法だけでなく、近似的な解を求める手法も含まれます。多くの場合、これらのアルゴリズムは特定の種類の公平分割が存在することを証明する目的で提案されていますが、中には日常生活における具体的な問題解決に役立つものも開発されています。

「公平」の基準について

参加者全員が分割対象を好ましいと感じている状況を例に、「公平」の基準について詳しく見てみましょう。

割合の公平 (Proportionality): これは、自身の価値観に基づいて、受け取った分の価値が全体の価値の人数分の一以上であると感じる状態を指します。
うらやましさ無しの公平 (Envy-freeness): これは、自身の価値観から見て、自分の受け取った分の価値が他のどの参加者の受け取った分の価値よりも小さくないと感じる状態です。うらやましさ無しの状態が実現できていれば、自動的に割合の公平も満たされます。しかし、その逆は必ずしも真ではありません。例えば、3人で羊羹を分ける際に、自分の分が全体の1/3以上の価値があると納得できたとしても、他の誰かの受け取った分の方が自分の分よりも価値が高いと感じる可能性はあります。
* 正確な公平 (Exact division): これは、自身の価値観に基づいて、自分の受け取った分の価値も、他のどの参加者の受け取った分の価値も、ちょうど全体の価値の人数分の一であると感じる状態を指します。正確な公平が実現されていれば、うらやましさ無しの公平も割合の公平も自動的に満たされます。

対象物に対する各参加者の価値評価はそれぞれ異なっていても構いませんが、対象物を好む場合、何も得られない場合の評価は0、一人で全体を得た場合の評価は1、そして得られた部分の価値は加算的である（すなわち、既得分に新たに得た部分の価値を加えると全体の評価値が増える）と仮定されることが多いです。このとき、何も持たない状態から対象物を増やしていくにつれて、参加者の感じる価値は0から1へと連続的に変化すると考えられます。

歴史的な分割法と現代のアルゴリズム

公平分割理論が体系化される以前から用いられていた分割方法もあります。2人の参加者が、好ましい対象物を自由に分割できる場合の古典的な方法として、紀元前から知られるのが「分割と選択法」（divide and choose、切る人・選ぶ人法とも）です。この方法では、まず一方の参加者が自分の価値基準で対象物を価値の等しい二つの部分に分け、次にもう一方の参加者が、自身の価値観で見て価値の高い方を選びます。最後に、残った部分を最初に切った人が受け取ります。この方法では、どちらの参加者も、自分の受け取った分の価値が相手の分以上の価値であると感じることができます。この手法は、全員が好む対象物だけでなく、全員が嫌うものを分割する場合にも応用可能です。

もう一つ、日常生活で行われる方法に「成分分割体積等分法」があります。これは、対象物が複数の異なる成分に分けられる場合に、それぞれの成分を人数分の均等な量に分割する方法です。この方法によれば、各参加者は全体の価値の人数分の一の価値を受け取ったと感じることができます。ただし、この方法で各自が得た価値の合計は、全体の価値と等しくなります。

現代では、様々な基準の公平分割を実現するための多くのアルゴリズムが研究されています。例えば、割合の公平を実現するものとして、3人用のシュタインハウスの方法や、n人用のバナッハとクナステルの最後に切った人法、デュビンスとスパニアの1本ナイフ移動法などがあります。うらやましさ無しの公平に関しては、前述の2人用の分割と選択法に加え、2人用のブラムズ-テイラーの勝者調整法、3人用のセルフリッジ-コンウェイ法やストロンキストの4本ナイフ移動法、そしてn人用のブラムズ-テイラーの絶対的優位法やシモンズ-スーのスペルナー彩色近似法などがあります。また、正確な公平を目指す方法としては、2人用のオースティンの2本ナイフ移動法などが知られています。

日常生活への応用

公平分割の考え方やアルゴリズムは、日常生活の様々な場面に応用されています。前述の分割と選択法や成分分割体積等分法以外に、特に実用的なものとして勝者調整法があります。これは離婚における財産分割などに用いられる方法です。対象となる複数の財産項目に対し、双方それぞれが合計100点となるように価値を点数化し、原則として項目をそのまま分割します。これにより、どちらの当事者も自分の得た財産の合計点数が相手の得た点数以上であると感じられるように分割を目指します。

また、スペルナー彩色近似法は、複数人で一軒家を賃貸する際の部屋割りや家賃の負担額を決定するのに役立ちます。例えば、タイプが異なる3つの部屋がある家を3人で借りる場合、それぞれの参加者が最も希望する部屋を割り当てつつ、家賃負担も適切に配分するといった問題に応用されます。この方法は、数学的な定理（スペルナーの補題など）を利用して、参加者の希望を考慮した割り当てを見つける近似的な手法です。

公平分割問題の研究は、理想的な「公平」の定義を探求し、それを実現するための数学的な手続きを開発することで、資源の分配や協力的な意思決定における実際的な課題解決に貢献しています。

もう一度検索