趣味の数学とプログラム。楽しい数学の世界へようこそ!

安定結婚問題

n人ずつの男女のマッチング方法を考えます。

ペアを組んだときに、お互いに現在の相手より好きなペア(ブロッキングペア)が存在しないようにマッチングさせることは可能でしょうか。

図のように、各自希望順を決めているとします。

たとえば、Aさん―aさん、Bさん―bさん、Cさん―cさん というペアにすると、Cさん―bさんというブロッキングペアが出来てしまいます。(ブロッキングペアは駆け落ちペアともいいます。不穏ですね)

安定マッチングを見つけるアルゴリズムの1つが、ゲール = シャプレイアルゴリズムです。

次のようなステップを繰り返します。

  1. 婚約していない男性が、今まで断られたことのない女性のうち、一番好きな人に告白します。
  2. 告白された女性は、
    婚約:現在婚約していなければ、受け入れて婚約。婚約していれば、婚約中の男性と比べて、告白した男性の方が好きならば、新たに婚約し直す(婚約していた男性にはお断り)
    拒否:婚約中の男性の方が好きならば、告白を断る。

全ての男性が婚約した時点で、そのときの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さんが好きならば、告白を断ったはずがありません。

ブロッキングペアの存在は矛盾しており、即ち安定マッチングであるということになります。

ブロッキングペアが存在しない安定マッチングなので、「安定」結婚問題と呼ばれるというわけです。

 

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です