安定マッチング問題

数学、経済学、コンピュータ科学において、安定マッチング問題^{[ 1 ] [ 2 ] [ 3 ]}とは、各要素に対する選好の順序が与えられた場合に、同じサイズの2つの要素集合間の安定マッチングを見つける問題である。マッチングとは、一方の集合の要素から他方の集合の要素への全単射である。マッチングは、以下の場合には安定ではない。

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

安定した結婚生活の問題は、次のように述べられている。

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

互いにペアを組む必要がある2つのクラス（この例では異性愛者の男性と女性）が存在することが、この問題を安定したルームメイト問題と区別する点です。

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

コンテンツ配信ネットワークでは、Gale-Shapley アルゴリズムの拡張が使用されています。ユーザーの視点からのパフォーマンスを最適化し、サーバーの負荷をバランスさせるには、特定の種類のコンテンツ (Web ページやビデオなど) にアクセスするユーザーのクラスターと、目的のコンテンツを提供できるサーバークラスターを適切にマッチングさせる必要があります。これは、ネットワークトポロジやインターネットサービスプロバイダとの契約などの変数に基づいて、ユーザー クラスターとサーバー クラスターが互いに (部分的な) 選好を持つものとしてモデル化できます。これは、安定マッチング問題として解決できます。各側にクラスターの数が等しくないこと、需要と容量がクラスター間で異なる可能性があること、選好が全体的ではなく部分的であることから、古典的な Gale-Shapley アプローチの一般化が必要です。^{[ 6 ]}

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

一般的に、安定したマッチングは多数存在する可能性がある。例えば、3人の男性（A、B、C）と3人の女性（X、Y、Z）が以下のような好みを持っているとしよう。

A: YXZ  B: ZYX  C: XZY 

X: BAC  Y: CBA  Z: ACB

このマッチング配置には、3つの安定した解が存在する。

• 男性は第一希望、女性は第三希望（AY、BZ、CX）を選ぶことができる。
• 参加者全員が第二希望の選択肢（AX、BY、CZ）を受け取ることができます。
• 女性は第一希望、男性は第三希望（AZ、BX、CY）を選ぶことができる。

3つとも安定している。不安定性には、両方の参加者が別の相手とより幸せになる必要があるからである。一方のグループに最初の選択肢を与えると、他の提案された相手には不満を持つことになるので、マッチングは安定する。全員に2番目の選択肢を与えると、他のマッチングはどちらか一方の当事者に嫌われることになる。一般に、安定結婚問題のどのインスタンスの解の集合も有限分配束の構造を与えることができ、この構造は安定結婚に関するいくつかの問題に対する効率的なアルゴリズムにつながる。^{[ 8 ]}

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

1962年、デビッド・ゲイルとロイド・シャプレーは、大学入学と結婚を望む個人の文脈において、異なるグループに同数の人がいる場合、結果として生じるすべてのペアリング/マッチング要因を安定させるように、マッチングされたカップルとして解決することが常に可能であることを証明した。彼らはそうするためのアルゴリズムを提示した。^{[ 12 ] [ 13 ]}

ゲイル・シャプレーアルゴリズム（遅延受理アルゴリズムとも呼ばれる）は、多数の「ラウンド」（または「反復」）から構成されます。

• 第1ラウンドでは、まずa）婚約していない男性はそれぞれ最も気に入った女性にプロポーズし、次にb）女性は最も気に入った求婚者には「たぶん」と答え、他の求婚者には「いいえ」と答えます。こうして女性は、現時点で最も気に入った求婚者と暫定的に「婚約」し、その求婚者も同様に女性と暫定的に婚約します。
• その後の各ラウンドでは、まずa ) 婚約していない男性は、まだプロポーズしていない女性の中で最も気に入った女性にプロポーズし（その女性がすでに婚約しているかどうかは関係ない）、次にb ) 女性は、現在婚約していない場合、または現在の仮のパートナーよりもこの男性を好む場合は「たぶん」と答える（この場合、彼女は現在の仮のパートナーを拒否し、そのパートナーは婚約解除となる）。婚約が仮のものであるため、すでに婚約している女性は「​​より良い相手に乗り換える」（そしてその過程で、それまでのパートナーを「振る」）権利が保持される。
• 全員が参加するまで、このプロセスが繰り返される。

このアルゴリズムは、参加者全員にとって安定した結婚を時間内に実現することを保証します。${\displaystyle O(n^{2})}$どこ${\displaystyle n}$は男性または女性の数です。^{[ 14 ]}

考えられるすべての異なる安定マッチングの中で、それは常にすべての安定マッチングの中ですべての男性にとって最良のもの、そしてすべての女性にとって最悪のものを生み出す。^{[ 15 ]}

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

ゲイル・シャプレーアルゴリズムは、各ラウンドで未参加のメンが独立して提案を行うことができるため、大規模なSMPインスタンスを高速化するための並列性も明らかにします。並列実装では、メンを異なるスレッドに割り当て、同期プリミティブを使用して同時提案を解決し、キュー回避、局所性を考慮したデータレイアウト、ハイブリッドCPU-GPU実行などの最適化を使用してオーバーヘッドを削減できます。^{[ 18 ]}

地方病院の定理は、安定マッチング問題のより一般的な変形に関するもので、例えば病院の医師の配置問題に適用される問題などであり、安定結婚問題の基本的なn対nの形式とは以下の点で異なります。

• 各参加者は、マッチング相手の参加者のうち、一部の参加者とのみマッチングされることを希望する場合があります。
• マッチングの一方の参加者（病院側）は、採用可能な医師の数を指定する数値的な収容能力を持っている場合がある。
• 一方の側の参加者総数は、もう一方の側でマッチングされるべき収容人数の合計と一致しない場合があります。
• 結果として得られるマッチング結果は、すべての参加者に一致するとは限りません。

この場合、安定性の条件は、マッチングされていないペアが、マッチングにおける自身の状況（別のパートナーがいる状況、あるいはマッチングされていない状況）よりも互いを好まないことである。この条件を満たせば、安定したマッチングは存在し、ゲイル・シャプレーアルゴリズムによって見つけることができる。

このような安定マッチング問題に関して、農村病院の定理は次のように述べている。

• 割り当てられた医師のセットと、各病院で充足されたポストの数は、すべての安定したマッチングにおいて同じである。
• 安定したマッチングにおいて空きポジションがある病院は、すべての安定したマッチングにおいて全く同じ医師の配置を受けることになる。

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

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

病院/研修医問題（大学入学問題とも呼ばれる）は、病院が複数の研修医を受け入れることができる、あるいは大学が複数の学生からなる新入生クラスを受け入れることができるという点で、安定結婚問題とは異なります。病院/研修医問題を解決するためのアルゴリズムは、病院指向（1995 年以前のNRMPのように） ^{[ 19 ]}または研修医指向のものがあります。この問題は、安定結婚問題を解決したのと同じ Gale と Shapley の原著論文でアルゴリズムによって解決されました。^{[ 12 ]}

カップルを含む病院/研修医問題では、研修医の集合に、同じ病院またはカップルが選択した特定の病院のペアに一緒に割り当てられなければならないカップルを含めることができます（たとえば、既婚カップルは、お互いに遠く離れたプログラムに閉じ込められることなく、一緒にいられるようにしたいと考えている）。病院/研修医問題にカップルを追加すると、この問題はNP完全になります。^{[ 20 ]}

割り当て問題とは、重み付き二部グラフにおいて、最大の重みを持つマッチングを見つけることを目的とする問題である。最大重みマッチングは必ずしも安定している必要はないが、場合によっては、安定マッチングよりも最大重みマッチングの方が優れていることもある。

契約とのマッチング問題は、参加者が異なる契約条件でマッチングされるマッチング問題の一般化である。^{[ 21 ]}契約の重要な特殊ケースは、柔軟な賃金とのマッチングである。^{[ 22 ]}

一般的なマッチング問題は、マッチングを求めます${\displaystyle M^{*}}$他のマッチングは存在しない${\displaystyle M}$より多くの人が幸せでいる${\displaystyle M}$より${\displaystyle M^{*}}$非二部グラフ入力の場合、ポピュラーマッチングが存在するかどうかを判定することはNP完全である。 ^{[ 23 ]}

• マッチング（グラフ理論） – グラフの異なる頂点間のマッチング。通常、選好順序とは関係がない。
• 羨望のないマッチング– 多対一マッチング問題に対する安定マッチングの緩和
• エッジカラーグラフのレインボーマッチング
• 安定マッチング多面体
• 秘書問題（結婚問題とも呼ばれる） – 一連の選択肢の中で、最良の報酬を得るためにいつ止めるべきかを決定すること

• Kleinberg, J.、および Tardos, E. (2005)アルゴリズム設計、第 1 章、pp 1–12。テキストについては、付随するウェブサイトを参照してください。Wayback Machineに2011年5月14日にアーカイブされました。
• Knuth, DE (1996).安定結婚とその他の組み合わせ問題との関係：アルゴリズムの数学的解析入門. CRM 論文集および講義ノート. 英語訳. アメリカ数学会.
• Pittel, B. (1992). 「安定した結婚問題の可能性のある解について」 . The Annals of Applied Probability . 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 Press。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
• 安定した結婚生活の問題に関する講義ノート