ゲール＝シャプレーアルゴリズム～最強のまとめ役1
それでは、みんなにとって望ましいコアを達成する方法を見ていこう。これをマスターすればあなたも立派なまとめ役だ。
といっても、「だれも駆け落ちしない組み合わせ」であるコアを、一から考え出すなんて、複雑で難しいのでは？という印象を受けるだろう。
しかし、実はマッチングの問題において、コアは単純な1つの作業を繰り返すだけで達成することができる。その仕組みはゲール＝シャプレーアルゴリズムと呼ばれている。
スポンサーリンク
それでは、仕組みを見ていこう。
◆ステップ1
すべての男性は、自分の最も好きな女性に告白。女性はそれぞれ、告白してきた男性のうち自分が最も好きな人だけをキープし、それ以外の男の告白をすべて拒否する。
◆ステップ2
拒否された男性は、次に好きな女性に告白する。女性はそれぞれ、2回目に告白してきた男性と、キープを含めて一番好きな人をキープし、それ以外の告白をすべて拒否する。
◆ステップ3
拒否された男性は、その次に好きな女性に告白する。…以下、同じことを繰り返す。
なんとも単純な仕組みではあるが、これがみんなにとって望ましい結果であるコアをもたらすことは、数学的に証明されている。現実には、このように何度も告白することは難しいが、望ましい結果を事前に探り、提案する際に便利である。
スポンサーリンク