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