algorithm - 安定マッチングの反例

Question

私は現在アルゴリズムの本を読んでいて、安定したマッチング問題に遭遇しました。そして、気になる疑問が頭に浮かんだのですが、本は答えていません。問題は次のとおりです。
マッチングが安定していない場合は、任意のブロッキング ペア (w、m) を選択し、それらをマッチングします。また、以前のパートナーと一致します。そして繰り返す。これは、安定したマッチングに到達するための正しいアルゴリズムですか?
答えはノーのようです。しかし、反例が思いつきません。助けてくれる人はいますか？

Answer 1

私は答えを見つけたと思います。3 人の女性と 3 人の男性がいるとします。それらの優先リストは次のとおりです。
w1: m3 > m2 > m1
w2: m2 > m3 > m1
w3: 気にしない

m1:
無視 m2: w1 > w2 > w3
m3: w2 > w1 > w3

最初のマッチング: (w1,m1) (w2,m2) (w3,m3)
ステップ 1: w1 と m2 が一致し、次に (w1,m2) (w2,m1) (w3,m3)
ステップ 2: w1 と m3 が一致する、次に (w1,m3) (w2,m1) (w3,m2)
ステップ 3: w2 と m3 が一致し、次に (w2,m3) (w1,m1) (w3,m2)
ステップ 4: w2 と m2 が一致し、次に(w1,m1) (w2,m2) (w3,m3)

4 つのステップの後、マ​​ッチングは初期状態になり、無限ループにつながります。

Answer 2

あなたが話しているアルゴリズムは、彼らの好みを考慮しないランダムなマッチングです。このアルゴリズムでは、1 つのパートナーの優先順位が高くなり、可能な一致が不安定になる可能性があります。

ソリューションがすべての人にとって公平である定義による安定したマッチング。

また、このアルゴリズムは、以前の一致を回避して無限ループを可能にすることについても言及していません。