安定結婚問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』

安定結婚問題（あんていけっこんもんだい）は安定マッチング問題の1つで、D.Gale(デイヴィッド・ゲール)とL.S.Shapley(ロイド・シャプレイ）によって1962年に提唱された問題である。

安定結婚問題の例題はN人の男性とN人の女性、および、各個人の希望リストからなる。 希望リストとは各個人の好みに基づき異性全員を全順序で並べたリストである。 安定結婚問題の解は安定なマッチングである。 安定結婚問題の例題に対し、互いに現在組んでいる相手よりも好きであるペア （以下ブロッキングペアとする）が存在しないマッチングを安定なマッチングという。 図1に安定結婚問題の例題とその例題の解となる安定なマッチング、および、安定でないマッチングを示す。

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

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

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

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

入力：n人の男性とn人の女性、および、各人の異性全員に対する希望リスト
出力：安定マッチング（つまり、男女n組のペア）

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

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

[編集] 参考図書

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

[編集] 関連項目

• 完全被覆問題