安定結婚問題
上で述べたように、安定結婚問題の例が与えられたとき安定マッチングは必ず 1 つ以上存在する。そのうちの 1 つ(ないし、2つ)を Gale と Shapley により提案された、ゲール-シャプレイ (Gale-Shapley) アルゴリズム(以下、G-S アルゴリズムと略す)を用いて求めることができる。その手順は、次の通りである。
この G-S アルゴリズムは男性がプロポーズするという形式で記述されている。しかし、女性がプロポーズするという形式に変えてもなんら妥当性が失われるわけではない。男性がプロポーズすれば、男性の希望を最も反映した(各男性ごとの安定パートナーの中で最も好ましい女性とペアになっている)男性最良安定マッチングが得られ、女性がプロポーズすると、女性最良安定マッチングを得る。 (男性がプロポーズする)G-S アルゴリズムは、(1) 1 人の男性が同じ女性に 2 度以上プロポーズしない、(2) 女性は婚約すると独身に戻らない、(3) 女性はプロポーズされる際その相手が悪くなることはない、ということからこのアルゴリズムが任意の例に対し、有限回の操作で安定マッチングを必ず導いて終了することがいえる。
この業績に対しロイド・シャープレー(89、史上2番目の高齢)に2012年のノーベル経済学賞が与えられた。