|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 安定 ： [あんてい] 1. (adj-na,n,vs) stability 2. equilibrium ・ 結婚 ： [けっこん] marriage ・ 問 ： [もん] 【名詞】 1. problem 2. question ・ 問題 ： [もんだい] 【名詞】 1. problem 2. question ・ 題 ： [だい] 1. (n,vs) title 2. subject 3. theme 4. topic
安定結婚問題（あんていけっこんもんだい）は安定マッチング問題の 1 つで、D. Gale（デイヴィッド・ゲール）と L. S. Shapley（ロイド・シャプレイ）によって1962年に提唱された問題である。 安定結婚問題の例題は ''N'' 人の男性と ''N'' 人の女性、および、各個人の希望リストからなる。希望リストとは各個人の好みに基づき異性全員を全順序で並べたリストである。安定結婚問題の解は安定なマッチングである。安定結婚問題の例題に対し、互いに現在組んでいる相手よりも好きであるペア（以下ブロッキングペアとする）が存在しないマッチングを安定なマッチングという。 図1に安定結婚問題の例題とその例題の解となる安定なマッチング、および、安定でないマッチングを示す。 画像:SMExample.JPG 「：」以下が各個人の希望リストである。点線はブロッキングペアを表している。 全ての例題について、安定マッチングは必ず存在する。それを見つける ''O''(''N''2) 時間アルゴリズムが存在することも知られている（下を参照）。 == ゲール-シャプレイ (Gale-Shapley) アルゴリズム == 上で述べたように、安定結婚問題の例が与えられたとき安定マッチングは必ず 1 つ以上存在する。そのうちの 1 つ（ないし、2つ）を Gale と Shapley により提案された、ゲール-シャプレイ (Gale-Shapley) アルゴリズム（以下、G-S アルゴリズムと略す）を用いて求めることができる。その手順は、次の通りである。 入力： 人の男性と 人の女性、および、各人の異性全員に対する希望リスト 出力：安定マッチング（つまり、男女 組のペア） ステップ 0 全員の状態は独身とする（全ての男性はどの女性にもプロポーズを行っていない）。 ステップ 1 独身の男性 h が存在する限り、以下の操作を繰り返す。 1-1 男性 h はまだプロポーズしていない女性の中で、最も好きな（つまり、希望リストの最高位の）相手女性 d に プロポーズする 1-2 (a) d が独身ならば、d は h と婚約する (b) d がすでに h' と婚約している場合 (b-1) d にとって h' のほうが好ましい希望順位が上()ならば、h からのプロポーズを断る (b-2) d にとって h のほうが好ましい（）ならば、h' との婚約を解消し h と婚約する ステップ 2 現在婚約しているペアの集合を安定マッチングとして出力する。（終了） この G-S アルゴリズムは男性がプロポーズするという形式で記述されている。しかし、女性がプロポーズするという形式に変えてもなんら妥当性が失われるわけではない。男性がプロポーズすれば、男性の希望を最も反映した（各男性ごとの安定パートナーの中で最も好ましい女性とペアになっている）男性最良安定マッチングが得られ、女性がプロポーズすると、女性最良安定マッチングを得る。 （男性がプロポーズする）G-S アルゴリズムは、(1) 1 人の男性が同じ女性に 2 度以上プロポーズしない、(2) 女性は婚約すると独身に戻らない、(3) 女性はプロポーズされる際その相手が悪くなることはない、ということからこのアルゴリズムが任意の例に対し、有限回の操作で安定マッチングを必ず導いて終了することがいえる。 ::この業績に対しロイド・シャープレー（89、史上2番目の高齢）に2012年のノーベル経済学賞が与えられた。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「安定結婚問題」の詳細全文を読む スポンサード リンク
|
