ゲール-シャプレイ (Gale-Shapley) アルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/03/12 04:50 UTC 版)
「安定結婚問題」の記事における「ゲール-シャプレイ (Gale-Shapley) アルゴリズム」の解説
上で述べたように、安定結婚問題の例が与えられたとき安定マッチングは必ず 1 つ以上存在する。そのうちの 1 つ（ないし、2つ）を Gale と Shapley により提案された、ゲール-シャプレイ (Gale-Shapley) アルゴリズム（以下、G-S アルゴリズムと略す）を用いて求めることができる。その手順は、次の通りである。 入力： n {\displaystyle n} 人の男性と k {\displaystyle k} 人の女性、および、各人の異性全員に対する選好順序のリスト出力：安定マッチング（つまり、男女 min { n , 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' のほうが好ましい希望順位が上( h ′ ≻ d h {\displaystyle h'\succ _{d}h} )ならば、h からのプロポーズを断る (b-2) d にとって h のほうが好ましい（ h ≻ d h ′ {\displaystyle h\succ _{d}h'} ）ならば、h' との婚約を解消し h と婚約する ステップ 2 現在婚約しているペアの集合を安定マッチングとして出力する。（終了） この G-S アルゴリズムは男性がプロポーズするという形式で記述されている。しかし、女性がプロポーズするという形式に変えてもなんら妥当性が失われるわけではない。男性がプロポーズすれば、男性の希望を最も反映した（各男性ごとの安定パートナーの中で最も好ましい女性とペアになっている）男性最良安定マッチングが得られ、女性がプロポーズすると、女性最良安定マッチングを得る。（男性がプロポーズする）G-S アルゴリズムは、(1) 1 人の男性が同じ女性に 2 度以上プロポーズしない、(2) 女性は婚約すると独身に戻らない、(3) 女性はプロポーズされる際その相手が悪くなることはない、ということからこのアルゴリズムが任意の例に対し、有限回の操作で安定マッチングを必ず導いて終了することがいえる。 この業績に対しロイド・シャープレー（89、史上2番目の高齢）に2012年のノーベル経済学賞が与えられた。
※この「ゲール-シャプレイ (Gale-Shapley) アルゴリズム」の解説は、「安定結婚問題」の解説の一部です。
「ゲール-シャプレイ (Gale-Shapley) アルゴリズム」を含む「安定結婚問題」の記事については、「安定結婚問題」の概要を参照ください。
- ゲール-シャプレイ アルゴリズムのページへのリンク
