公平な分割

公平な分割は、ゲーム理論において、一連のリソースを、それに対する権利を有する複数の人々の間で分割し、各人が正当な取り分を受け取るようにするという問題である。この問題は、相続財産の分割、パートナーシップの解消、離婚の和解、電子周波数の割り当て、空港の交通管理、地球観測衛星の活用など、さまざまな現実世界の状況で発生する。これは、数学、経済学（特に社会的選択理論）、紛争解決における活発な研究分野である。公平な分割の中心となる信条は、そのような分割は、プレーヤー自身だけが実際に商品の価値を知っているため 、外部の仲裁を必要とせずに、プレーヤー自身によって行われるべきであるというものである。

公平な分割アルゴリズムの典型は、分割と選択です。これは、異なる好みを持つ 2 人のエージェントが、それぞれが最高のケーキを選んだと確信できるようにケーキを分割できることを示しています。公平な分割の研究は、この手順をさまざまなより複雑な設定に拡張したものと見ることができます。

公平な分割の問題には、分割する商品の性質、公平性の基準、プレーヤーの性質とその好み、分割の質を評価するその他の基準に応じて、さまざまな種類があります。

正式には、公平な分割問題は、集合(「ケーキ」と呼ばれることが多い) とプレーヤーのグループによって定義されます。分割とは、 を互いに素な部分集合に分割することです。つまり、プレーヤーごとに 1 つの部分集合です。 ${\displaystyle C}$${\displaystyle n}$${\displaystyle C}$${\displaystyle n}$${\displaystyle C=X_{1}\sqcup X_{2}\sqcup \cdots \sqcup X_{n}}$

セットにはさまざまなタイプがあります: ${\displaystyle C}$

• ${\displaystyle C}$は、たとえば、各アイテムが 1 人の人に完全に渡されるような、分割できないアイテムの有限集合である場合があります。${\displaystyle C=\{{\text{ピアノ}},{\text{車}},{\text{アパート}}\}}$
• ${\displaystyle C}$は、お金やケーキなどの分割可能なリソースを表す無限集合です。数学的には、分割可能なリソースは実空間のサブセットとしてモデル化されることが多く、たとえば、セクション [0,1] は、平行に切断する必要がある細長いケーキを表します。単位円は、アップルパイを表します。

さらに、分割されるセットは次のようになります。

• 同質性 – 例えば、金額だけが重要なお金、または
• 異質 – 例えば、異なる材料や異なるアイシングなどが使われているケーキなど。

最後に、分割する項目が以下のものであるかどうかについて、いくつかの仮定を立てるのが一般的です。

• 車やケーキなどの商品、または
• 悪いこと（家事など）

これらの区別に基づいて、いくつかの一般的なタイプの公平な分割問題が研究されてきました。

• 公正な品目の割り当て- 分割不可能な異質な品物のセットを分割します。
• 公平な資源配分 - 分割可能で同質な財のセットを分割すること。特別なケースとして、単一の同質な資源を公平に分割することがあります。
• 公平なケーキカット–分割可能な異質な財を分割する。特別なケースとして、ケーキが円形の場合があり、その場合、この問題は公平なパイカットと呼ばれます。
• 公正な雑用分担-分割可能な異質な悪を分割する。

組み合わせや特殊なケースもよく見られます。

• 賃貸の調和（別名、ハウスメイト問題） - 分割不可能な異質な財（例：アパートの部屋）のセットと、同時に分割可能な同質な悪（アパートの家賃）を分割します。
• 公平な河川分配- 国際河川を流れる水をその流域の国々間で分割すること。
• 公平なランダム割り当て（くじを複数の部門に分ける）は、分割できない財を割り当てるときに特に一般的です。

通常公平な分割と呼ばれるもののほとんどは、仲裁の使用により、理論上は公平とは見なされません。このような状況は、現実の問題にちなんで名付けられた数学理論では頻繁に発生します。財産が破産した場合の権利に関するタルムードの決定は、公平性に関する複雑な考えの発展を反映しています。^[1]しかし、それらはラビによる法的議論の結果であり、請求者の評価による分割ではありません。

主観的価値理論によれば、各アイテムの価値を客観的に測ることはできない。したがって、人によって各アイテムに異なる価値を割り当てる可能性があるため、客観的な公平性は不可能である。人々が公平性の概念をどのように定義するかに関する実証実験では、決定的な結果は得られていない。^[2]

したがって、公平性に関する現在の研究のほとんどは、主観的公平性の概念に焦点を当てています。各人は、 の各サブセットに数値を割り当てる個人的な主観的な効用関数または価値関数を持っていると想定されています。多くの場合、関数は正規化されていると想定されており、すべての人にとって、空集合は 0 (すべての i に対して)、アイテムが望ましい場合はアイテムのセット全体が 1 (すべての i に対して)、アイテムが望ましくない場合は -1 と評価されます。例を次に示します。 ${\displaystyle n}$${\displaystyle V_{i}}$${\displaystyle C}$${\displaystyle V_{i}(\emptyset )=0}$${\displaystyle V_{i}(C)=1}$

• が分割できないアイテムの集合 {ピアノ、車、アパート} である場合、アリスは各アイテムに 1/3 という値を割り当てることができます。これは、各アイテムがアリスにとって他のアイテムとまったく同じように重要であることを意味します。ボブは集合 {車、アパート} に 1 という値を割り当て、X 以外の他のすべての集合に 0 という値を割り当てることができます。これは、ボブが車とアパートだけを一緒に取得したいことを意味します。車だけ、アパートだけ、またはそれぞれとピアノを一緒に取得することは、ボブにとって価値がありません。${\displaystyle C}$
• ケーキが細長い場合（区間 [0,1] としてモデル化）、アリスは各サブセットにその長さに比例した値を割り当てることができます。つまり、アイシングに関係なく、ケーキをできるだけ多くしたいということです。ボブは、たとえば [0.4, 0.6] のサブセットにのみ値を割り当てることができます。これは、ケーキのこの部分にはチェリーが含まれており、ボブはチェリーだけを気にしているからです。${\displaystyle C}$

これらの主観的価値関数に基づいて、公平な分割のための広く使用されている基準がいくつかあります。これらの中には互いに矛盾するものもありますが、組み合わせられることも多いです。ここで説明する基準は、各プレイヤーが同じ金額を受け取る権利がある場合に限ります。

• 比例分割とは、各プレイヤーが自分の価値関数に従って、少なくとも正当な取り分を得ることを意味します。たとえば、3 人でケーキを分割する場合、各自が自分の評価に従って少なくとも 3 分の 1 を受け取ります。つまり、n人の各人が、合計値の 少なくとも 1/ nとして評価するサブセットを取得します 。${\displaystyle C}$
  • ${\displaystyle V_{i}(X_{i})\geq V_{i}(C)/n}$すべてのiのために。
• 超比例分割とは、各プレイヤーが 1/ nより厳密に大きい金額を受け取る分割です。 (このような分割は、プレイヤーの評価が異なる場合にのみ存在します。)
  • ${\displaystyle V_{i}(X_{i})>V_{i}(C)/n}$すべての私に対して。
• 嫉妬のない分割では、誰も自分の取り分よりも他人の取り分を欲しがらないことが保証されます。つまり、すべての人が自分の取り分を少なくとも他の取り分と同じくらい大切にします。
  • ${\displaystyle V_{i}(X_{i})\geq V_{i}(X_{j})}$すべての i と j について。
• グループ羨望のない分割は、エージェントのどのサブセットも、同じサイズの別のサブセットを羨まないことを保証します。これは、羨望のない状態よりも強い条件です。
• 公平な分割とは、各プレイヤーの自分のスライスに対する評価が等しい、つまり、それぞれが同等の価値を受け取る、または「同等の幸福を経験する」ことを意味します。これは難しい目標です。なぜなら、プレイヤーは自分の評価を尋ねられた場合に正直である必要がないからです。
  • ${\displaystyle V_{i}(X_{i})=V_{j}(X_{j})}$すべての i と j について。
• 正確な分割（コンセンサス分割とも呼ばれます）は、すべてのプレーヤーが各シェアの価値に同意する分割です。
  • ${\displaystyle V_{i}(X_{i})=V_{j}(X_{i})}$すべての i と j について。

上記の基準はすべて、参加者が平等な権利を持っていることを前提としています。参加者ごとに権利が異なる場合 (たとえば、各パートナーが異なる金額を投資したパートナーシップなど)、公平性の基準もそれに応じて調整する必要があります。権利が異なる場合の比例ケーキカットを参照してください。

公平性に加えて、分割がパレート最適であること、つまり、他の割り当てでは誰かの利益が増す一方で誰かの不利益は増さないことが望まれる場合があります。効率性という用語は、効率的市場という経済学の考えに由来しています。この定義によれば、1 人のプレーヤーがすべてを得る分割は最適であるため、それだけでは公平な取り分さえ保証されません。効率的なケーキカットと公平性の代償も参照してください。

現実世界では、人々は他のプレイヤーが商品をどのように評価しているかについて非常に正確な考えを持っている場合があり、それを非常に気にすることがあります。お互いの評価について完全に知っている場合は、ゲーム理論でモデル化できます。部分的な知識をモデル化するのは非常に困難です。公平な分割の実際的な側面の大部分は、そのような部分的な知識や小さな間違いにもかかわらずうまく機能する手順を考案し、研究することです。

追加の要件は、公平な分割手順が戦略証明可能であることです。つまり、参加者が真の評価を報告することが主要な戦略である必要があります。この要件は、特に公平性とパレート効率と組み合わせると、通常、満たすのが非常に困難です。その結果、多くの場合、インセンティブ互換性に弱められ、プレーヤーが特定のソリューションコンセプトに従って行動する場合にのみ、真の評価を報告することが求められます。

公平な分割手順では、プレイヤーが実行すべきアクションを、表示可能なデータと評価に基づいてリストします。有効な手順とは、各プレイヤーが自分の評価に従って合理的に行動する公平な分割を保証する手順です。アクションがプレイヤーの評価に依存する場合、手順は合理的なプレイヤーが従う戦略を記述します。プレイヤーはピースに異なる価値があるかのように行動できますが、一貫性が必要です。たとえば、手順で最初のプレイヤーがケーキを 2 つの均等な部分に切り分け、2 番目のプレイヤーがピースを選択する場合、最初のプレイヤーは 2 番目のプレイヤーの方が多く獲得したと主張することはできません。

プレイヤーが行うことは次のとおりです。

• 公平な分割の基準について合意する
• 有効な手順を選択し、そのルールに従う

各プレイヤーの目的は、獲得できる最小額を最大化すること、言い換えれば、maximin を達成することであると想定されます。

手順は、離散手順と連続手順に分けられます。離散手順では、たとえば、ケーキを切ったり、マークを付けたりするのは一度に 1 人だけです。連続手順では、1 人のプレーヤーがナイフを動かし、もう 1 人のプレーヤーが「ストップ」と言うようなことが行われます。別の種類の連続手順では、1 人のプレーヤーがケーキの各部分に値を割り当てます。

公平な分割手順の一覧については、カテゴリ:公平な分割プロトコルを参照してください。

各プレイヤーが1つの連結したピースを受け取る場合、3人以上のプレイヤー間でケーキを嫉妬なく分割することを保証できる有限プロトコル（たとえ無制限であっても）はありません。^[3]ただし、この結果は、その研究で提示されたモデルにのみ適用され、たとえば、仲介者がプレイヤーの評価関数に関する完全な情報を持ち、この情報に基づいて分割を提案する場合には適用されません。^[4]

最近、公平な分割のモデルは、個々のエージェントからエージェントのファミリー(事前に決定されたグループ) に拡張されました。グループ間の公平な分割を参照してください。

ソル・ガーファンクルによれば、ケーキカット問題は20世紀数学で最も重要な未解決問題の一つであったが^[5] 、この問題の最も重要な変種は1995年にスティーブン・ブラムスとアラン・テイラーによってブラムス・テイラー手順で最終的に解決された。

分割と選択の起源は文書化されていません。関連する活動である交渉と物々交換も古くから行われています。2人以上の人が関わる交渉も非常に一般的で、ポツダム会談は最近の注目すべき例です。

公平な分割の理論は、第二次世界大戦の終わりごろまで遡る。この理論は、当時ポーランドにあったリ​​ヴィウのスコティッシュ カフェでよく会合を開いていたポーランドの数学者、ヒューゴ シュタインハウス、ブロニスワフクナスター、ステファン バナッハのグループによって考案された。1944 年には、「last-diminisher」と呼ばれる、プレーヤーの数を問わない比例(公平な分割)分割が考案された。シュタインハウスは、1947 年 9 月 17 日にワシントン DC で開催された計量経済学会の会議でこの問題を初めて公表し、これをバナッハとクナッハの功績だとした。この会議でシュタインハウスは、このような分割に必要な最小のカット数を求める問題も提案した。

羨望のないケーキカットの歴史については、「 羨望のないケーキカット」を参照してください。

• 17匹の動物の相続パズルは、 17頭のラクダ（または象、馬）を1/2、1/3、1/9の割合に公平に分割するパズルです。これは人気のある数学パズルで、起源は古代にあるとよく言われますが、最初に文書化されたのは18世紀のイランでした。^[6]
• ナンバーズシーズン3のエピソード「ワン・アワー」で、チャーリーは誘拐犯が要求した金額に当てはまるケーキカット問題について話します。
• ヒューゴ・シュタインハウスは著書『数学のスナップショット』の中で、公平な割り算のさまざまなバリエーションについて書いている。著書の中で、彼は、公平な割り算の特別な3人バージョンが1944年にベルデフフのG.クロクマイニーによって考案され、別のバージョンはL.コット夫人によって考案されたと述べている。^[7]
• マーティン・ガードナーとイアン・スチュワートはともにこの問題に関する章を含む本を出版している。^{[8] [9]マーティン・ガードナーはこの問題の雑用分担形式を導入した。イアン・スチュワートは}Scientific AmericanとNew Scientistの記事で公平な分担問題を普及させた。
• 恐竜漫画はケーキカット問題に基づいています。^[10]
• イスラエル映画「聖クララ」では、ロシア移民がイスラエルの数学教師に、円形のケーキを7人で公平に分けるにはどうしたらよいかと質問します。教師の答えは、ケーキの真ん中を3回まっすぐに切って、8等分にすることです。7人しかいないので、共産主義の精神にのっとり、1つは捨てるべきです。

• 公平な分割実験
• 公平な分割における未解決の問題のリスト
• オンラインフェア部門
• 戦略的フェア分割
• 配分と配分の数学
• 公平性（経済学）
• 国際貿易
• 正義（経済）
• ナップザック問題
• ナッシュの交渉ゲーム
• ピザ定理
• 公平さの代償

• ヤング、ペイトン H. (1995)。『公平性：理論と実践』プリンストン大学出版局。
• Brams, Steven J.; Taylor, Alan D. (1996).公正な分割: ケーキカットから紛争解決まで。ケンブリッジ大学出版局。ISBN 0-521-55644-9。
• ロバートソン、ジャック、ウェッブ、ウィリアム (1998)。ケーキカットアルゴリズム: できる限り公平に。マサチューセッツ州ネイティック: AK ピーターズ。ISBN 978-1-56881-076-8LCCN 97041258.  OL 2730675W  .
• エルヴェ・ムーラン（2004年）「公正な分割と集団的福祉」マサチューセッツ州ケンブリッジ：MIT出版。ISBN 9780262134231。
• バルバネル、ジュリアス B. (2005)。効率的で公平な分割の幾何学。アラン D. テイラーによる序文。ケンブリッジ: ケンブリッジ大学出版局。doi : 10.1017 / CBO9780511546679。ISBN 0-521-84248-4MR  2132232 。 短い要約は、 Barbanel, J. (2010). 「A Geometric Approach to Fair Division」でご覧いただけます 。The College Mathematics Journal . 41 (4): 268. doi :10.4169/074683410x510263。
• スティーブン・J・ブラムス（2008年）。『数学と民主主義：より良い投票と公平な分割手続きの設計』プリンストン、ニュージャージー：プリンストン大学出版局。ISBN 9780691133218。

• ヴィンセント・P・クロフォード（1987年）「公正な分割」『新パルグレイブ経済学辞典』第2巻、274～275ページ。
• ハル・ヴァリアン（1987年）「公平性」『新パルグレイブ経済学辞典』第2巻、275～276ページ。
• ブライアン・スカイムズ（1996年）『社会契約の進化』ケンブリッジ大学出版局。ISBN 978-0-521-55583-8 
• Hill, TP (2000). 「公平な分配を得るための数学的手段」. American Scientist . 88 (4): 325–331. Bibcode :2000AmSci..88..325H. doi :10.1511/2000.4.325. S2CID  221539202.
• Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016)。計算的社会的選択ハンドブック。ケンブリッジ大学出版局。ISBN 9781107060432。（無料オンライン版）、第11章～第13章。
• クリスチャン・クラムラー著「公正な分割」 – グループ意思決定および交渉ハンドブック 183～202 ページ。
• ケーキカット：分割可能な財の公正な分割、クラウディア・リンドナーとヨルグ・ローテ著、Economics and Computation pp 395-491。
• 不可分財の公正な分割、Jérôme Lang と Jörg Rothe 著、Economics and Computation pp 493-550。

• コロラド大学ボルダー校の離散数学プロジェクトによる公平な除算。
• 公平な分割：マーカー方式
• 公正な分割：密封入札方式