安定結婚問題とは？ わかりやすく解説

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

安定結婚問題は${\displaystyle n}$

「：」以下が各個人の希望リストである。点線はブロッキングペアを表している。

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

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

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

入力：${\displaystyle n}$ 人の男性と ${\displaystyle k}$ 人の女性、および、各人の異性全員に対する選好順序のリスト
出力：安定マッチング（つまり、男女 ${\displaystyle \min\{n,k\}}$ 組以下のペア）

ステップ 0 [初期設定] 全員の状態は独身とする（全ての男性はどの女性にもプロポーズを行っていない）。
 
ステップ 1　独身の男性 h が存在する限り、以下の操作を繰り返す。
 1-1 男性 h はまだプロポーズしていない女性の中で、最も好きな（つまり、希望リストの最高位の）相手女性 d に
 プロポーズする
 
 1-2 (a) d が独身ならば、d は h と婚約する
 
     (b) d がすでに h' と婚約している場合
        (b-1) d にとって h' のほうが好ましい希望順位が上(${\displaystyle h'\succ _{d}h}$)ならば、h からのプロポーズを断る
 
        (b-2) d にとって h のほうが好ましい（${\displaystyle h\succ _{d}h'}$）ならば、h' との婚約を解消し h と婚約する
 
ステップ 2　現在婚約しているペアの集合を安定マッチングとして出力する。（終了）

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

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

参考図書

• 応用数理計画ハンドブック（朝倉書店）

関連項目

• 完全被覆問題