「相思相愛」を実現する極めて具体的な方法 その相手には、不満の持ちようがない

ゲール＝シャプレーは、お互いの好みを反映し尽くした理想的な結果である安定マッチングが、どんなマッチング問題にも必ず存在することを示した。

さらに、たった７ページの論文の中で、それを簡単に見つけることができるアルゴリズム（機械的な作業手順）まで明らかにしたのだ。

安定マッチングを導くアルゴリズムは、考案者にちなんでゲール＝シャプレー（ＧＳ）アルゴリズムとよく呼ばれる。

GSアルゴリズムを合コンの例で見てみよう

ここでは、男性グループと女性グループの間の１対１のマッチングというストーリーに沿って、解説していこう。

合コンのようなシチュエーションをイメージすればＯＫだ。男性・女性はそれぞれ何人でも構わない。説明を単純にするため、全員が「誰ともペアにならずに一人でいるのは最悪だ」と思っていることにする。

まず、参加者たち全員から異性グループのメンバーに対する好みをランキングしてもらう必要がある。そして、その好みに基づいて機械的に次の作業を行う。

（※試しにこの図で答えに行き着くまでの過程を考えてみてほしい。詳細な手順はこちら→ ▼経済学で理想のパートナーを探そう！▼）

 
 
 

1． 男性が第1希望の女性に一斉にプロポーズ（提案）

2． 女性は自分の好みにいちばん近い人を選んでキープ（保留）、残りの男性をリジェクト（拒否）

3． 男性はリジェクトされるたびに次に好みの女性にプロポーズ

4． 女性は、より好み（ランキング上位）の男性が来るたびにキープ相手を変更、残りをリジェクト

この作業をリジェクトされる男性がいなくなるまで続けると、なんと最終的なマッチング結果が必ず安定マッチングになるのである。

各ラウンドで決まるパートナーと直ちにペアが確定するのではなく、あくまでキープ、暫定的なパートナーにすぎない、というのが一番のポイントだ。