安定結婚問題（あんていけっこんもんだい、）とはデイヴィッド・ゲールと ロイド・シャプレイによって1962年に提示された問題である。安定結婚問題はformula_1人の男性とformula_2人の女性、および、各個人の選好順序からなる。選好順序とは各個人の好みに基づき異性全員と自分自身を全順序で並べたリストである。ここで、「自分自身」とは誰とも結婚せずに独身のままでいることを意味し、「参加者全員が独身であるよりも望ましい相手と結婚している」マッチングは個人合理性（）を満たすと定義される。安定結婚問題の解は安定なマッチングである。安定結婚問題に対し、互いに現在組んでいる相手よりも好きであるペア（以下ブロッキングペアとする）が存在せず、全員が個人合理性を満たすマッチングを安定マッチング（）という。下図に安定結婚問題の例題とその例題の解となる安定なマッチング、および、安定でないマッチングを示す。「：」以下が各個人の希望リストである。点線はブロッキングペアを表している。全ての例題について、安定マッチングは必ず存在する。それを見つける "O"("N") 時間アルゴリズムが存在することも知られている（下を参照）。上で述べたように、安定結婚問題の例が与えられたとき安定マッチングは必ず 1 つ以上存在する。そのうちの 1 つ（ないし、2つ）を Gale と Shapley により提案された、ゲール-シャプレイ (Gale-Shapley) アルゴリズム（以下、G-S アルゴリズムと略す）を用いて求めることができる。その手順は、次の通りである。
この G-S アルゴリズムは男性がプロポーズするという形式で記述されている。しかし、女性がプロポーズするという形式に変えてもなんら妥当性が失われるわけではない。男性がプロポーズすれば、男性の希望を最も反映した（各男性ごとの安定パートナーの中で最も好ましい女性とペアになっている）男性最良安定マッチングが得られ、女性がプロポーズすると、女性最良安定マッチングを得る。
（男性がプロポーズする）G-S アルゴリズムは、(1) 1 人の男性が同じ女性に 2 度以上プロポーズしない、(2) 女性は婚約すると独身に戻らない、(3) 女性はプロポーズされる際その相手が悪くなることはない、ということからこのアルゴリズムが任意の例に対し、有限回の操作で安定マッチングを必ず導いて終了することがいえる。

出典:wikipedia