安定した結婚生活の問題

数学、経済学、コンピュータサイエンスにおいて、安定結婚問題（安定マッチング問題とも呼ばれる）は、各要素の優先順位が与えられた場合に、2 つの等しいサイズの要素セット間で安定マッチングを見つける問題です。マッチングは、 1 つのセットの要素から他のセットの要素への一対一の関係です。次の場合、マッチングは安定では ありません。

言い換えれば、マッチングにおいて、両者が現在のパートナーよりも相手を好む ペア ( A、B )が存在しない場合に、マッチングは安定していると言えます。

安定した結婚の問題は次のように述べられています。

n人の男性とn 人の女性がいて、各人が異性全員を好みの順位にランク付けしている場合、異性同士が現在のパートナーよりも相手を望むような関係にならないように、男性と女性を結婚させます。そのようなペアがいない場合、結婚の集合は安定しているとみなされます。

互いにペアになる必要がある 2 つのクラス (この例では異性愛者の男性と女性) の存在により、この問題は安定したルームメイト問題と区別されます。

安定した結婚問題の解決策を見つけるアルゴリズムは、さまざまな現実世界の状況に応用されていますが、その中で最もよく知られているのは、卒業した医学生の最初の病院への配属でしょう。^[1] 2012年、ロイド・S・シャプレーとアルビン・E・ロスは「安定した配分の理論と市場設計の実践」に対してノーベル経済学賞を受賞しました。 ^[2]

安定的結婚の重要かつ大規模な応用は、大規模な分散インターネット サービスでユーザーをサーバーに割り当てることです。^[3]インターネットでは、何十億ものユーザーが Web ページ、ビデオ、その他のサービスにアクセスしており、各ユーザーを、そのサービスを提供する世界中の (潜在的に) 数十万のサーバーの 1 つにマッチングさせる必要があります。ユーザーは、要求されたサービスに対してより速い応答時間を提供できるほど近くにあるサーバーを好み、その結果、各ユーザーに対してサーバーの (部分的な) 優先順序が付けられます。各サーバーは、より低コストでユーザーにサービスを提供することを優先するため、その結果、各サーバーに対してユーザーの (部分的な) 優先順序が付けられます。世界中のコンテンツやサービスの多くを配信するコンテンツ配信ネットワークは、数十秒ごとにユーザーとサーバーの間のこの大規模で複雑な安定的結婚問題を解決し、何十億ものユーザーを、要求された Web ページ、ビデオ、その他のサービスを提供できるそれぞれのサーバーにマッチングできるようにしています。^[3]

安定したマッチングのためのゲール・シャプレーアルゴリズムは、ヘブライ・ユニオン大学を卒業したラビをユダヤ教の会衆に割り当てるために使用されています。 ^[4]

一般的に、安定したマッチングは多種多様です。たとえば、次のような好みを持つ男性 3 人 (A、B、C) と女性 3 人 (X、Y、Z) がいるとします。

A: YXZ B: ZYX C: XZY  

X: BAC Y: CBA Z: ACB

このマッチング配置には、安定したソリューションが 3 つあります。

• 男性は第一選択、女性は第三選択（AY、BZ、CX）となります。
• すべての参加者は第 2 の選択肢 (AX、BY、CZ) を取得します。
• 女性は最初の選択肢、男性は 3 番目の選択肢 (AZ、BX、CY) を取得します。

これら 3 つの条件はすべて安定しています。不安定性は、参加者の両者が別の組み合わせに満足することを必要とするためです。1 つのグループに最初の選択肢を与えると、他の提案された組み合わせには満足しないため、組み合わせが安定していることが保証されます。全員に 2 番目の選択肢を与えると、他の組み合わせはいずれかの当事者に気に入られないことが保証されます。一般に、安定した結婚問題のあらゆるインスタンスに対する解の族は、有限分配格子の構造を与えることができ、この構造は安定した結婚に関するいくつかの問題に対する効率的なアルゴリズムにつながります。^[5]

n人の男性とn 人の女性による安定結婚問題の一様ランダムインスタンスでは、安定マッチングの平均数は漸近的に である。^[6] 異なる安定マッチングの数を最大化するように選択された安定結婚インスタンスでは、この数はnの指数関数である。^[7] 特定のインスタンスにおける安定マッチングの数を数えることは#P 完全 である。^[8]${\displaystyle e^{-1}n\ln n}$

1962年、デイヴィッド・ゲイルとロイド・シャプレーは、男女の数が同数であれば、安定した結婚問題を解決し、すべての結婚を安定させることが常に可能であることを証明した。彼らはそのためのアルゴリズムを提示した。 ^{[9] [10]}

ゲール・シャプレー法アルゴリズム(遅延承認アルゴリズムとも呼ばれる) には、いくつかの「ラウンド」(または「反復」) が含まれます。

• 最初のラウンドでは、まずa ) 婚約していない各男性が、最も好む女性にプロポーズし、次にb ) 各女性が、最も好む求婚者に「多分」と返事し、他の求婚者全員に「いいえ」と返事します。その後、女性はこれまでで最も好む求婚者と仮に「婚約」し、その求婚者も同様に、女性と仮に婚約します。
• その後の各ラウンドでは、まずa ) 婚約していない男性がそれぞれ、まだプロポーズしていない最も好ましい女性にプロポーズし (女性がすでに婚約しているかどうかは関係ありません)、次にb ) 女性が現在婚約していない場合、または現在の暫定パートナーよりもこの男性を好む場合 (この場合、女性は婚約していない現在の暫定パートナーを拒否します)、「多分」と返信します。婚約の暫定的な性質により、すでに婚約している女性が「上位の相手と交際する」権利 (そして、その過程で、それまでのパートナーを「捨てる」権利) が保持されます。
• このプロセスは、全員が参加するまで繰り返されます。

このアルゴリズムは、男性または女性の数が一定である時間 内に、参加者全員に安定した結婚をもたらすことが保証されている。 ^[11]${\displaystyle O(n^{2})}$${\displaystyle n}$

あらゆる可能な安定したマッチングの中で、すべての男性にとって最良かつすべての女性にとって最悪のマッチングが常に得られる。^[12]

これは男性（提案側）の視点から見ると誠実なメカニズムである。つまり、男性は自分の好みを偽ってより良いマッチングを得ることはできない。さらに、GSアルゴリズムは男性にとってグループ戦略証明でもある。つまり、男性の連合が自分たちの好みを偽って連合内のすべての男性が厳密により良い状態になるような調整をすることはできない。^[13]しかし、一部の連合が自分たちの好みを偽って、一部の男性がより良い状態になり、他の男性は同じパートナーを維持することは可能である。^[14] GSアルゴリズムは女性（レビュー側）にとって誠実ではない。つまり、各女性が自分の好みを偽ってより良いマッチングを得ることができる可能性がある。

地方病院定理は、医師と病院の職位のマッチング問題に適用される安定マッチング問題のより一般的な変種に関するもので、安定した結婚問題の基本的なn対n形式とは次のような点で異なります。

• 各参加者は、マッチングの相手側の参加者のサブセットとのみマッチングすることを希望する場合があります。
• マッチングの一方の参加者（病院）は、雇用を希望する医師の数を指定する数値的な能力を持つ場合があります。
• 一方の参加者の総数は、もう一方の参加者が対応する総容量と一致しない可能性があります。
• 結果のマッチングは、参加者全員に一致するとは限りません。

この場合、安定性の条件は、マッチングされていないペアが、マッチングにおける状況（その状況が別のパートナーであるか、マッチングされていないかに関係なく）よりもお互いを好まないことです。この条件では、安定したマッチングは依然として存在し、Gale-Shapley アルゴリズムによって依然として見つけることができます。

このような安定したマッチング問題について、地方病院定理は次のように述べています。

• 割り当てられた医師のセットと各病院の充足されたポジションの数は、すべての安定したマッチングで同じです。
• 安定したマッチングで空きポジションがある病院は、すべての安定したマッチングでまったく同じ医師のグループを受け入れます。

無関心との安定したマッチングでは、男性の中には2人以上の女性に対して無関心になる人もいれば、その逆の人もいる。

安定したルームメイト問題は安定した結婚問題に似ていますが、参加者全員が単一のプールに属するという点が異なります（「男性」と「女性」が同数に分割されるのではなく）。

病院/研修医問題（大学入学問題としても知られる）は、病院が複数の研修医を受け入れたり、大学が新入生を1クラス以上受け入れたりする可能性がある点で、安定結婚問題とは異なります。病院/研修医問題を解決するためのアルゴリズムは、病院指向（ 1995年以前のNRMPのように）^[15]または研修医指向です。この問題は、安定結婚問題を解決したGaleとShapleyの同じ元の論文でアルゴリズムを使用して解決されました。^[9]

カップルの病院/研修医問題では、研修医の集合に、同じ病院またはカップルが選択した特定の病院のペアに一緒に割り当てられる必要があるカップルを含めることができます（たとえば、結婚したカップルは、お互いに遠く離れたプログラムに縛られずに、一緒にいることを確実にしたいと考えています）。病院/研修医問題にカップルを追加すると、問題はNP完全になります。^[16]

割り当て問題は、重み付き二部グラフ内で最大重みを持つマッチングを見つけようとします。最大重み付きマッチングは安定している必要はありませんが、アプリケーションによっては、最大重み付きマッチングの方が安定したマッチングよりも優れています。

契約によるマッチング問題はマッチング問題の一般化であり、参加者は異なる契約条件でマッチングされる。^[17]契約の重要な特殊ケースは柔軟な賃金によるマッチングである。^[18]

• マッチング (グラフ理論) - グラフの異なる頂点間のマッチング。通常は優先順位とは無関係です。
• 嫉妬のないマッチング– 多対一マッチング問題に対する安定マッチングの緩和
• エッジカラーグラフのレインボーマッチング
• 安定マッチング多面体
• 安定マッチングの束
• 秘書問題（結婚問題とも呼ばれる） - 一連の選択肢の中で最高の報酬を得るためにいつ止めるかを決める

• Kleinberg, J., Tardos, E. (2005) Algorithm Design、第1章、pp 1–12。テキストについては関連ウェブサイトを参照。[1] Archived 2011-05-14 at the Wayback Machine。
• Knuth, DE (1996)。安定結婚と他の組み合わせ問題との関係: アルゴリズムの数学的分析入門。CRM プロシーディングおよび講義ノート。英語訳。アメリカ数学会。
• Pittel, B. (1992). 「安定結婚問題の尤もらしい解決について」.応用確率年報. 2 (2): 358–401. doi : 10.1214/aoap/1177005708 . JSTOR  2959755.
• Roth, AE (1984). 「医療インターンと研修医の労働市場の進化: ゲーム理論のケーススタディ」(PDF) . Journal of Political Economy . 92 (6): 991–1016. doi :10.1086/261272. S2CID  1360205.
• Roth, AE; Sotomayor, MAO (1990).両側マッチング: ゲーム理論的モデリングと分析の研究. Cambridge University Press .
• ショーハム、ヨアブ、レイトンブラウン、ケビン (2009)。マルチエージェントシステム：アルゴリズム、ゲーム理論、論理的基礎。ニューヨーク：ケンブリッジ大学出版局。ISBN 978-0-521-89943-7。セクション 10.6.4 を参照してください。オンラインで無料でダウンロードできます。
• シューマー、J.ヴォーラ、RV (2007)。 「お金を使わない仕組み設計」（PDF）。ニサンでは、ノーム。ラフガーデン、ティム。タルドス、エヴァ。ヴァジラニ、ビジェイ (編)。アルゴリズムゲーム理論。 255–262ページ。ISBN 978-0521872829。
• ガスフィールド、D.; アーヴィング、RW (1989)。安定した結婚問題: 構造とアルゴリズム。MITプレス。ISBN 0-262-07118-5。

• 安定した結婚問題のインタラクティブなフラッシュデモンストレーション
• https://web.archive.org/web/20080512150525/http://kuznets.fas.harvard.edu/~aroth/alroth.html#NRMP
• http://www.dcs.gla.ac.uk/research/algorithms/stable/EGSapplet/EGS.html
• 安定した結婚問題講義ノート