旧式SEの計算機室 ｎ人ずつの男女のマッチング方法を考えます。
ペアを組んだときに、お互いに現在の相手より好きなペア（ブロッキングペア）が存在しないようにマッチングさせることは可能でしょうか。
図のように、各自希望順を決めているとします。
たとえば、Aさん―aさん、Bさん―bさん、Cさん―cさん というペアにすると、Cさん―ｂさんというブロッキングペアが出来てしまいます。（ブロッキングペアは駆け落ちペアともいいます。不穏ですね）
安定マッチングを見つけるアルゴリズムの１つが、ゲール = シャプレイアルゴリズムです。
次のようなステップを繰り返します。
- 婚約していない男性が、今まで断られたことのない女性のうち、一番好きな人に告白します。
- 告白された女性は、
婚約：現在婚約していなければ、受け入れて婚約。婚約していれば、婚約中の男性と比べて、告白した男性の方が好きならば、新たに婚約し直す（婚約していた男性にはお断り）
拒否：婚約中の男性の方が好きならば、告白を断る。
全ての男性が婚約した時点で、そのときのｎ組のペアは安定マッチングとなる。
※ループを繰り返すたびに、候補は減っていくので、無限ループになることはありません。
上の図の4組で、このアルゴリズムを実行してみると、Aさん―bさん、Bさん―cさん、Cさん―aさん という結果が出ます。確かにブロッキングペアはありませんね。
ただし、男性側からの告白は男性有利で、Aさん（第2希望）、Bさん(第1希望）、Cさん（第1希望）の相手とペアになれましたが、女性側から見ると、aさん（第3希望）、ｂさん（第2希望）、ｃさん（第3希望）です。
女性側から告白するルールで、アルゴリズムを実行すると、Aさん―aさん、Bさん―cさん、Cさん―bさん と女性に有利な結果になりました。（男性側はそれぞれ、第3，第1、第2希望、女性側は、第1、第1、第2希望）
ゲール = シャプレイアルゴリズムで得られたのが、安定マッチングでなかったとすると、ブロッキングペア（Xさん―ｙさん）が存在します。
↓
Xさんは、必ずｙさんに告白しているので、ｙさんにとって今の相手よりＸさんが好きならば、告白を断ったはずがありません。
↓
ブロッキングペアの存在は矛盾しており、即ち安定マッチングであるということになります。
ブロッキングペアが存在しない安定マッチングなので、「安定」結婚問題と呼ばれるというわけです。
