安定結婚問題

安定結婚問題（あんていけっこんもんだい、英: stable marriage problem）とはデイヴィッド・ゲールとロイド・シャープレーによって1962年に提示された問題である。

安定結婚問題は $n$ 人の男性と $k$ 人の女性、および、各個人の選好順序からなる。選好順序とは各個人の好みに基づき異性全員と自分自身を全順序で並べたリストである。ここで、「自分自身」とは誰とも結婚せずに独身のままでいることを意味し、「参加者全員が独身であるよりも望ましい相手と結婚している」マッチングは個人合理性（英: individuality rationality）を満たすと定義される。安定結婚問題の解は安定なマッチングである。安定結婚問題に対し、互いに現在組んでいる相手よりも好きであるペア（以下ブロッキングペアとする）が存在せず、全員が個人合理性を満たすマッチングを安定マッチング（英: stable matching）という。

下図に安定結婚問題の例題とその例題の解となる安定なマッチング、および、安定でないマッチングを示す。「：」以下が各個人の希望リストである。点線はブロッキングペアを表している。

全ての例題について、安定マッチングは必ず存在する。それを見つける O(N²) 時間アルゴリズムが存在することも知られている（下を参照）。

ゲール-シャープレー (Gale-Shapley) アルゴリズム

→詳細は「ゲール-シャープレー・アルゴリズム（英語版）」を参照

上で述べたように、安定結婚問題の例が与えられたとき安定マッチングは必ず 1 つ以上存在する。そのうちの 1 つ（ないし、2つ）を Gale と Shapley により提案された、ゲール-シャプレイ (Gale-Shapley) アルゴリズム（以下、G-S アルゴリズムと略す）を用いて求めることができる。その手順は、次の通りである。

入力： $n$  人の男性と  $k$  人の女性、および、各人の異性全員に対する選好順序のリスト

出力：安定マッチング（つまり、男女  $\min\{n,k\}$  組以下のペア）


ステップ 0 [初期設定] 全員の状態は独身とする（全ての男性はどの女性にもプロポーズを行っていない）。
 

ステップ 1　独身の男性 h が存在する限り、以下の操作を繰り返す。

 1-1 男性 h はまだプロポーズしていない女性の中で、最も好きな（つまり、希望リストの最高位の）相手女性 d に
 プロポーズする
 

 1-2 (a) d が独身ならば、d は h と婚約する
 

     (b) d がすでに h' と婚約している場合

        (b-1) d にとって h' のほうが好ましい希望順位が上( $h'\succ _{d}h$ )ならば、h からのプロポーズを断る
 

        (b-2) d にとって h のほうが好ましい（ $h\succ _{d}h'$ ）ならば、h' との婚約を解消し h と婚約する
 

ステップ 2　現在婚約しているペアの集合を安定マッチングとして出力する。（終了）

この G-S アルゴリズムは男性がプロポーズするという形式で記述されている。しかし、女性がプロポーズするという形式に変えてもなんら妥当性が失われるわけではない。男性がプロポーズすれば、男性の希望を最も反映した（各男性ごとの安定パートナーの中で最も好ましい女性とペアになっている）男性最良安定マッチングが得られ、女性がプロポーズすると、女性最良安定マッチングを得る。
（男性がプロポーズする）G-S アルゴリズムは、(1) 1 人の男性が同じ女性に 2 度以上プロポーズしない、(2) 女性は婚約すると独身に戻らない、(3) 女性はプロポーズされる際その相手が悪くなることはない、ということからこのアルゴリズムが任意の例に対し、有限回の操作で安定マッチングを必ず導いて終了することがいえる。

この業績に対しロイド・シャープレー（89、史上2番目の高齢）に2012年のノーベル経済学賞が与えられた。